1

I have a list like this: a,b,c,d,e,f,g. And I want to calculate the permutation number 57 in a list of two elements ( in this case is f,g ). But I do not want to permute the list 57 times, I want a math formula able to calculate permutation number 57 in python.

I have tried this in python but it doesn't works and gives me the following result: ['a', 'b', 'e', 'd', 'f', 'c', 'g'], the correct result must be: ['f', 'g']

    import math

    def calculate_kth_permutation(lst, k):
        n = len(lst)
        if k >= math.factorial(n):
            raise ValueError("Index k is out of range.")

        result = []
        for i in range(n, 0, -1):
            fact = math.factorial(i - 1)
            quotient, k = divmod(k, fact)
            result.append(lst.pop(quotient))

        return result

    # Example usage:
    my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
    index = 56  # 0-based index for the 57th permutation
    permutation = calculate_kth_permutation(my_list, index)
    print(permutation)

Someone can help me find the correct formula?

Dave
  • 7,460
  • 3
  • 26
  • 39
V.Petretto
  • 319
  • 2
  • 8
  • 1
    Do the permutation IDs need to be assigned in lexicographic order? I.e., would a solution that gives each permutation a unique ID and lets you quickly go from ID to permutation & back be of interest if the IDs weren't in lexicographic order? – Dave Jul 25 '23 at 13:23
  • Yes it can be of interest. Thank you for the reply. – V.Petretto Jul 25 '23 at 13:27
  • 1
    Should this be closed as duplicate with this: https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others? You don't care about PHP, but neither do the algorithms mentioned in the answers to that question. – Dave Jul 25 '23 at 13:44
  • ok, yes I close it, thank you – V.Petretto Jul 25 '23 at 14:40

1 Answers1

2

Here's an algorithm to convert between permutations and ranks in linear time. However, the ranking it uses is not lexicographic. It's weird, but consistent. I'm going to give two functions, one that converts from a rank to a permutation, and one that does the inverse.

First, to unrank (go from rank to permutation)

Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

Next, to rank:

Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

The running time of both of these is O(n).

There's a nice, readable paper explaining why this works: Ranking & Unranking Permutations in Linear Time, by Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, 30 September 2001, Pages 281–284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

Note: This answer was originally posted here: Finding n-th permutation without computing others

Dave
  • 7,460
  • 3
  • 26
  • 39