What you are looking is called unrank
in combinatorial algorithm. Consider the list of the element of a set S in a fixed order, unrank_S(i)
returns the i
-th element of the list without computing the list. So your S
here is Perm(n, k)
: the list of all k
-permutation of a set of size n
. As you know the size of this set is n!/k!
. One way to do that is to use Factoradic numbers
Here is an unrank algorithm in python:
def factorial(n):
if n == 0: return 1
return n*factorial(n-1)
def unrank(S, k, i):
S = list(S) # make a copy to avoid destroying the list
n = len(S)
nb = factorial(n) // factorial(n-k)
if i >= nb:
raise IndexError
res = []
while k > 0:
nb = nb // n
pos = i // nb # the factoradic digits
i = i % nb # the remaining digits
res.append(S[pos])
del S[pos]
k = k-1
n = n-1
return res
Then
[unrank(range(5), 2, i) for i in range(20)]
[[0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 3], [1, 4], [2, 0], [2, 1], [2, 3], [2, 4], [3, 0], [3, 1], [3, 2], [3, 4], [4, 0], [4, 1], [4, 2], [4, 3]]
and
unrank(list('ABCDEFGHJKLMNPQRSTUVWXYZ23456789'),6, 128347238)\
['G', 'L', 'E', 'H', 'T', 'R']
Of course you might want to compute factorial using a better method or even to cache it in a pre-computed array to avoid recomputing it.