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

Question

我需要高效地计算长度为k的下一个排列，选项有n个。维基百科列出了一个很好的算法来计算从n个选项中计算长度为n的下一个排列。最好的方法是使用该算法（或 Steinhaus-Johnson-Trotter算法），然后只考虑列表的前k项，每当更改都在该位置以上时再次迭代。

约束条件： - 该算法必须仅通过当前排列计算下一个排列。如果需要生成所有排列的列表，它将占用太多内存。 - 它必须能够计算长度为k的n的排列（这是另一种算法失败的地方）

非约束条件：

• 我不在意是否就地排序
• 我不在意它是否按字典顺序排列，或者按任何顺序排列
• 当然，我不会太在意它如何高效地计算下一个排列，但是要合理，不能每次都生成所有可能的排列来给我下一个排列。

- aaronstacy

---

我非常确定你会在Python itertools模块的代码中找到答案，看一下即可。 - YXD

是的，这是在Mac OS X上的一个*.so文件，所以我太懒了，没有去找源代码。我想我应该停止偷懒，去找一下源代码。 - aaronstacy

http://hg.python.org/releasing/2.7.3/file/7bb96963d067/Modules/itertoolsmodule.c#l2497 - Danica

http://docs.python.org/2/library/itertools.html#itertools.permutations - YXD

Answer 1

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

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

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

参考维基百科文章提供了第二部分的算法，因此我不会在此重复。第一部分的算法非常相似。为简单起见，我将其描述为“查找整数[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+1 替换元素 j。

- rici