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.

About these ads

Pages: 1 2

7 Responses to “Patience Sorting”

  1. 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";
    
  2. Nate said

    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]
    
    
  3. Mike said

    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))
    
  4. Ihor Diachenko said

    #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;
    }

  5. mcmillhj said

    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)
    
  6. Andras said

    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;
    }

  7. Andras said

    Sorry, didn’t read the Howto.
    In Java
    Is it possible to edit a comment?
    Thanks Andras

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

Follow

Get every new post delivered to your Inbox.

Join 628 other followers

%d bloggers like this: