ISourceCode

Make the frequent cases fast and the rare case correct

Patience Sorting

Using the Solitaire card game

The game begins with a shuffled deck of cards, labeled 1, 2,…, n.

The cards are dealt one by one into a sequence of piles on the table, according to the following rules.

1. Initially, there are no piles. The first card dealt forms a new pile consisting of the single card.
2. 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.
3. 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 n = 52, which has approximately 5% chance to happen. – Wikipedia

For a theoretical introduction to this sorting mechanism please refer to my earlier article Patience sorting and Longest increasing subsequence.

for the sequence 7 2 8 1 3 4 10 6 9 5

We have a pile formation shown below with no of piles = 5

Implementation: Not efficient as i have not used a O(lgn) priority queue based popping algorithm from the piles that will be formed. I use a recursive procedure

import bisect
import random 

def popped(piles,l):
	for a in range(0,l):
		if not piles[a]:
			piles.pop(a)
			return 
def asc(piles):
	length = len(piles)
	print "***"
	print "Groups still left",length
 	 
	small = piles[0][0]
	for i in range(0,length):
		if piles[i][0] < small:
			small = piles[i][0]
	result.append(small)
	print "The current sorted resultant list",result	
	for j in range(0,length):
		if piles[j][0] == small:
		
			piles[j].pop(0)
			print "The minimum that was popped and added to resultant = ",small
			print "groups after popping the current minimum",piles
	val = popped(piles,length)
	
	if len(piles) == 0:	
		print "End of algorithm"
	else:		
		asc(piles)
	
			
def grouping(seq):
	piles = []
    	for x in seq:
        	new_pile = [x]
        	i = bisect.bisect_left(piles, new_pile)
        	if i != len(piles):
            		piles[i].insert(0, x)
        	else:
            		piles.append(new_pile)	
	print "The piles formed for the given input are",piles
	
	asc(piles)
    	

result = []
input = range(1,8)
random.shuffle(input)
print "Random input is ",input
grouping(input)
print "Sorted list is",result	

OUPUT:

labuser@ubuntu:~$ python sortpatience.py
Random input is [6, 1, 5, 3, 2, 4, 7]
The piles formed for the given input are [[1, 6], [2, 3, 5], [4], [7]]
***
Groups still left 4
The current sorted resultant list [1]
The minimum that was popped and added to resultant = 1
groups after popping the current minimum [[6], [2, 3, 5], [4], [7]]
***
Groups still left 4
The current sorted resultant list [1, 2]
The minimum that was popped and added to resultant = 2
groups after popping the current minimum [[6], [3, 5], [4], [7]]
***
Groups still left 4
The current sorted resultant list [1, 2, 3]
The minimum that was popped and added to resultant = 3
groups after popping the current minimum [[6], [5], [4], [7]]
***
Groups still left 4
The current sorted resultant list [1, 2, 3, 4]
The minimum that was popped and added to resultant = 4
groups after popping the current minimum [[6], [5], [], [7]]
***
Groups still left 3
The current sorted resultant list [1, 2, 3, 4, 5]
The minimum that was popped and added to resultant = 5
groups after popping the current minimum [[6], [], [7]]
***
Groups still left 2
The current sorted resultant list [1, 2, 3, 4, 5, 6]
The minimum that was popped and added to resultant = 6
groups after popping the current minimum [[], [7]]
***
Groups still left 1
The current sorted resultant list [1, 2, 3, 4, 5, 6, 7]
The minimum that was popped and added to resultant = 7
groups after popping the current minimum [[]]
End of algorithm
Sorted list is [1, 2, 3, 4, 5, 6, 7]
labuser@ubuntu:~$

The above implementation shows how the piles are formed , how the minimum element is popped after making O(n) comparison and how the piles change dynamically after each pop eventually leading to an empty pile

Also in the LIS article we find the length of increasing subsequence from counting number of piles. However to find the actual sequence we need to first build the piles and during building the pile we need to follow this strategy: 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.

If we use a priority queue mechanism to pop the elements to build the sorted list and then use O(P) backtracking algorithm explained above to build the subsequence then

the whole process is in O(N lg P) + O(P) where N is no of elements and P is no of piles

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: