5

I need to efficiently calculate the next permutation of length k from n choices. Wikipedia lists a great algorithm for computing the next permutation of length n from n choices.

The best thing I can come up with is using that algorithm (or the Steinhaus–Johnson–Trotter algorithm), and then just only considering the first k items of the list, and iterating again whenever the changes are all above that position.

Constraints:

  • The algorithm must calculate the next permutation given nothing more than the current permutation. If it needs to generate a list of all permutations, it will take up too much memory.
  • It must be able to compute a permutation of only length k of n (this is where the other algorithm fails

Non-constraints:

  • Don't care if it's in-place or not
  • I don't care if it's in lexographical order, or any order for that matter
  • I don't care too much how efficiently it computes the next permutation, within reason of course, it can't give me the next permutation by making a list of all possible ones each time.
4

1 回答 1

1

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

1)k从一组 size中找到所有 size 的子集n。

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

引用的 Wikipedia 文章提供了第 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。

于 2013-02-02T19:53:29.597 回答