C++ STL次の組み合わせによる置換

Question

std::next_permutationは、このシーケンスの6つの順列を生成する要素[1, 2, 3]を含む一部のコンテナで使用できます。私がしたいことは、いくつかのセット[1, 2, 3, 4, 5, 6]がサイズ3のすべての可能な順列を生成することを示しています。この例では、[4, 3, 2]はこの基準の結果である置換の1つになります。私は自分の組み合わせの関数を記述するのではなく、これを行うSTLの方法（可能な場合）を探しています。私が読んでいなければならない特定のSTL実装

Answer 1

これは最も効率的なアルゴリズムではありませんが、簡単です。ソートされた要素から始めなければなりません。次のk-permutationを得るには、最後のn-k個の要素を逆にして、次の順列を取得しようとします。最初のk個の要素は次のk個の置換である。

Answer 2

現在、（2016年時点で）これを行う単一のSTD機能はありません。あなたが持っている最も近いあなたが望むhttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

機能からの提案がnext_partial_permutationと呼ばれ、（N2639から）のように見えるされている。ここで

template <class BidirectionalIterator > 
bool next_partial_permutation(
    BidirectionalIterator first , 
    BidirectionalIterator middle , 
    BidirectionalIterator last) 
{ 
    std::reverse(middle , last); 
    return std::next_permutation(first , last); 
} 

Answer 3

はSmalltalkの中で書かれたアルゴリズムです。

アルゴリズムの考え方は、長さがmで、要素が1とnの間である配列の辞書順を考慮することです。そのようなarrayが与えられた場合、方法nextは、arrayを、その次の部分置換と置き換えます。

私は3つのインスタンス変数

array  the current permutation of length m 
m   the size of array 
complement the SortedCollection of integers not in array 

で、このクラスで

m: length n: limit 
    m := length. 
    array := (1 to: m) asArray. 
    complement := (m + 1 to: limit) asSortedCollection 

を次のように方法nextがarrayそれは今なるように修正作品m:n:インスタンス作成メソッドをクラスを作成しました次の順列を保つ。

アルゴリズムが再帰的ではないことに言及する価値があります。

方法array IFF nilとnext答えは順序（すなわち、array = (n, n-1, ...., n-m+1)で最後の順列が含まれています。

array = (1 ... m)で始まり、答えがnilなるまでnextを送信するすべての順列を計算するために。

next 
    | index max h a c | 
    index := self lastDecreasingIndex. 
    max := complement max. 
    h := (index to: m) findLast: [:i | (array at: i) < max] ifAbsent: nil. 
    h isNil 
    ifTrue: [ 
     index = 1 ifTrue: [^nil]. 
     a := array at: index - 1. 
     index to: m do: [:i | complement add: (array at: i)]. 
     c := complement detect: [:cj | a < cj]. 
     array at: index - 1 put: c. 
     complement remove: c; add: a. 
     index to: m do: [:i | array at: i put: complement removeFirst]] 
    ifFalse: [ 
     h := h + index - 1. 
     a := array at: h. 
     c := complement detect: [:ci | a < ci]. 
     array at: h put: c. 
     complement remove: c; add: a. 
     h + 1 to: m do: [:i | complement add: (array at: i)]. 
     h + 1 to: m do: [:i | array at: i put: complement removeFirst]] 

lastDecreasingIndex 
    | index | 
    index := m. 
    [(array at: index - 1) > (array at: index)] whileTrue: [ 
    index := index - 1. 
    index = 1 ifTrue: [^1]]. 
    ^index