Patience Sorting
August 22, 2014
For simplicity, we assume the cards are represented by integers and that there are no duplicates. The function that deals the cards into piles repeatedly considers the top card on the deck; note that, at each step, the cards at the tops of the piles are arranged in increasing order:
(define (deal deck)
(let loop ((deck deck) (selip (list)) (piles (list)))
(cond ((null? deck) piles) ; no more cards in deck
((null? piles) ; add card to new pile
(loop (cdr deck) (list)
(reverse (cons (list (car deck)) selip))))
((< (car deck) (caar piles)) ; found correct pile
(loop (cdr deck) (list)
(append (reverse selip)
(list (cons (car deck) (car piles)))
(cdr piles))))
(else ; continue search for correct pile
(loop deck (cons (car piles) selip) (cdr piles))))))
To sort the deck, we repeatedly move the minimum top-card to the output; the outer loop collects the output in list xs while the inner loop removes the minimum card from the piles:
(define (sort deck)
(let loop1 ((xs (list)) (piles (deal deck)))
(if (null? piles) (reverse xs)
(let ((x (apply min (map car piles))))
(let loop2 ((piles piles) (selip (list)))
(if (= (caar piles) x)
(loop1 (cons x xs)
(append (reverse selip)
(if (null? (cdar piles)) (list)
(list (cdar piles)))
(cdr piles)))
(loop2 (cdr piles) (cons (car piles) selip))))))))
After all the cards are dealt, and in fact at each stage in the dealing, the top cards of the piles are always in ascending order. It makes sense to take advantage of that fact and turn the sorting stage “inside-out;” instead of searching for the minimum at each stage, always take the minimum item from the top of the first pile, then move the remainder of the first pile to its proper position in the list of piles to maintain the sorted order of the top cards of the piles. Like this:
(define (insert xs xss)
(if (null? xs) xss
(let loop ((xss xss) (rev (list)))
(if (null? xss) (reverse (cons xs rev))
(if (< (car xs) (caar xss))
(append (reverse rev) (list xs) xss)
(loop (cdr xss) (cons (car xss) rev)))))))
(define (sort deck)
(let loop ((xs (list)) (piles (deal deck)))
(if (null? piles) (reverse xs)
(loop (cons (caar piles) xs)
(insert (cdar piles) (cdr piles))))))
You can run the program at http://programmingpraxis.codepad.org/KWZtp2C1.
Programming Praxis 
use strict; my @Q = qw(4 3 9 1 5 2 7 8 6); my $cols = []; foreach (@Q) { my $f = 0; $f++ while $f<@{$cols} && $_ > $cols->[$f][0]; unshift @{$cols->[$f]},$_; ## Going to use unshift so stacks stored upside down! } my @res; while(@{$cols}) { my( $m_s, $min, $s ) = ( 0, $cols->[0][0], 0 ); foreach( @{$cols} ) { ($m_s,$min) = ($s,$_->[0]) if $_->[0] < $min; $s++; } push @res, shift @{$cols->[$m_s]}; ## shift entry off.... splice @{$cols},$m_s,1 unless @{$cols->[$m_s]}; ## Remove any empty stacks! } print "@res\n";I didn’t think to assume no repeating values — here’s a my version in Swift:
struct PatienceSorter : SequenceType { typealias Generator = PatienceGenerator var stacks: [[Int]] = [] init(_ numbers: [Int]) { numberLoop: for num in numbers { for i in 0..<stacks.count { if stacks[i].last! >= num { stacks[i].append(num) continue numberLoop } } stacks.append([num]) } } func generate() -> PatienceGenerator { return PatienceGenerator(stacks) } struct PatienceGenerator : GeneratorType { var _stacks: [[Int]] init(_ stacks: [[Int]]) { _stacks = stacks } mutating func next() -> Int? { switch _stacks.count { case 0: return nil default: var loweststack = 0 for i in 0..<_stacks.count { if _stacks[i].last! <= _stacks[loweststack].last! { loweststack = i } } let next = _stacks[loweststack].removeLast() if _stacks[loweststack].count == 0 { _stacks.removeAtIndex(loweststack) } return next } } } } let norepeatSort = PatienceSorter(shuffle(Array(1...20))) println(norepeatSort.stacks) // [[9, 8, 6, 3, 2, 1], [14, 13, 12, 4], [15, 5], [20, 17, 11, 7], [19, 16, 10], [18]] println(Array(norepeatSort)) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] let repeatSort = PatienceSorter([6, 4, 3, 7, 3, 5, 1, 1, 2, 8, 6, 4, 8, 4, 5, 2, 1, 5, 4, 8]) println(repeatSort.stacks) // [[6, 4, 3, 3, 1, 1, 1], [7, 5, 2, 2], [8, 6, 4, 4, 4], [8, 5, 5], [8]] println(Array(repeatSort)) // [1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 8, 8, 8]The problem says to add an item to the top of a pile if it is smaller that
the current top of the pile. However, it is more efficient to append an item
to the end of a list, so this function adds an item to the bottom of a pile
(end of a list), if it is greater than the current bottom of the pile.
from heapq import merge def psort(seq): piles = [] for item in seq: for pile in piles: if item > pile[-1]: pile.append(item) break else: piles.append([item]) return list(merge(*piles))#include
#include
#include
using namespace std;
bool try_insert(vector<vector> &piles, int x)
{
if (piles.size() == 0)
return false;
for (auto &pile: piles)
{
if (x <= pile.back())
{
pile.push_back(x);
return true;
}
}
return false;
}
int pop_least(vector<vector> &piles)
{
int least, least_i;
for (int i = 0; i < piles.size(); i++)
{
if (i == 0)
least_i = i, least = piles[i].back();
else if (piles[i].back() < least)
least_i = i, least = piles[i].back();
}
piles[least_i].pop_back();
if (piles[least_i].size() == 0) piles.erase(piles.begin() + least_i);
return least;
}
void patience_sort(vector &v)
{
vector<vector> piles;
for (int i = 0; i < v.size(); i++)
{
if(!try_insert(piles, v[i]))
piles.push_back(vector{v[i]});
}
for (int i = 0; i < v.size(); i++)
v[i] = pop_least(piles);
}
int main(void)
{
int n;
cout <> n;
cout <<"Elements: ";
vector v;
int tmp;
for (int i = 0; i >tmp;
v.push_back(tmp);
}
patience_sort(v);
for (int x: v)
cout << x <<" ";
cout <<endl;
}
Cool problem.
(define (build-stacks deck) (build-stacks-helper deck (list))) (define (build-stacks-with-existing deck stacks) (build-stacks-helper deck stacks)) (define (build-stacks-helper deck stacks) (define (aux deck buffer stacks) (cond ((null? deck) stacks) ; no cards left in deck ((null? stacks) ; add a new stack ;; recurse ;; remove top card from deck ;; buffer is empty because we are adding a stack ;; append new stack to the END of any stacks we were already holding ;; in buffer (aux (cdr deck) (list) (reverse (cons (list (car deck)) buffer)))) ((< (car deck) (caar stacks)) ; card should go in this stack ;; recurse ;; remove top card from deck ;; buffer is empty because we are adding to an existing stack ;; insert card into existing stack between to remainder of ;; stacks and any cards we have stored in buffer (aux (cdr deck) (list) (append (reverse buffer) (list (cons (car deck) (car stacks))) (cdr stacks)))) (else ; wrong stack ;; recurse ;; deck stays the same ;; add the current stack to the buffer ;; look at next stack (aux deck (cons (car stacks) buffer) (cdr stacks))))) (aux deck (list) stacks)) ; sorting ; since all of the stacks are held in increasing order by the above code ; we can "sort" by taking the top value from the first stack then ; re-build the remainder of the first stack over the other stacks (define (sort-stacks deck) (define (aux sorted-deck stacks) (display sorted-deck) (newline) (display stacks) (newline) (if (null? stacks) sorted-deck (aux (append sorted-deck (list (caar stacks))) (build-stacks-with-existing (reverse (cdar stacks)) (cdr stacks))))) (aux (list) (build-stacks deck))) (define deck '(4 3 9 1 5 2 7 8 6)) (sort-stacks deck) ;; () ;; ((1 3 4) (2 5 9) (6 7) (8)) ;;(1) ;; ((2 5 9) (3 4 6 7) (8)) ;; (1 2) ;; ((3 4 6 7) (5 8) (9)) ;; (1 2 3) ;; ((4 5 8) (6 7 9)) ;; (1 2 3 4) ;; ((5 6 7 9) (8)) ;; (1 2 3 4 5) ;; ((6 7 8) (9)) ;; (1 2 3 4 5 6) ;; ((7 8 9)) ;; (1 2 3 4 5 6 7) ;; ((8 9)) ;; (1 2 3 4 5 6 7 8) ;; ((9)) ;; (1 2 3 4 5 6 7 8 9) ;; () ;;(1 2 3 4 5 6 7 8 9)Java:
public static <T extends Comparable> List sort(List list) {
List<Stack> stacks = newArrayList();
for (T next : list) {
Stack stackForNext = null;
for (Stack stack : stacks) {
if (next.compareTo(stack.peek()) < 0) {
stackForNext = stack;
break;
}
}
if (stackForNext == null) {
stackForNext = new Stack();
stacks.add(stackForNext);
}
// System.out.println("push " + next + " -> " + stackForNext);
stackForNext.push(next);
// System.out.println(" " + stacks);
}
List sortedList = newArrayList();
for (int i = 0; i < list.size(); i++) {
Stack stackWithSmallest = null;
for (Stack stack : stacks) {
if (stackWithSmallest == null || stackWithSmallest.size() == 0
|| (stack.size() > 0 && stack.peek().compareTo(stackWithSmallest.peek()) < 0)) {
stackWithSmallest = stack;
}
}
sortedList.add(stackWithSmallest.pop());
}
return sortedList;
}
Sorry, didn’t read the Howto.
In Java
Is it possible to edit a comment?
Thanks Andras
Another Python solution:
def patience_sort(items):
piles = []
while items:
x = items.pop(0)
added = False
for p in piles:
if p[0] > x:
p.insert(0, x)
added = True
break
if not added:
p = [x]
piles.append(p)
sorted_items = []
while piles:
min_pile, min_item = None, None
for p in piles:
if not min_pile or p[0] < min_item:
min_pile = p
min_item = p[0]
sorted_items.append(min_item)
min_pile.pop(0)
if not min_pile:
piles.remove(min_pile)
return sorted_items
if __name__ == '__main__':
print(patience_sort([4, 3, 9, 1, 5, 2, 7, 8, 6]))
[/sourcecode}
Fix formatting:
def patience_sort(items): piles = [] while items: x = items.pop(0) added = False for p in piles: if p[0] > x: p.insert(0, x) added = True break if not added: p = [x] piles.append(p) sorted_items = [] while piles: min_pile, min_item = None, None for p in piles: if not min_pile or p[0] < min_item: min_pile = p min_item = p[0] sorted_items.append(min_item) min_pile.pop(0) if not min_pile: piles.remove(min_pile) return sorted_items if __name__ == '__main__': print(patience_sort([4, 3, 9, 1, 5, 2, 7, 8, 6]))