In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
Solitaire is any tabletop game which one can play by oneself or with other people. The solitaire card game Klondike is often known as simply Solitaire....
A card game is any game using playing cards as the primary device with which the game is played, be they traditional or game-specific. Countless card games exist, including families of related games...
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible...
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...
d deck of cards, labeled .
The cards are dealt one by one into a sequence of piles on the table, according to the following rules.
Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
Each new card may be placed either on an existing pile whose top card has a value higher than the new card's value, thus increasing the number of cards in that pile, or to the right of all of the existing piles, thus forming a new pile.
When there are no more cards remaining to deal, the game ends.
The object of the game is to finish with as few piles as possible. D. Aldous and P. Diaconis suggest defining 9 or fewer piles as a winning outcome for , which has approximately 5% chance to happen.
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
as an input for the sorting, consider it as a collection of cards, with the (unknown in the beginning) statistical ordering of each element serving as its index. Note that the game never uses the actual value of the card, except for comparison between two cards, and the relative ordering of any two array elements is known.
Now simulate the patience sorting game, played with the greedy strategy
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
, i.e., placing each new card on the leftmost pile that is legally possible to use. At each stage of the game, under this strategy, the labels on the top cards of the piles are increasing from left to right. To recover the sorted sequence, repeatedly remove the minimum visible card.
Complexity
If values of cards are in the range , there is an efficient implementation with worst-case running time for putting the cards into piles, relying on a van Emde Boas tree
Van Emde Boas tree
A van Emde Boas tree , also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O time...
. A description is given in the work by S. Bespamyatnikh and M. Segal.
When no assumption is made about values, the greedy strategy can be implemented in comparisons in worst case. In fact, one can implement it with an array of stacks ordered by values of top cards and, for inserting a new card, use a binary search
Binary search algorithm
In computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
, which is comparisons in worst case, where is the number of piles. To complete the sorting in an efficient way (aka worst case), each step will retrieve the card with the least value from the top of leftmost pile, and then some work has to be done. Finding the next card by searching it among all tops of piles, as in the wikibooks implementation suggested below, gives a worst case. However, we can use an efficient priority queue(for example, a binary heap) to maintain the piles so that we can extract the maximum data in O(log n) time.
Algorithm for finding a longest increasing subsequence
First, execute the sorting algorithm as described above. The number of piles is the length of a longest subsequence. Whenever a card is placed on top of a pile, put a back-pointer to the top card in the previous pile (that, by assumption, has a lower value than the new card has). In the end, follow the back-pointers from the top card in the last pile to recover a decreasing subsequence of the longest length; its reverse is an answer to the longest increasing subsequence algorithm.
S. Bespamyatnikh and M. Segal give a description of an efficient implementation of the algorithm, incurring no additional asymptotic cost over the sorting one (as the back-pointers storage, creation and traversal require linear time and space). They further show how to report all the longest increasing subsequences from the same resulting data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s.
C++ Implementation
This is an implementation using Patience Sorting to sort an array, performing O(n log n) time complexity.
for (Iterator it = begin; it != end; it++)
{
PileType new_pile;
new_pile.push(*it);
typename std::vector::iterator insert_it =
std::lower_bound(piles.begin, piles.end, new_pile,
pile_less);
if (insert_it piles.end)
piles.push_back(new_pile);
else
insert_it->push(*it);
}
// sorted array already satisfies heap property for min-heap
for (Iterator it = begin; it != end; it++)
{
std::pop_heap(piles.begin, piles.end, pile_more);
*it = piles.back.top;
piles.back.pop;
if (piles.back.empty)
piles.pop_back;
else
std::push_heap(piles.begin, piles.end, pile_more);
}
}
Java Implementation
import java.util.*;
public class PatienceSort
{
public static > void sort (E[] n)
{
List> piles = new ArrayList>;
// sort into piles
for (E x : n)
{
Pile newPile = new Pile;
newPile.push(x);
int i = Collections.binarySearch(piles, newPile);
if (i < 0) i = ~i;
if (i != piles.size)
piles.get(i).push(x);
else
piles.add(newPile);
}
System.out.println("longest increasing subsequence has length = " + piles.size);
// priority queue allows us to retrieve least pile efficiently
PriorityQueue> heap = new PriorityQueue>(piles);
for (int c = 0; c < n.length; c++)
{
Pile smallPile = heap.poll;
n[c] = smallPile.pop;
if (!smallPile.isEmpty)
heap.offer(smallPile);
}
assert(heap.isEmpty);
}
private static class Pile> extends Stack implements Comparable>
{
public int compareTo(Pile y) { return peek.compareTo(y.peek); }
}
}
History
According to D. Aldous and P. Diaconis, patience sorting was first recognized as an algorithm to compute the longest increasing subsequence length by Hammersley, and by A.S.C. Ross and independently Robert W. Floyd as a sorting algorithm. Initial analysis was done by Mallows.
Use
The Bazaar version control system uses the patience sorting algorithm for merge resolution.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
.
, which has approximately 5% chance to happen.
-element array with an ordering
, there is an efficient implementation with 
worst-case running time for putting the cards into piles, relying on a van Emde Boas tree
comparisons in worst case. In fact, one can implement it with an array of stacks ordered by values of top cards and, for inserting a new card, use a binary search
comparisons in worst case, where 
is the number of piles. To complete the sorting in an efficient way (aka 
worst case), each step will retrieve the card with the least value from the top of leftmost pile, and then some work has to be done. Finding the next card by searching it among all tops of piles, as in the wikibooks implementation suggested below, gives a 
worst case. However, we can use an efficient priority queue(for example, a binary heap) to maintain the piles so that we can extract the maximum data in O(log n) time.