I want to create a function f that maps integer indexes to a unique permutation of a list L, no matter the language. A quite similar problem has been adressed there, the difference here is that we don't want duplicate permutations (example : [1,0,0] is not a valid permutation of [1,0,0], see the complete example below). As far as I know, this particular problem has yet not been addressed.

Here is an example. Consider the list:

L = [1,0,0,-1]

Then I would like the function to perform a mapping similar to the following:

f(0) = [1,0,0,-1]
f(1) = [0,1,0,-1]
f(2) = [0,0,1,-1]
f(3) = [1,0,-1,0]
f(4) = [0,1,-1,0]
f(5) = [0,0,-1,1]
f(6) = [1,-1,0,0]
f(7) = [0,-1,1,0]
f(8) = [0,-1,0,1]
f(9) = [-1,1,0,0]
f(10) = [-1,0,1,0]
f(11) = [-1,0,0,1]

The order does not matter, the important is that I get a bijective mapping from the set [0;11] to the unique permutations of L without any duplicata. I am looking for a generic solution, that could work for any list L, and moreover it should avoid storing all possible permutations as this can easily be unpraticable. Is there a way to do that ?

CodePudding user response：

A general algorithm for this would be as follows:

1. Convert the list into a set of unique items associated with the number of times each item appears in the list. For example: ["A","C","A","C","B","A"] → [["A",3], ["B",1], ["C",2]]
2. Set n to the number of items in the original list, and m to the number of items in the reduced set (in this case, n=6 and m=3), and let's supppose you want to generate the ith permutation of this list.
3. Create a new empty list
4. Until the length of this new list is equal to n:

1. Calculate x = i % m and add the xth item of the set of unique items to your list.
2. Set i to the integer part of i / m
3. Decrement the number of occurrences of this xth item. If it eaches zero, remove this item from the set and decrement m

5. The new list now contains the ith permutation

Optionally, you might want to make sure that i is in the range from 0 to one less than the total number of permutations, which is equal to n! divided by the factorials of every number of occurrences in the reduced set (6!/(3!1!2!) in the above example).