PDA

Visualizza la versione completa : [c++] generare tutte le possibili combinazioni di A,B,C date 10 posizioni


freetom
25-01-2010, 10:17
Dati 3 elementi A,B,C e 10 posizioni...
Generare tutte le possibili combinazioni non ripetute di A,B,C a coprire tutte le 10 posizioni..

es.
A,A,A,A,A,A,A,A,B,C
A,A,A,A,B,B,C,C,C,C
A,A,A,B,B,C,C,C,C,C
ecc...

E' possibile secondo voi farlo in c++?
Da cosa potrei partire...? :confused:


Grazie

:ciauz:

ps:Per adesso a me tornerebbero 154 combinazioni univoche ma vi chiedo conferma o smentita. :ecco:

MItaly
25-01-2010, 10:34
Se si parla di combinazioni (non permutazioni) dovrebbero essere 3^10=59049 combinazioni. Ho scritto un po' di tempo fa proprio per un utente del forum del codice generico per il calcolo di combinazioni di cui vado piuttosto fiero: versione originale (http://forum.html.it/forum/showthread.php?s=&postid=12701416#post12701416); versione resa generica (http://stackoverflow.com/questions/1991361/find-all-combinations-of-a-given-set-of-numbers/1991542#1991542).
Ti basti sapere che sulla mia macchina (vecchiotta) macina circa 20 milioni di combinazioni al secondo.

freetom
25-01-2010, 13:38
Originariamente inviato da MItaly
Se si parla di combinazioni (non permutazioni) dovrebbero essere 3^10=59049 combinazioni. Ho scritto un po' di tempo fa proprio per un utente del forum del codice generico per il calcolo di combinazioni di cui vado piuttosto fiero: versione originale (http://forum.html.it/forum/showthread.php?s=&postid=12701416#post12701416); versione resa generica (http://stackoverflow.com/questions/1991361/find-all-combinations-of-a-given-set-of-numbers/1991542#1991542).
Ti basti sapere che sulla mia macchina (vecchiotta) macina circa 20 milioni di combinazioni al secondo.

Ma le permutazioni cosa sarebbero? :confused: :)

Grazie mille e stra-complimenti per il tuo programma!

:ciauz:

ps:In sostanza a ma servirebbe di sapere in particolare solo i mix possibili dei 3 elementi secondo le 10 quantità non posizioni.. cerco di spiegarmi meglio con un altro esempio.. perchè probabilmente ho portato fuori rotta...

AAAABBCCCC -> 4a 2b 4c
per me è esattamente la stessa cosa di
AABBAACCCC -> 4a 2b 4c
o ancora... di...
ABBCCCCAAA -> 4a 2b 4c

quindi queste 3 ad esempio valgono x 1 solo caso...

Spero di essere stato + chiaro adesso e mi scuso per l'inesattezza della domanda precedente :stordita:

Grazie ancora MItaly :zizi:

ybla82
25-01-2010, 14:13
ciao,
secondo me puoi usare 3 cicli for annidati l'uno dentro l'altro.

La soluzione però è customizzata in caso di dimensione 10 e con 3 tipi di elementi, e ho supposto che per ogni combinazione ci debba essere almeno un elemento per tipo.

Detto questo...

primo for conta da 0 a 8.
il secondo conta da [valore contatore predente] + 1 fino a 9
il terzo conta da [valore contatore predente] + 1 fino a 10.


Diversamente se vuoi una cosa generica, potrebbe essere una soluzione pensare ad una funzione ricorsiva.

MItaly
25-01-2010, 17:59
Originariamente inviato da freetom
ps:In sostanza a ma servirebbe di sapere in particolare solo i mix possibili dei 3 elementi secondo le 10 quantità non posizioni.. cerco di spiegarmi meglio con un altro esempio.. perchè probabilmente ho portato fuori rotta...
Roba tipo lotto, quindi? Allora ti va bene la soluzione di ybla82; puoi renderla generica con funzioni ricorsive (ma in questa maniera aggiungi l'overhead della chiamata a funzione, che sui grandi numeri si fa sentire), oppure puoi modificare in qualche maniera il mio programma (che di fatto simula dei for annidati con un unico for magico).

Loading