Orbit64.Rank
Bijective rank/unrank primitives.
Every function here maps a combinatorial object onto a contiguous range of integers starting at zero, and back. The codec is built entirely from these three families, so the total size of a cube encoding is just the product of the ranges -- no bits are lost to alignment inside a coordinate.
Definitions
Binomial coefficient, saturating at Int32.maxValue. Returns 0 when
k is out of range.
The result stays in Int32 because that is what the ranks it feeds are:
the codec only ever asks for C(24, 4) and smaller, so the largest it
really produces is 10626. The running product is Int64 all the same,
because this is public and a caller is not bound by what the codec asks.
Overflowing to a negative number would be worse than saying "very
large" -- combUnrank searches upwards until this exceeds a rank, and a
negative never does.
C(n, k) = C(n, n - k), and the smaller of the two is taken. That is
not only cheaper: it keeps the running product monotone, so stopping
early at the cap cannot skip past a final value that would have fitted.
Colexicographic rank of a k-subset of 0..n-1, in [0, C(n, k)).
The combinatorial number system: rank = sum C(c_i, i+1) over the
sorted elements. This is Kociemba's UDSlice coordinate generalized.
The inverse of combRank.
r is expected below C(n, k) for the n the caller has in mind --
which is not a number this function is given, so it cannot check it. A
rank from outside that range still returns, and still returns k
ascending values; they are simply not a subset of anything the caller
asked about.
Rank an arrangement of ntypes labels over n slots, k copies of
each, in [0, n! / (k!)^ntypes).
Decomposed into a chain of combination ranks -- pick the slots holding
label 0, then label 1 from what remains, and so on. The last label is
forced, so it contributes nothing. Every intermediate radix stays small
enough for Int32, which is why center orbits need no big integers
until the final assembly.
The inverse of multisetRank.
The inversion parity of p: 0 for even and 1 for odd.
This is kept beside permutation ranking because a cube's corner and
midge permutations must have the same parity. It deliberately says
nothing about whether p is a permutation; callers validate that
separately before using a rank.
Lexicographic (Lehmer) rank of the permutation p of 0..n-1.
Runs in O(n^2): for each element it counts how many smaller elements
follow it. At n = 24 that is 276 comparisons, which measured cheaper
than maintaining a Fenwick tree.
Rank a permutation known to have parity into the contiguous range
[0, n! / 2).
The first n - 2 Lehmer digits select every element but the final two.
Their order is then forced by parity, so it costs no digit. This is a
bijection for either parity class and is the compact coordinate used by
odd-cube state packing.
The inverse of permRank: the permutation of 0..n-1 with rank r.
Dearer than permRank, despite extracting its digits in a linear pass:
removing the chosen element rebuilds avail at every digit, so the fold
is quadratic in allocation. permRank's quadratic inversion count
allocates nothing at all, and measures about four times cheaper at
n = 24.