2

Is there an efficient algorithm to generate a permutation from one index provided? The permutations do not need to have any specific ordering and it just needs to return every permutation once per every possible index. The set I wish to permute is all integers from 0~255.

pythonian 23
  • 365
  • 4
  • 16
  • 1
    If I understand this correctly, in your case, the permutations coincide with the indices themselves. Why not return the index? – user1984 Mar 14 '22 at 15:20
  • Note that log2(256!) = 1684 bits (around) = 210.5 bytes. So, the index would be about as long as the permutation array itsel (256 bytes). – Damien Mar 14 '22 at 15:45
  • 1
    Could you provide an example of what you are looking for with sample input and output? Currently, it is very unclear. – RBarryYoung Mar 14 '22 at 16:17
  • Related: [Finding n-th permutation without computing others](https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others); [Given a list of elements in lexicographical order (i.e. ('a', 'b', 'c', 'd')), find the nth permutation](https://stackoverflow.com/questions/6784148/given-a-list-of-elements-in-lexicographical-order-i-e-a-b-c-d-f/6784359#6784359) – Stef Mar 14 '22 at 18:07

2 Answers2

3

If I understand the question correctly, the problem is as follows: You are given two integers n and k, and you want to find the kth permutation of n integers. You don't care about it being the kth lexicographical permutation, but it's just easier to be lexicographical so let's stick with that.

This is not too bad to compute. The base permutation is 1,2,3,4...n. This is the k=0 case. Consider what happens if you were to swap the 1 and 2: by moving the 1, you are passing up every single permutation where 1 goes first, and there are (n-1)! of those (since you could have permuted 2,3,4..n if you fixed the 1 in place). Thus, the algorithm is as follows:

for i from 1 to n:
    j = k / (n-i)! // integer division, so rounded down
    k -= j * (n-i)!
    place down the jth unplaced number

This will iteratively produce the kth lexicographical permutation, since it repeatedly solves a sub-problem with a smaller set of numbers to place, and decrementing k along the way.

Jacob Steinebronn
  • 833
  • 3
  • 12
1

There is an implementation in python in module more-itertools: nth_permutation.

Here is an implementation, adapted from the code of more_itertools.nth_permutation:

from sympy import factorial

def nth_permutation(iterable, index):
    pool = list(iterable)
    n = len(pool)
    c = factorial(n)
    index = index % c
    result = [0] * n
    q = index
    for d in range(1, n + 1):
        q, i = divmod(q, d)
        if 0 <= n - d < n:
            result[n - d] = i
        if q == 0:
            break
    return tuple(map(pool.pop, result))

print( nth_permutation(range(6), 360) )
# (3, 0, 1, 2, 4, 5)
Stef
  • 13,242
  • 2
  • 17
  • 28
  • @KellyBundy I deleted it because the OP actually rearranged the data in a different way than what I thought. I thought they were grouping the elements so that all duplicates are close together. But actually they're putting one occurrence of every element first, then grouping the remaining duplicates. I guess we could do `uniques = set(l); return list(chain(uniques, (Counter(l) - Counter(uniques)).elements())` but I'm not sure how helpful that would be to the OP. – Stef Mar 21 '22 at 17:54
  • Yes, I find that difficulty of communication frustrating too. I guess it's not so surprising that using `set` adds overhead? – Stef Mar 22 '22 at 09:33
  • 1
    The set takes some time, yes, but the biggest part appears to be the Counter subtraction: [benchmark of parts](https://ideone.com/Roqg9q). I've put a chat room link on my profile now, maybe that helps, and maybe if enough people do that, SO will offer a standardized lightweight functionality :-) – Kelly Bundy Mar 22 '22 at 14:34