1

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 ?

Asimonu
  • 100
  • 7
  • Create all permutations of a list made of unique elements of L, and insert into it the "duplicates" in all possible arrangements? – Jean-Baptiste Yunès May 25 '22 at 10:14
  • If the list had no duplicates, then this is a well-known problem and has implementations in pseudo-code on wikipedia and in libraries in a few programming languages, for instance [in python: more_itertools.nth_permutation](https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.nth_permutation) and its inverse function [more_itertools.permutation_index](https://more-itertools.readthedocs.io/en/stable/api.html#more_itertools.permutation_index). If the list has duplicates, it's a bit harder but there should be implementations out there. – Stef May 25 '22 at 11:13
  • This question appears to be asking the same thing, but is specific to mathematica: [mathematica: What is the fastest way to get the nth distinct permutation of a list](https://mathematica.stackexchange.com/questions/77443/what-is-the-fastest-way-to-get-the-nth-distinct-permutation-of-a-list) – Stef May 25 '22 at 11:21
  • 1
    And this appears to be a perfect duplicate: [Ranking and unranking of permutations with duplicates](https://stackoverflow.com/questions/6884708/ranking-and-unranking-of-permutations-with-duplicates) – Stef May 25 '22 at 11:24
  • @Stef good one indeed, I didn't see this question. However I think the answers of this topic don't take into account the duplicata, or need to store all the permutations in some list which can easily be unpraticable. I am going to edit a bit my question to take this last requirement into account – Asimonu May 25 '22 at 12:06
  • [This answer](https://stackoverflow.com/a/6885929/2144669) from the question that Stef linked is quite cryptic but does seem to handle duplicates properly. – David Eisenstat May 25 '22 at 12:20
  • You may want to look up *Lehmer codes*, a bijective mapping between the numbers 0, 1, …, n! - 1 and permutations of an n-element set. – templatetypedef May 25 '22 at 14:16

1 Answers1

1

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
  1. 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).

r3mainer
  • 23,981
  • 3
  • 51
  • 88