算法实现/排序/耐心排序
给定一个通用的 STL 风格的输入迭代器到一个序列，我们将称其元素的值类型为 card_type，并假设我们有一些卡片容器 PileType（一个例子可以是 vector<card_type>），以及一堆容器 TableType（它，再次，可以只是一个堆的向量）。
在这种情况下，可以将耐心排序定义如下
/**
* 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++;
}
}
为了使 std::lower_bound 算法起作用，需要一个很小的实用比较器函数对象
/**
* 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< ). */
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()); }
}
}
import bisect
import 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 range(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)
使用耐心排序方法实现。放置在堆上的元素 (newelem) 将“卡片”与先前堆栈顶部的引用结合在一起，如算法所述。组合是使用 cons 完成的，所以放在堆上的东西是一个列表——一个递减子序列。[1]
(defn place [piles card]
(let [[les gts] (->> piles (split-with #(<= (ffirst %) card)))
newelem (cons card (->> les last first))
modpile (cons newelem (first gts))]
(concat les (cons modpile (rest gts)))))
(defn a-longest [cards]
(let [piles (reduce place '() cards)]
(->> piles last first reverse)))
(println (a-longest [3 2 6 4 5 1]))
(println (a-longest [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]))
输出
(2 4 5)
(0 2 6 9 11 15)
package main
import (
"fmt"
"container/heap"
)
type PileHeap [][]int
func (h PileHeap) Len() int { return len(h) }
func (h PileHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h PileHeap) Less(i, j int) bool {
return h[i][len(h[i])-1] < h[j][len(h[j])-1]
}
func (h *PileHeap) Push(x interface{}) {
*h = append(*h, x.([]int))
}
func (h *PileHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
/*
bisectPilesRight uses binary search to returns the index where to insert card x,
assuming piles is already sorted according to the value of the top card
in each pile
The return value i is such that it's the largest i
for which the top card in piles[i] >= x and
return i == len(piles) if no such pile can be found
*/
func bisectPilesRight(piles [][]int , x int) int {
lo, hi := 0, len(piles)
for lo < hi {
// invariant: x maybe between a[lo]...a[hi-1]
mid := lo + (hi-lo)/2 // don't use (lo+hi)/2 to avoid overflow
// Note that since (hi-lo)/2 >= 0, lo <= mid < hi
pile := piles[mid]
if x < pile[len(pile) - 1] { // compare x to top of pile
hi = mid // x may be between a[lo]...a[mid-1]
} else {
lo = mid+1 // x may be between a[mid+1]...a[hi]
}
// The new range is either lo...mid or mid+1...hi and
// because lo<=mid<hi, the new range is always smaller than lo..hi
}
return lo
}
func PatienceSort(a []int) []int {
piles := make([][]int, 0, 10) // each pile will be a slice.
for _, x := range(a) {
i := bisectPilesRight(piles, x)
if i < len(piles) {
piles[i] = append(piles[i], x)
} else {
piles = append(piles, []int{x}) // make a new pile
}
// fmt.Println(piles)
}
h := PileHeap(piles) // Use piles as a heap
// heap.Init(&h) is not need because piles are already sorted by top card
n := len(a)
sorted := make([]int, n)
for i := 0; i < n; i++ {
pile := heap.Pop(&h).([]int)
top := len(pile) - 1
sorted[i] = pile[top]
if top > 0 {
// Put pile minus the top card back in heap if it is not empty
heap.Push(&h, pile[:top])
}
}
return sorted
}
func main() {
a := []int{2,6,3,1,5,9,2}
fmt.Print(patienceSort(a))
}
function patience_sort(sequence s)
-- create list of sorted lists
sequence piles = {}
for i=1 to length(s) do
object n = s[i]
for p=1 to length(piles)+1 do
if p>length(piles) then
piles = append(piles,{n})
elsif n>=piles[p][$] then
piles[p] = append(piles[p],n)
exit
end if
end for
end for
-- merge sort the piles
sequence res = ""
while length(piles) do
integer idx = smallest(piles,return_index:=true)
res = append(res,piles[idx][1])
if length(piles[idx])=1 then
piles[idx..idx] = {}
else
piles[idx] = piles[idx][2..$]
end if
end while
return res
end function