Ho una lista di N elementi e mi chiedo come posso scorrere l'elenco per ottenere ogni combinazione. Non ci sono i doppi, quindi ho bisogno di prendere tutto N! ordinamenti. La memoria extra non è un problema, sto cercando di pensare all'algoritmo più semplice ma ho dei problemi.Algoritmo C++ per N! ordini
risposta
Buona chiamata (per così dire). Sebbene sia giusto, l'OP ha chiesto l'algoritmo * più semplice *. –
C++ STL ha next_permutation per questo scopo.
Ampliando le risposte degli altri, ecco un esempio di std :: next_permutation adattato da cplusplus.com
#include <iostream>
#include <algorithm>
using namespace std;
void outputArray(int* array, int size)
{
for (int i = 0; i < size; ++i) { cout << array[i] << " "; }
}
int main()
{
int myints[] = { 1, 2, 3, 4, 5 };
const int size = sizeof(myints);
cout << "The 5! possible permutations with 5 elements:\n";
sort (myints, myints + size);
bool hasMorePermutations = true;
do
{
outputArray(myints, size);
hasMorePermutations = next_permutation(myints, myints + size);
}
while (hasMorePermutations);
return 0;
}
+1 per fornire un esempio. –
Non sembra esserci alcun punto nella variabile 'bool'. Puoi semplicemente 'do {...} while (std :: next_permutation (...));' –
@Charles: È vero, potrei farlo. Per motivi di insegnamento ho estratto la next_permutation poiché quello era il focus del codice. – Bill
semplice algoritmo utilizzando la ricorsione:
pseudocodice
getPermutations(CurItemList , CurPermList)
if CurItemList.isempty()
return CurPermList
else
Permutations = {}
for i = 1 to CurItemList.size()
CurPermList.addLast(CurItemList.get(i))
NextItemList = CurItemList.copy()
NextItemList.remove(i)
Permutations.add(getPermutations(NextItemList, CurPermList))
CurPermList.removeLast()
return Permutations
// To make it look better
Permutations(ItemList)
return getPermutations(ItemList, {})
I non l'ho provato, ma dovrebbe funzionare Forse non è il modo più intelligente per farlo, ma è un modo semplice. Se qualcosa non va, per favore fatemelo sapere!
Provare a creare il set di combinazioni in modo ricorsivo con un numero fisso di elementi possibili. L'insieme di tutte le combinazioni possibili sarà l'unione delle serie di combinazioni di 1 elemento, 2 elementi, ... fino a N elementi.
Quindi è possibile attaccare ogni combinazione di dimensioni fisse singolarmente.
- 1. Miglior algoritmo per ordini di compensazione
- 2. Architettura MySQL per algoritmo n * (n - 1)/2
- 3. Modo efficiente per trovare ordini di coppia?
- 4. dinamica programmazione algoritmo N, K problema
- 5. Un algoritmo di ordinamento O (n)
- 6. Algoritmo per trovare la sottostringa comune tra le stringhe N
- 7. Esiste un algoritmo O (n) per costruire un max-heap?
- 8. Algoritmo per risolvere il puzzle di N Queens Domination
- 9. O (n) algoritmo per scoprire l'elemento che appare più di n/2 volte
- 10. C#: algoritmo numerico per generare numeri dalla distribuzione binomiale
- 11. O-grande complessità del c^n + n * (log n)^2 + (10 * n)^c
- 12. Algoritmo C/C++: modo più veloce per calcolare (2^n)% d con e D 32 o 64 bit interi
- 13. Algoritmo di distanza di Levenshtein meglio di O (n * m)?
- 14. C# algoritmo per la generazione gerarchia
- 15. Questo algoritmo di O (n^4) è evitabile?
- 16. Algoritmo Rijndal usando C#
- 17. C# N l'unione per l'ordinamento esterno
- 18. Lanciare Y o N per boolare C#
- 19. C#: N Cicli For
- 20. Algoritmo "seleziona" C++
- 21. campionamento permutazioni di [1,2,3, ..., N] per la grande N
- 22. O (n) algoritmo per trovare la mediana di una raccolta di numeri
- 23. Corrispondenza a^n b^n c^n (ad esempio "aaabbbccc") utilizzando le espressioni regolari in C#
- 24. Questo algoritmo dovrebbe essere eseguito in O (n)?
- 25. algoritmo tfidf per python
- 26. Algoritmo per il calcolo del coefficiente binomiale
- 27. Esiste un algoritmo O (n) per generare un array senza prefisso per un array intero positivo?
- 28. Algoritmo per l'esclusione dei numeri
- 29. Algoritmo LP Simplex in C++
- 30. Algoritmo Triple DES in C?
è una combinazione o una permutazione? – sud03r
Vedere anche una spiegazione di due diversi algoritmi su http://stackoverflow.com/questions/352203/generating-permutations-lazily/ – ShreevatsaR