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

この問題は、次の2つの部分に分けることができます。

k1）サイズのセットからサイズのすべてのサブセットを検索しますn。

2）そのようなサブセットごとに、サイズのサブセットのすべての順列を見つけますk。

参照されているウィキペディアの記事はパート2のアルゴリズムを提供しているので、ここでは繰り返しません。パート1のアルゴリズムは非常に似ています。k簡単にするために、「整数のサイズのすべてのサブセットを検索する」について説明します[0...n-1]。

1）サブセットから始めます[0...k-1]

2）サブセットを指定して、次のサブセットを取得するにはS：

j2a）次のような最小のものを見つけますj ∈ S ∧ j+1 ∉ S。の場合j == n-1、次のサブセットはありません。終わったね。

j2b）シーケンスを形成する要素よりも少ない要素i...j-1（これらの値のいずれかが欠落している場合、j最小ではないため）。が0でない場合iは、これらの要素を。に置き換えますi-i...j-i-1。j要素を要素に置き換えますj+1。

于 2013-02-02T19:53:29.597 に答える