Algorithm Implementation/Sorting/Patience sort

C++

Given a generic STL-style input iterator to a sequence, we shall call its elements' value type card_type, and assume that we have some container of cards PileType (an example could be vector<card_type>), and a container of piles TableType (which, again, could be just a vector of piles).

In this case, one can define the patience sorting as follows:

    /**
     * Patience sort algorithm as per Aldous and Diaconis,
     * using binary search to select the leftmost heap for a new card.
     * Compares cards using operator<
     * 
     * TableType requirements
     *  -# whatever lower_bound needs
     *  -# begin(), end(): ForwardIterator of piles
     * 
     * PileType requirements
     *  -# default constructible
     *  -# constructible from a single card const reference
     *      typedef typename PileType::value_type card_type;
     *  -# push_back(const card_type&)
     *  -# assignable, lightweight on a singleton pile
     *  -# whatever lower_bound needs
     *  -# back() implemented or an appropriate pile_less specialization
     */
    template < typename PileType, typename TableType, typename InputIterator > 
    void patience_sort(TableType& table, InputIterator first, InputIterator last) {
        typedef PileType pile_type;
        typedef typename PileType::value_type card_type;
        typedef TableType table_type;
        typedef typename table_type::iterator iterator;
 
        while (first != last) {
            pile_type new_pile(*first); // read *first only once! (input iterator)
            // find the leftmost heap with the top card greater 
            // than *first , to push *first on it
            iterator pile_p = std::lower_bound(
                                table.begin(), table.end(), new_pile, 
                                pile_less<pile_type>() );
            if (pile_p != table.end()) {
                pile_p->push_back(new_pile.back());
            }
            // ...or allocate a new heap on the right with *first
            else {
                table.push_back(new_pile);
            }
            first++;
        }
    }

For the std::lower_bound algorithm to work, a tiny utility comparator functor is needed:

  /**
   * Comparator for two piles according to their top card values.
   * Compares cards using operator<
   */
  template < typename pile_type >
  struct pile_less : std::binary_function<pile_type, pile_type, bool>
  {
      bool operator()(const pile_type& x, const pile_type& y) const
      {
          return x.back() < y.back();
      }
  };
/**
 * When the algorithm is run with the sole purpose to discover the length of the longest increasing subsequence, 
 * one doesn't need to store any cards in the piles beneath the topmost one, since only the topmost card's value
 * is ever used by the algorithm above, and the length of the longest increasing subsequence is equal to the number of piles on the
 * table,
 * i.e., ''table.size()'':
 */
    /** 
     * A class representing a pile that is sticky, i.e., once a card
     * is put onto its top, it's glued forever. This way, only
     * the top card is actually remembered (O(1) memory per heap).
     * Used by longest_increasing_subsequence().
     *
     * Unfortunately, such heap is impossible to use in more advanced
     * algorithms, such as the Bespamyatnykh and Segal one, for the
     * actual longest increasing subsequence recovery.
     */
    template< typename Card >
    struct StickyPile { // cards stick together when put here :-)
        typedef Card value_type;
        typedef const value_type& const_reference;
        StickyPile(const Card& _card) : card(_card) {}
        void push_back(const Card& _card) { card = _card; }
        const_reference back() const { return card; }
    private:
        Card card;
    };
 
    /** Find the length of the longest increasing subsequence
     * given by the given iterator range, using patience_sort().
     * Compares cards using operator<
     */
    template< typename InputIterator >
    size_t longest_increasing_subsequence( 
            InputIterator first, InputIterator last)
    {
        typedef typename std::iterator_traits<InputIterator>::value_type Card;
        typedef StickyPile<Card> pile_type;
        typedef std::vector< pile_type > table_type;
        table_type table;
        patience_sort<pile_type>(table, first, last);
        return table.size();
    }
 
/* The above GPL code is based on excerpts from [[http://www.tarunz.org/~vassilii/pub/c++/patience_sort.hpp patience_sort.hpp]],
 which also provides versions of the same functionality parametrized by any given comparator (rather than using operator< ). */

Java

import java.util.*;
public class PatienceSort
{
    public static <E extends Comparable<? super E>> void sort (E[] n)
    {
        List<Pile<E>> piles = new ArrayList<Pile<E>>();
        // sort into piles
        for (E x : n)
        {
            Pile<E> newPile = new Pile<E>();
            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<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles);
        for (int c = 0; c < n.length; c++)
        {
            Pile<E> smallPile = heap.poll();
            n[c] = smallPile.pop();
            if (!smallPile.isEmpty())
                heap.offer(smallPile);
        }
        assert(heap.isEmpty());
    }
 
    private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>>
    {
        public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); }
    }
}

Python

import bisect, heapq
 
def sort(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 "longest increasing subsequence has length =", len(piles)
 
    # priority queue allows us to retrieve least pile efficiently
    for i in xrange(len(seq)):
        small_pile = piles[0]
        seq[i] = small_pile.pop(0)
        if small_pile:
            heapq.heapreplace(piles, small_pile)
        else:
            heapq.heappop(piles)
    assert not piles
 
foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1]
sort(foo)
print foo