将整数映射到具有重复且没有高存储空间的唯一排列

Question

我想创建一个函数 f，将整数索引映射到列表 L 的唯一排列，无论使用何种语言。一个非常相似的问题已经被解决 there，这里的区别是我们不想要重复的排列（例如：[1,0,0] 不是 [1,0,0] 的有效排列，见下面的完整示例）。据我所知，这个特殊问题还没有得到解决。

这是一个例子。考虑列表：

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

然后我希望函数执行类似于以下的映射：

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]

顺序无关紧要，重要的是我得到了从集合 [0;11] 到 L 的唯一排列的双射映射，没有任何重复项。我正在寻找一个通用的解决方案，它可以适用于任何列表 L，而且它应该避免存储所有可能的排列，因为这很容易不可行。有办法吗？

Answer 1

一般算法如下：

将列表转换为一组与每个项目在列表中出现的次数相关联的唯一项目。例如：["A","C","A","C","B","A"] → [["A",3], ["B",1], ["C",2]]
将n设置为原始列表中的项目数，将m设置为缩减集中的项目数（在本例中，n=6和m=3)，假设您想生成此列表的第 i 个排列。
创建一个新的空列表
直到这个新列表的长度等于n:

Calculate x = i % m and add the xth item of the set of unique items to your list.

Set i to the integer part of i / m

Decrement the number of occurrences of this xth item. If it eaches zero, remove this item from the set and decrement m

新列表现在包含第 i 个排列

可选地，您可能希望确保 i 在 0 到比排列总数少一的范围内，它等于 n！除以缩减集中每个出现次数的阶乘（上例中为 6!/(3!1!2!)）。

将整数映射到具有重复且没有高存储空间的唯一排列

Map an integer to a unique permutation with duplicate and without high storage

algorithm

permutation