flix

0.75.3

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

def binomial(n: Int32, k: Int32): Int32§ Source

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.

def combRank(subset: Vector[Int32]): Int32§ Source

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.

def combUnrank(r: Int32, k: Int32): Vector[Int32]§ Source

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.

def multisetRank(labels: Vector[Int32], k: Int32, ntypes: Int32): BigInt§ Source

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.

def multisetUnrank(value: BigInt, n: Int32, k: Int32, ntypes: Int32): Vector[Int32]§ Source

The inverse of multisetRank.

def permParity(p: Vector[Int32]): Int32§ Source

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.

def permRank(p: Vector[Int32]): BigInt§ Source

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.

def permRankWithParity(p: Vector[Int32], parity: Int32): BigInt§ Source

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.

def permUnrank(r: BigInt, n: Int32): Vector[Int32]§ Source

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.

def permUnrankWithParity(rank: BigInt, n: Int32, parity: Int32): Vector[Int32]§ Source

Recover the rank-th permutation of n elements with parity.

rank must be below n! / 2; state decoding establishes that bound before calling this primitive.