Patience Sort

Patience sorting is a card sorting algorithm well-suited for partially sorted streams. It builds the sorted pile by adding each element to the pile position where it fits maintaining sorted order.

The algorithm processes a stream of numbers:

Maintain sorted piles where next element for each pile is at top
Take next element and find pile whose top element it can follow while maintaining sort order
Add element to this pile’s position
If no pile, start a new pile with this element

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<Stack<Integer>> patienceSort(Iterator<Integer> stream) {
  List<Stack<Integer>> piles = new ArrayList<>();

  while (stream.hasNext()) {
    int next = stream.next();

    boolean added = false;
    for (Stack<Integer> pile : piles) {
      if (pile.isEmpty() || pile.peek() > next) {
        pile.push(next);
        added = true;
        break;
      }
    }

    if (!added) {
      Stack<Integer> newPile = new Stack<>();
      newPile.push(next);
      piles.add(newPile); 
    }
  }

  return piles;
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<stack<int>> patienceSort(vector<int>::iterator iter) {
  vector<stack<int>> piles;

  while (iter != vec.end()) {
    int next = *iter++;
    
    bool added = false;
    for (auto &pile : piles) {
      if (pile.empty() || pile.top() > next) {
        pile.push(next);
        added = true;
        break; 
      }
    }

    if (!added) {
      stack<int> newPile; 
      newPile.push(next);
      piles.push_back(newPile);
    }
  }

  return piles;
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def patience_sort(stream):

  piles = []

  for next_elem in stream:

    added = False
    for pile in piles:
      if not pile or pile[-1] > next_elem:
        pile.append(next_elem)
        added = True
        break

    if not added:
      piles.append([next_elem])

  return piles

Patience sort efficiently handles streaming partially sorted data. Useful for data processing pipelines.

Patience Sort is a card game-based sorting algorithm that’s used to compute the length of the longest increasing subsequence (LIS) in a given array. It is often used in computer science because of its efficiency and simplicity. It’s named after a solitaire card game called “Patience” where the objective is to sort a deck of cards into some order.

Here’s a high-level description of the Patience Sort algorithm:

Create piles: Start with an empty set of piles. Each pile will hold one or more elements from the array. The piles are arranged from left to right (or in an increasing index order). At any point, the top card of each pile will form a non-increasing sequence.
Iterate over the array: For each element in the array, check if there’s a pile whose top card is greater than or equal to the current element. If there is, place the current element on top of the leftmost such pile. If there isn’t, start a new pile with the current element.
Longest increasing subsequence: The number of piles at the end of the algorithm is the length of the LIS.

Here’s why Patience Sort works: each pile represents a possible ending to an increasing subsequence, and placing a card on top of a pile corresponds to extending that subsequence. The leftmost pile represents the longest possible increasing subsequence found so far.

One thing to note is that the actual LIS can’t be reconstructed from the piles, as the algorithm only maintains the end elements of the possible subsequences. However, variations of this algorithm can maintain extra information to allow the actual subsequence to be reconstructed.

The algorithm runs in O(n log n) time because at each step, it performs a binary search over the piles to decide where to place the current element. This makes it an efficient algorithm for calculating the LIS.

Application

Applying the Patience Sorting algorithm to the Longest Increasing Subsequence (LIS) problem can be achieved as follows:

Create piles: Start with an empty set of piles. Each pile will hold one or more elements from the array. The piles are arranged from left to right (or in increasing index order).
Iterate over the array: For each element in the array, perform a binary search over the piles. If the element is larger than the top card of all piles, start a new pile with the current element. If there’s a pile whose top card is larger than the current element, replace that top card with the current element.
Longest increasing subsequence: The number of piles at the end of the algorithm is the length of the LIS.

Here is a Python code snippet that applies Patience Sorting to solve the LIS problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        piles = []
        for num in nums:
            pos = bisect_left(piles, num)
            if pos == len(piles):
                piles.append(num)
            else:
                piles[pos] = num
        return len(piles)

I assume that the input is a list of integers. Here’s how you can use patience sort to find the length of the Longest Increasing Subsequence (LIS):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from bisect import bisect_left

def lengthOfLIS(nums):
    piles = []
    for num in nums:
        pos = bisect_left(piles, num)
        if pos == len(piles):
            piles.append(num)
        else:
            piles[pos] = num
    return len(piles)

This Python script uses binary search (bisect_left) to decide where to place each number. If a pile whose top card is bigger than the current card is found, the current card will be placed on top of that pile, otherwise, a new pile will be made.

The result is that each “pile” represents a potential subsequence, and the length of the longest increasing subsequence is the total number of piles created. Note that the actual elements in the piles do not necessarily form an increasing subsequence.

This script should run in O(N log N) time, where N is the length of the input list, because each insertion operation is O(log N) and we perform N insertions. This makes it more efficient than the simple dynamic programming approach, which is O(N^2).