C++ STL Nächste Permutation mit Kombination

Question

Ich weiß, dass ich std::next_permutation auf einige Container verwenden kann, die die Elemente [1, 2, 3] enthalten, die 6 Permutationen dieser Sequenz erzeugen würden. Was ich gerne machen würde, ist ein Satz [1, 2, 3, 4, 5, 6], der alle möglichen Permutationen der Größe 3 erzeugt. Für dieses Beispiel wäre also [4, 3, 2] eine der Permutationen, die sich aus diesem Kriterium ergeben. Ich suche nach einer STL-Methode (wenn möglich), anstatt meine eigene Kombinationsfunktion zu schreiben. Irgendeine bestimmte STL-Implementierung, über die ich lesen sollte?

Answer 1

Dies ist nicht der effizienteste mögliche Algorithmus, aber es ist einfach. Sie müssen mit den sortierten Elementen beginnen. Um die nächste k-Permutation zu erhalten, kehren Sie die letzten n-k Elemente um und versuchen Sie dann, die nächste Permutation zu erhalten. Die ersten k Elemente sind die nächste k-Permutation.

Answer 2

Zur Zeit gibt es (Stand 2016) keine einzige STD-Funktion. Die nächstgelegene Sie haben, ist der Vorschlag von http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

Die Funktion, die Sie next_partial_permutation und sieht aus wie (von N2639) aufgerufen werden soll:

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

Hier ist ein Algorithmus geschrieben in Smalltalk.

Die Idee des Algorithmus besteht darin, die lexikografische Reihenfolge von Arrays der Länge m mit Elementen zwischen 1 und n zu berücksichtigen. Bei einem solchen array ersetzt das Verfahren nextarray durch seine nächste partielle Permutation in dieser Reihenfolge.

Ich habe

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

Die Instanz-Erzeugungsverfahren eine Klasse mit drei Instanzvariablen erstellt m:n: wie funktioniert In dieser Klasse

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

folgt das Verfahren next so die array modifiziert, dass es wird jetzt halte die nächste Permutation.

Es ist erwähnenswert, dass der Algorithmus nicht rekursiv ist.

Verfahren next Antworten mit nil iff array enthält die letzte Permutation in der Reihenfolge (dh array = (n, n-1, ...., n-m+1).

alle Permutationen mit array = (1 ... m) und senden next, bis die Antwort nil.

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]] 

ist beginnen zu berechnen

Wo

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