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

Question

我需要高效从n计算长度k的下一个排列选择。维基百科列出 a greatalgorithm用于根据 n 个选项计算下一个长度 n 的排列。

我能想到的最好的事情是使用该算法(或 the Steinhaus–Johnson–Trotter algorithm )，然后只考虑列表的前 k 项，并在所有更改时再次迭代高于那个位置。

约束:

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

非约束:

• 不关心它是否就位
• 我不在乎它是按字典顺序还是任何顺序
• 我不太关心它计算下一个排列的效率如何，当然，在合理的范围内，它不能通过做一个给我下一个排列每次列出所有可能的。

Answer 1

你可以把这个问题分解成两部分:

1) 从大小为 n 的集合中找出大小为 k 的所有子集。

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

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

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。