Columnsort in Python
Sorts an r by s matrix with a fixed sequence of column sorts and fixed permutations, when r is large relative to s.
- File
columnsort.py, 77 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/columnsort/. The authors are listed in prov/HTGXH0.jsonl.
"""Leighton's columnsort on an r by s matrix, stored as a list of s columns.
Each of the four column sorts would run on s processors at once; here
the columns are sorted one after the other, which gives the same result.
The output is sorted in column-major order.
"""
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def sort_columns(cols: list[list[T]]) -> list[list[T]]:
return [sorted(c) for c in cols]
def column_major(cols: list[list[T]]) -> list[T]:
return [x for c in cols for x in c]
def from_column_major(seq: list[T], r: int) -> list[list[T]]:
return [seq[k : k + r] for k in range(0, len(seq), r)]
def transpose_step(cols: list[list[T]]) -> list[list[T]]:
"""Step 2: pick up the keys column by column, lay them down row by row."""
r, s = len(cols[0]), len(cols)
seq = column_major(cols)
return [[seq[i * s + k] for i in range(r)] for k in range(s)]
def untranspose_step(cols: list[list[T]]) -> list[list[T]]:
"""Step 4: the inverse of step 2, rows read in order, laid down column by column."""
r, s = len(cols[0]), len(cols)
seq = [cols[k][i] for i in range(r) for k in range(s)]
return from_column_major(seq, r)
def shift_sort_unshift(cols: list[list[T]]) -> list[list[T]]:
"""Steps 6 to 8: sort the windows of the column-major order that start
half a column late. The padding keys of the shifted matrix never move,
so they are left out."""
r = len(cols[0])
seq = column_major(cols)
half = r - r // 2 # @line L6: the first shifted column holds ceil(r/2) real keys
out = sorted(seq[:half])
for k in range(half, len(seq), r): # @line L7
out.extend(sorted(seq[k : k + r]))
return from_column_major(out, r) # @line L8
def columnsort(cols: list[list[T]], check: bool = True) -> list[list[T]]:
"""Return the matrix sorted in column-major order.
With check=True, require s to divide r and r >= 2 (s - 1)^2."""
s = len(cols)
if s == 0:
return []
r = len(cols[0])
if any(len(c) != r for c in cols):
raise ValueError("all columns must have the same length")
if check and (r % s != 0 or r < 2 * (s - 1) ** 2):
raise ValueError("columnsort needs s | r and r >= 2 (s - 1)^2")
cols = sort_columns(cols) # @line L1
cols = transpose_step(cols) # @line L2
cols = sort_columns(cols) # @line L3
cols = untranspose_step(cols) # @line L4
cols = sort_columns(cols) # @line L5
return shift_sort_unshift(cols)
test_columnsort.py 62 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/columnsort/. The authors are listed in prov/HTGXH0.jsonl.
import itertools
import random
import pytest
from columnsort import column_major, columnsort, sort_columns, transpose_step, untranspose_step
EXAMPLE = [
[3, 11, 5, 13, 10, 14, 27, 25, 19],
[26, 7, 4, 18, 16, 22, 6, 2, 8],
[15, 1, 17, 21, 23, 12, 24, 9, 20],
]
def test_example() -> None:
out = columnsort(EXAMPLE)
assert out == [list(range(1, 10)), list(range(10, 19)), list(range(19, 28))]
def test_example_after_step_five() -> None:
cols = sort_columns(untranspose_step(sort_columns(transpose_step(sort_columns(EXAMPLE)))))
assert cols[0] == [1, 2, 3, 4, 5, 6, 8, 10, 12]
def test_steps_two_and_four_are_inverse() -> None:
cols = [[1, 2, 3, 4], [5, 6, 7, 8]]
assert transpose_step(cols) == [[1, 3, 5, 7], [2, 4, 6, 8]]
assert untranspose_step(transpose_step(cols)) == cols
def zero_one_inputs(r: int, s: int):
"""After step 1 a 0-1 matrix depends only on the zeros in each column."""
for zeros in itertools.product(range(r + 1), repeat=s):
yield [[0] * z + [1] * (r - z) for z in zeros]
def test_all_zero_one_inputs_small() -> None:
for r, s in ((2, 2), (4, 2), (9, 3), (12, 3)):
for cols in zero_one_inputs(r, s):
out = column_major(columnsort(cols))
assert out == sorted(out)
def test_condition_is_needed() -> None:
cols = [[0] * z + [1] * (16 - z) for z in (1, 1, 1, 5)]
out = column_major(columnsort(cols, check=False))
assert out != sorted(out)
with pytest.raises(ValueError):
columnsort(cols)
def test_random_large() -> None:
rng = random.Random(3)
for r, s in ((20, 4), (32, 4), (36, 4), (50, 5)):
for _ in range(100):
vals = [rng.randint(0, 40) for _ in range(r * s)]
cols = [vals[k * r : (k + 1) * r] for k in range(s)]
assert column_major(columnsort(cols)) == sorted(vals)
What the next level needs
- the tests did not run in this build