Reply To: Programming

[upsidedown]

My solution to: #98031

The first thing I noticed is that the first symbol is easy to work out. In madness’ example, we have:

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

… so the first digit just increases sequentially. The gap between increments of the first digit is always the same, and equals the number of permutations of the remaining digits (n - 1)!.

Let’s normalise permutation symbols to be s ∈ { 0, ..., n - 1 }; and permutation numbers to be p ∈ { 0, ..., n! - 1 }. We can then write an expression for the first symbol as:

first p n = int(p / n!)

Now we know the first symbol, we’re effectively left with the same problem, but with n - 1 symbols from the set { 0, ..., n - 1 } - { the first symbol } and a permutation sequence number p % (n - 1)!. We can therefore just map the symbols into { 0, ..., n - 2 } and reuse the same first function. Python:

def permutation(p, n):
    permutation = []
    symbols = list(range(n))

    while len(permutation) < n:
        f = factorial(n - len(permutation) - 1)
        symbol = symbols[p // f]
        symbols.remove(symbol)
        permutation.append(symbol)
        p %= f

    return permutation