## 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.

I didn’t think to assume no repeating values — here’s a my version in Swift:

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.

#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.

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: