Refactor permutation algorithms and random permutation generation

[sraaphorst]

Refactor the permutation implementation and related algorithms to clarify the distinction between abstract permutations, ordered representations, and random permutation generation.

The Permutation<A> type should continue to represent an abstract bijection on a finite set:

$$\sigma : A \to A.$$

A permutation does not inherently require an ordering on its domain. Operations such as composition, inversion, cycle decomposition, parity, exponentiation, and permutation order are defined for arbitrary finite sets.

Order-sensitive algorithms, including inversion count and Kendall tau distance, should continue to require an ordered domain explicitly at runtime or consume a separate ordering abstraction where appropriate.

1. Remove FiniteSet<A>.fisherYates

Remove the public extension:

fun <A> FiniteSet<A>.fisherYates(...)

Fisher–Yates is an implementation technique rather than a domain-level operation on finite sets. Exposing it as a FiniteSet extension also duplicates the behavior of randomPermutation.

Move the Fisher–Yates implementation into a private helper in PermutationAlgorithms.kt, or another suitable internal location.

For example:

private fun <A> MutableList<A>.shuffleInPlace(random: Random) {
    for (i in lastIndex downTo 1) {
        val j = random.nextInt(i + 1)
        val temporary = this[i]
        this[i] = this[j]
        this[j] = temporary
    }
}

The implementation may instead use the Kotlin standard-library shuffle operation if its behavior and reproducibility guarantees are appropriate for Kosmos.

2. Consolidate random permutation generation

Retain a single public operation for producing random permutations:

fun <A : Any> randomPermutation(
    domain: FiniteSet<A>,
    random: Random = Random.Default,
): Permutation<A>

A uniformly random permutation can be produced from either an ordered or unordered finite set. Any enumeration of the underlying elements may be shuffled uniformly, so an ordered domain is not mathematically required.

Suggested implementation:

fun <A : Any> randomPermutation(
    domain: FiniteSet<A>,
    random: Random = Random.Default,
): Permutation<A> {
    val shuffled = domain.toList().toMutableList()
    shuffled.shuffleInPlace(random)

    val mapping = domain
        .toList()
        .zip(shuffled)
        .toMap()

    return Permutation.of(domain, mapping)
}

The implementation should avoid independently calling domain.toList() if an unordered domain could return inconsistent enumerations during one invocation. Capture the enumeration once:

val elements = domain.toList()
val shuffled = elements.toMutableList()

Then build the mapping from elements.

3. Document seeded reproducibility

For an ordered domain, the same domain ordering and random seed should produce the same permutation, subject to the guarantees of the selected random-number generator.

For an unordered domain, the resulting permutation should still be uniformly distributed, but reproducibility may depend on the iteration order of the backing set.

Document this distinction:

Random generation is uniform for both ordered and unordered domains.
Seeded reproducibility is guaranteed only when the domain enumeration is stable.

Do not require callers to convert unordered sets to ordered sets merely to generate a random permutation. Such conversion may preserve an arbitrary backing-set iteration order and would not itself provide meaningful reproducibility.

4. Keep Permutation defined over FiniteSet

Do not change:

data class Permutation<A : Any>(
    override val domain: FiniteSet<A>,
    ...
)

to require:

FiniteSet.Ordered<A>

Most permutation operations are independent of any ordering on the domain.

Order-sensitive operations should enforce their own requirements. For example:

fun <A : Any> Permutation<A>.inversionCount(): Long {
    val orderedDomain = domain as? FiniteSet.Ordered<A>
        ?: throw IllegalArgumentException(
            "Inversion count requires an ordered permutation domain."
        )

    // ...
}

5. Clarify ordered representation versus mathematical order

Review permutation algorithms for places where domain.toList() or domain.order is used.

Each use should be classified as one of:

• arbitrary enumeration used only to traverse the finite set;
• stable enumeration required for reproducible behavior;
• positional ordering required by one-line permutation notation;
• mathematical ordering required by an algorithm.

Algorithms in the latter two categories should require either:

FiniteSet.Ordered<A>

or an appropriate ordering abstraction such as:

TotalOrder<A>

depending on whether the algorithm needs a concrete enumeration or only pairwise comparison.

Do not treat an unordered set’s backing iteration order as a mathematical order.

6. Consider an explicit one-line representation

Consider, but do not necessarily implement as part of this issue, an explicit conversion from an abstract permutation to its one-line representation relative to an ordered domain:

fun <A : Any> Permutation<A>.toOneLineNotation(): List<A>

This operation would require the permutation domain to be ordered and would return:

domain.order.map(this::apply)

Alternatively:

fun <A : Any> Permutation<A>.toOneLineNotation(
    order: FiniteSet.Ordered<A>
): List<A>

could support an externally supplied reference order.

This would centralize the interpretation currently reconstructed by inversion-counting and ranking algorithms.

7. Review invoke(FiniteSet<A>)

The current operation:

operator fun invoke(set: FiniteSet<A>): FiniteSet<A> =
    FiniteSet.ordered(set.map(this::apply))

should be reviewed.

Since FiniteSet.map already preserves whether the receiver is ordered or unordered, wrapping its result in FiniteSet.ordered may unnecessarily convert unordered sets into ordered sets.

It may be sufficient to write:

operator fun invoke(set: FiniteSet<A>): FiniteSet<A> =
    set.map(this::apply)

The operation should also verify that every element of set belongs to the permutation domain, unless that guarantee is already provided elsewhere.

8. Add or update tests

Add tests covering:

• randomPermutation over an ordered domain;
• randomPermutation over an unordered domain;
• preservation of the original domain;
• bijectivity of generated mappings;
• deterministic output for a fixed ordered domain and seed;
• approximate uniformity for small domains;
• removal of the public fisherYates extension;
• preservation of ordered versus unordered set type when applying a permutation to a finite set;
• rejection of elements outside the permutation domain where applicable.

For uniformity testing, use a small domain such as three elements and verify that all six permutations occur with approximately equal frequency over a sufficiently large deterministic sample. The tolerance should be wide enough to avoid flaky probabilistic tests.