从n个选择中有效地计算长度k的下一个排列

Question

我需要从 选择中有效地计算下一个长度的排列.维基百科列出了一个很好的算法 ,可以根据选择计算下一个长度排列.knnn

我能想到的最好的事情是使用该算法(或Steinhaus-Johnson-Trotter算法),然后只考虑k列表的第一项,并在变化全部高于该位置时再次迭代.

约束:

• 算法必须计算下一个排列,只给出当前排列.如果需要生成所有排列的列表,则会占用太多内存.
• 它必须能够计算只有长度k的排列n(这是其他算法失败的地方)

非约束:

• 不在乎它是否就地
• 我不在乎它是否符合排序规则或任何订单
• 我不太关心它如何有效地计算下一个排列,理所当然,它不能通过每次列出所有可能的排列来给我下一个排列.

Answer 1

您可以将这个问题分为两部分：

k1)从一组 size 中查找 size 的所有子集n。

2) 对于每个这样的子集，找到大小为 的子集的所有排列k。

引用的维基百科文章提供了第 2 部分的算法，因此这里不再重复。第 1 部分的算法非常相似。为了简单起见，我将其描述为“查找k整数大小的所有子集” [0...n-1]。

1）从子集开始[0...k-1]

2) 给定一个子集，得到下一个子集S：

2a) 找到最小的j使得j ∈ S ∧ j+1 ∉ S。如果j == n-1，则没有下一个子集；我们完成了。

2b) 小于的元素j形成一个序列i...j-1（因为如果缺少任何一个值，j则不会是最小的）。如果i不为 0，则将这些元素替换为i-i...j-i-1。将 元素 替换j为 元素j+1。