Patience sorting in Python
Deals elements onto piles by binary search and merges them; the pile count equals the longest increasing subsequence length.
- File
patience_sorting.py, 107 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/patience-sorting/. The authors are listed in prov/JTB25B.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def deal(a: list[T]) -> list[list[T]]:
"""Deal the items onto piles. Each pile is a list from bottom to top.
Each item goes on the leftmost pile whose top is greater than it, or on a new pile at the right.
"""
piles: list[list[T]] = []
for x in a:
lo, hi = 0, len(piles)
while lo < hi: # the tops are non-decreasing from left to right
mid = (lo + hi) // 2
if x < piles[mid][-1]:
hi = mid
else:
lo = mid + 1
if lo == len(piles):
piles.append([])
piles[lo].append(x)
return piles
def longest_nondecreasing_subsequence(a: list[T]) -> list[T]:
"""Return a longest non-decreasing subsequence of a, using the piles and back links."""
tops: list[int] = [] # the index in a of the top of each pile
back: list[int] = [-1] * len(a)
for idx, x in enumerate(a):
lo, hi = 0, len(tops)
while lo < hi:
mid = (lo + hi) // 2
if x < a[tops[mid]]:
hi = mid
else:
lo = mid + 1
back[idx] = tops[lo - 1] if lo > 0 else -1
if lo == len(tops):
tops.append(idx)
else:
tops[lo] = idx
out: list[T] = []
j = tops[-1] if tops else -1
while j >= 0:
out.append(a[j])
j = back[j]
out.reverse()
return out
def patience_sorting(a: list[T]) -> None:
"""Sort the list a in place, in non-decreasing order. The sort is stable."""
piles: list[list[T]] = [] # @line L1
for x in a: # @line L2
lo, hi = 0, len(piles) # @line L3
while lo < hi:
mid = (lo + hi) // 2
if x < piles[mid][-1]:
hi = mid
else:
lo = mid + 1
if lo == len(piles): # @line L4
piles.append([])
piles[lo].append(x) # @line L5
def less(p: int, q: int) -> bool:
# Order the piles by their top item, and on a tie by their index.
x, y = piles[p][-1], piles[q][-1]
if x < y:
return True
if y < x:
return False
return p < q
heap = list(range(len(piles)))
def sift_down(i: int) -> None:
while True:
left, s = 2 * i + 1, i
if left < len(heap) and less(heap[left], heap[s]):
s = left
if left + 1 < len(heap) and less(heap[left + 1], heap[s]):
s = left + 1
if s == i:
return
heap[i], heap[s] = heap[s], heap[i]
i = s
for i in range(len(heap) // 2 - 1, -1, -1): # @line L6
sift_down(i)
for t in range(len(a)): # @line L7
p = heap[0] # @line L8
a[t] = piles[p].pop()
if not piles[p]: # @line L9
heap[0] = heap[-1]
heap.pop()
if heap:
sift_down(0)
test_patience_sorting.py 65 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/patience-sorting/. The authors are listed in prov/JTB25B.jsonl.
import itertools
import random
from patience_sorting import deal, longest_nondecreasing_subsequence, patience_sorting
def test_example() -> None:
a = [5, 1, 4, 2, 8, 3, 7, 6]
assert deal(a) == [[5, 1], [4, 2], [8, 3], [7, 6]]
assert longest_nondecreasing_subsequence(a) == [1, 2, 3, 6]
patience_sorting(a)
assert a == [1, 2, 3, 4, 5, 6, 7, 8]
def brute_longest(a: list[int]) -> int:
best = 0
for r in range(len(a) + 1):
for idx in itertools.combinations(range(len(a)), r):
if all(a[idx[t]] <= a[idx[t + 1]] for t in range(r - 1)):
best = max(best, r)
return best
def test_piles_equal_longest_nondecreasing() -> None:
rng = random.Random(3)
for _ in range(300):
a = [rng.randint(0, 5) for _ in range(rng.randint(0, 10))]
s = longest_nondecreasing_subsequence(a)
assert len(deal(a)) == len(s) == brute_longest(a)
assert all(s[t] <= s[t + 1] for t in range(len(s) - 1))
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], list(range(30)), list(range(30, 0, -1))):
b = list(a)
patience_sorting(b)
assert b == sorted(a)
def test_stable() -> None:
class Key:
def __init__(self, k: int, tag: int) -> None:
self.k, self.tag = k, tag
def __lt__(self, other: "Key") -> bool:
return self.k < other.k
rng = random.Random(8)
for _ in range(200):
pairs = [(rng.randint(0, 4), i) for i in range(rng.randint(0, 30))]
b = [Key(k, t) for k, t in pairs]
patience_sorting(b)
assert [(x.k, x.tag) for x in b] == sorted(pairs)
def test_random_against_sorted() -> None:
rng = random.Random(10)
for _ in range(100):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 300))]
b = list(a)
patience_sorting(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build