C++ STL Permutazione Prossimo con Combinazione

Question

so che posso usare std::next_permutation su alcuni contenitore contenente gli elementi [1, 2, 3] che genererebbe 6 permutazioni di questa sequenza. Quello che mi piacerebbe fare è dare qualche set [1, 2, 3, 4, 5, 6] generare tutte le permutazioni possibili di dimensione 3. Quindi per questo esempio, [4, 3, 2] sarebbe una delle permutazioni risultante da questo criterio. Sto cercando un modo STL di farlo (se possibile) piuttosto che scrivere la mia propria funzione di combinazioni. Qualche particolare implementazione STL di cui dovrei leggere?

Answer 1

Questo non è il più efficiente algoritmo di possibile, ma è facile. È necessario iniziare con gli elementi ordinati. Per ottenere la successiva k-permutazione, invertire gli ultimi elementi n-k e quindi provare a ottenere la permutazione successiva. I primi k elementi sono la successiva k-permutazione.

Answer 2

Non c'è attualmente (a partire dal 2016) nessuna funzione singola STD per farlo. Il più vicino quello che hai è la proposta http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

la funzione desiderata viene chiamata next_partial_permutation e si presenta come (da 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

Ecco un algoritmo scritto in Smalltalk.

L'idea dell'algoritmo consiste nel considerare l'ordine lessicografico delle matrici di lunghezza m con elementi tra 1 e n. Dati tali array, il metodo next sostituisce array con la sua successiva permutazione parziale nell'ordine indicato.

Ho creato una classe con tre variabili di istanza

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

il metodo di creazione dell'istanza m:n: funziona come segue

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

In questa classe il metodo next modifica il array in modo che ora mantieni la prossima permutazione.

Potrebbe essere la pena ricordare che l'algoritmo non è ricorsiva.

Il metodo next risposte con nil se e solo se array contiene l'ultima permutazione in ordine (vale a dire, array = (n, n-1, ...., n-m+1).

Per calcolare tutte le permutazioni iniziano con array = (1 ... m) e inviare next fino a quando la risposta è 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]] 

Dove

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