Get permutation with specified degree by index number

Question

I've been working on this for hours but couldn't figure it out.

Define a permutation's degree to be the minimum number of transpositions that need to be composed to create it. So a the degree of (0, 1, 2, 3) is 0, the degree of (0, 1, 3, 2) is 1, the degree of (1, 0, 3, 2) is 2, etc.

Look at the space Snd as the space of all permutations of a sequence of length n that have degree d.

I want two algorithms. One that takes a permutation in that space and assigns it an index number, and another that takes an index number of an item in Snd and retrieves its permutation. The index numbers should obviously be successive (i.e. in the range 0 to len(Snd)-1, with each permutation having a distinct index number.)

I'd like this implemented in O(sane); which means that if you're asking for permutation number 17, the algorithm shouldn't go over all the permutations between 0 and 16 to retrieve your permutation.

Any idea how to solve this?

(If you're going to include code, I prefer Python, thank you.)

Update:

I want a solution in which

1. The permutations are ordered according to their lexicographic order (and not by manually ordering them, but by an efficient algorithm that gives them with lexicographic order to begin with) and
2. I want the algorithm to accept a sequence of different degrees as well, so I could say "I want permutation number 78 out of all permutations of degrees 1, 3 or 4 out of the permutation space of range(5)". (Basically the function would take a tuple of degrees.) This'll also affect the reverse function that calculates index from permutation; based on the set of degrees, the index would be different.

I've tried solving this for the last two days and I was not successful. If you could provide Python code, that'd be best.

Answer 1

The permutations of length n and degree d are exactly those that can be written as a composition of k = n - d cycles that partition the n elements. The number of such permutations is given by the Stirling numbers of the first kind, written n atop k in square brackets.

Stirling numbers of the first kind satisfy a recurrence relation

[n]           [n - 1]   [n - 1]
[ ] = (n - 1) [     ] + [     ]
[k]           [  k  ]   [k - 1],

which means, intuitively, the number of ways to partition n elements into k cycles is to partition n - 1 non-maximum elements into k cycles and splice in the maximum element in one of n - 1 ways, or put the maximum element in its own cycle and partition the n - 1 non-maximum elements into k - 1 cycles. Working from a table of recurrence values, it's possible to trace the decisions down the line.

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    if (n, k) not in memostirling1:
        if not (1 <= k <= n): return 0
        memostirling1[(n, k)] = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
    return memostirling1[(n, k)]

def unrank(n, d, i):
    k = n - d
    assert 0 <= i <= stirling1(n, k)
    if d == 0:
        return list(range(n))
    threshold = stirling1(n - 1, k - 1)
    if i < threshold:
        perm = unrank(n - 1, d, i)
        perm.append(n - 1)
    else:
        (q, r) = divmod(i - threshold, stirling1(n - 1, k))
        perm = unrank(n - 1, d - 1, r)
        perm.append(perm[q])
        perm[q] = n - 1
    return perm