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?C++ STL Permutazione Prossimo con Combinazione
risposta
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.
Sembra ovvio ora che lo dici, +1. – Barry
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);
}
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
- 1. Come combinazione/permutazione in rubino?
- 2. Come calcolare combinazione e permutazione in R?
- 3. Java Permutazione e combinazione dei flag booleani
- 4. Implementazione C/C++ prossimo più prossimo a K
- 5. Espressioni regolari in C++ STL
- 6. C# Permutazione di un array di arraylists?
- 7. C equivalente di C++ STL
- 8. C errore ++ STL rimuovere
- 9. C++ stl convolution
- 10. Problem solving in C++ con STL
- 11. Utilizzo di STL con Android NDK C++
- 12. stl priority_queue di C++ con struct
- 13. C++ UNICODE e STL
- 14. RAII e C++ STL
- 15. Combinazione di C++ e C#
- 16. combinazione C# stack queue
- 17. Parsing interi con STL
- 18. Allocatori conformi a STL C++
- 19. Stesse permutazioni in due array utilizzando next_permutation() stl in C++
- 20. Combinazione reale in Groovy
- 21. Ordinamento di una permutazione con costo minimo
- 22. debug di codice C++ con modelli e STL con gdb
- 23. C++ STL pop_heap non funziona
- 24. Padding stl stringhe in C++
- 25. STL C++, iteratori costanti, find()
- 26. Permutazione di un elenco - Haskell
- 27. Stack STL con 2 parametri
- 28. Come generare una permutazione?
- 29. permutazione di matrice
- 30. permutazione di un vettore
http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n –
http://stackoverflow.com/questions/9430568/generating-combinations-in -c –
http://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c –