Get permutation with specified degree by index number

algorithm, combinatorics, permutation, python, time-complexity

Solution

This answer is less elegant/efficient than my other one, but it describes a polynomial-time algorithm that copes with the additional constraints on the ordering of permutations. I'm going to describe a subroutine that, given a prefix of an n-element permutation and a set of degrees, counts how many permutations have that prefix and a degree belonging to the set. Given this subroutine, we can do an n-ary search for the permutation of a specified rank in the specified subset, extending the known prefix one element at a time.

We can visualize an n-element permutation p as an n-vertex, n-arc directed graph where, for each vertex v, there is an arc from v to p(v). This digraph consists of a collection of vertex-disjoint cycles. For example, the permutation 31024 looks like

 _______
/       \
\->2->0->3
 __     __
/  |   /  |
1<-/   4<-/ .

Given a prefix of a permutation, we can visualize the subgraph corresponding to that prefix, which will be a collection of vertex-disjoint paths and cycles. For example, the prefix 310 looks like

2->0->3
 __
/  |
1<-/ .

I'm going to describe a bijection between (1) extensions of this prefix that are permutations and (2) complete permutations on a related set of elements. This bijection preserves up to a constant term the number of cycles (which is the number of elements minus the degree). The constant term is the number of cycles in the prefix.

The permutations mentioned in (2) are on the following set of elements. Start with the original set, delete all elements involved in cycles that are complete in the prefix, and introduce a new element for each path. For example, if the prefix is 310, then we delete the complete cycle 1 and introduce a new element A for the path 2->0->3, resulting in the set {4, A}. Now, given a permutation in set (1), we obtain a permutation in set (2) by deleting the known cycles and replacing each path by its new element. For example, the permutation 31024 corresponds to the permutation 4->4, A->A, and the permutation 31042 corresponds to the permutation 4->A, A->4. I claim (1) that this map is a bijection and (2) that it preserves degrees as described before.

The definition, more or less, of the (n,k)-th Stirling number of the first kind, written

[n]
[ ]
[k]

(ASCII art square brackets), is the number of n-element permutations of degree n - k. To compute the number of extensions of an r-element prefix of an n-element permutation, count c, the number of complete cycles in the prefix. Sum, for each degree d in the specified set, the Stirling number

[  n - r  ]
[         ]
[n - d - c]

of the first kind, taking the terms with "impossible" indices to be zero (some analytically motivated definitions of the Stirling numbers are nonzero in unexpected places).

To get a rank from a permutation, we do n-ary search again, except this time, we use the permutation rather than the rank to guide the search.

Here's some Python code for both (including a test function).

import itertools

memostirling1 = {(0, 0): 1}
def stirling1(n, k):
    ans = memostirling1.get((n, k))
    if ans is None:
        if not 1 <= k <= n: return 0
        ans = (n - 1) * stirling1(n - 1, k) + stirling1(n - 1, k - 1)
        memostirling1[(n, k)] = ans
    return ans

def cyclecount(prefix):
    c = 0
    visited = [False] * len(prefix)
    for (i, j) in enumerate(prefix):
        while j < len(prefix) and not visited[j]:
            visited[j] = True
            if j == i:
                c += 1
                break
            j = prefix[j]
    return c

def extcount(n, dset, prefix):
    c = cyclecount(prefix)
    return sum(stirling1(n - len(prefix), n - d - c) for d in dset)

def unrank(n, dset, rnk):
    assert rnk >= 0
    choices = set(range(n))
    prefix = []
    while choices:
        for i in sorted(choices):
            prefix.append(i)
            count = extcount(n, dset, prefix)
            if rnk < count:
                choices.remove(i)
                break
            del prefix[-1]
            rnk -= count
        else:
            assert False
    return tuple(prefix)

def rank(n, dset, perm):
    assert n == len(perm)
    rnk = 0
    prefix = []
    choices = set(range(n))
    for j in perm:
        choices.remove(j)
        for i in sorted(choices):
            if i < j:
                prefix.append(i)
                rnk += extcount(n, dset, prefix)
                del prefix[-1]
        prefix.append(j)
    return rnk

def degree(perm):
    return len(perm) - cyclecount(perm)

def test(n, dset):
    for (rnk, perm) in enumerate(perm for perm in itertools.permutations(range(n)) if degree(perm) in dset):
        assert unrank(n, dset, rnk) == perm
        assert rank(n, dset, perm) == rnk

test(7, {2, 3, 5})

Problem

Original source

Related problems

• Generate sample of 1,000,000 random permutations
• Generalising a "next permutation" function