Newsgroup: it.comp.lang.visual-basic
Titolo: combinazioni ??

salve a tutti, il quesito che Vi pongo e' il seguente:
data una serie di numeri lunga a n piacere es: 1,2,3,4,5,..15,16
combinandoli k a piacere es 3 a 3 (senza ripetizioni) ottengo:
         n!                  16!
    ----------- = nel es.  ------  = 560 gruppi di tre numeri.
    (n-k)! * k!            13! * 3!
{1,2,3} {1,2,4} {1,2,5} ecc {14,15,16}
ora, se li volessi combinare a 3 a 3 in sequenze di 6 numeri
es {1,2,3,4,5,6} in modo tale da rappresentare tutte le combinazioni
da 3 numeri, senza che si ripetano per cui il gruppo 1,2,7,8,9,10 e'
valido (non contiene nessuna delle terzine gia presenti in
1,2,3,4,5,6) ed il gruppo 1,2,6,14,15,16 NON e' valido (1,2,6 e' gia'
presente in 1,2,3,4,5,6)
otterrei 560 gruppi / il numero di gruppi che si ottiene da 6 numeri =
 =  560 / ( 6! / (3!*3!)) = 560/20 = 28 gruppi di 6 numeri cadauno che
rappresentano (senza ripetersi) i 560 gruppi di 3 numeri cadauno.
Bene, sperando di essere stato fin qui chiaro, la domanda e':
qualcuno e' a conoscenza di un algoritmo che calcoli questi 28 gruppi
di 6 numeri ? (NB un algoritmo di carattere generale, 3, 6, 16 sono
quantita' casuali utilizzate a titolo di esempio).
Se puo' essere di aiuto, tale algoritmo dovrebbe (boh) essere simile
ad una qualche riduzione per sistemi tipo totocalcio/totogol/lotto
attualmente, spremendo al massimo le mie scarse cellule non ottengo
nulla di buono (nell'esempio citato 9 gruppi validi 
1-> 01 02 03 04 05 06
2-> 01 02 07 08 09 10
3-> 01 02 11 12 13 14 
4-> 01 03 07 11 15 16
5-> 02 04 08 12 15 16
6-> 03 04 07 08 13 14
7-> 03 04 09 10 11 12
8-> 05 06 07 08 11 12
9-> 05 06 09 10 13 14
ed una MAREA di gruppi di 3 NON "coperti" che se vado a ricombinare
danno luogo a ripetizioni e quindi sballano dal totale di 28 gruppi da
6.
mi scuso ancora una volta per la lunghezza, e se c'e' un anima buona
che ha un'illuminaizone e' ben accetta.
ciao.
Maurizio
mauma...@tin.it
togliere il primo mau per reply


L'ordine è importante? Ossia (1,2,3) e (1,3,2) sono validi?
Ciao Bruno


No, {1,2,3} = {1,3,2}
NB ho letto in giro che implementare un algoritmo del genere, che
ottenga soluzioni perfette e' impossibile (??!??) ma voglio provarci
lo stesso !! (ho la testa dura)


 [..]




Ciao, Silvio
pillow....@flashnet.it



Scusate il post multiplo!!!
mi sono incasinato con IE, ho pure saltato un livello, la risposta era per
maurizio
l'argomento comunque e' interessante

> di 6 numeri?
Mi sono perso il mex, puoi rispiegarmelo?? please??

> Mi sono perso il mex, puoi rispiegarmelo?? please??
probabilmente non trovi il messaggio perche' io ho risposto a quello
sbagliato.
intendevo rispondere al messaggio precedente a quello cui mi sono accodato.
comunque il quesito originale di maurizio, sul quale mi mettero' al lavoro
appena avro' un attimo era questo:
-------
salve a tutti, il quesito che Vi pongo e' il seguente:
data una serie di numeri lunga a n piacere es: 1,2,3,4,5,..15,16
combinandoli k a piacere es 3 a 3 (senza ripetizioni) ottengo:
         n!                  16!
    ----------- = nel es.  ------  = 560 gruppi di tre numeri.
    (n-k)! * k!            13! * 3!
{1,2,3} {1,2,4} {1,2,5} ecc {14,15,16}
ora, se li volessi combinare a 3 a 3 in sequenze di 6 numeri
es {1,2,3,4,5,6} in modo tale da rappresentare tutte le combinazioni
da 3 numeri, senza che si ripetano per cui il gruppo 1,2,7,8,9,10 e'
valido (non contiene nessuna delle terzine gia presenti in
1,2,3,4,5,6) ed il gruppo 1,2,6,14,15,16 NON e' valido (1,2,6 e' gia'
presente in 1,2,3,4,5,6)
otterrei 560 gruppi / il numero di gruppi che si ottiene da 6 numeri =
 =  560 / ( 6! / (3!*3!)) = 560/20 = 28 gruppi di 6 numeri cadauno che
rappresentano (senza ripetersi) i 560 gruppi di 3 numeri cadauno.
Bene, sperando di essere stato fin qui chiaro, la domanda e':
qualcuno e' a conoscenza di un algoritmo che calcoli questi 28 gruppi
di 6 numeri ? (NB un algoritmo di carattere generale, 3, 6, 16 sono
quantita' casuali utilizzate a titolo di esempio).
Se puo' essere di aiuto, tale algoritmo dovrebbe (boh) essere simile
ad una qualche riduzione per sistemi tipo totocalcio/totogol/lotto
attualmente, spremendo al massimo le mie scarse cellule non ottengo
nulla di buono (nell'esempio citato 9 gruppi validi 
1-> 01 02 03 04 05 06
2-> 01 02 07 08 09 10
3-> 01 02 11 12 13 14 
4-> 01 03 07 11 15 16
5-> 02 04 08 12 15 16
6-> 03 04 07 08 13 14
7-> 03 04 09 10 11 12
8-> 05 06 07 08 11 12
9-> 05 06 09 10 13 14
ed una MAREA di gruppi di 3 NON "coperti" che se vado a ricombinare
danno luogo a ripetizioni e quindi sballano dal totale di 28 gruppi da
6.
---------


stesso, il gioco e' fatto!
Potrebbe andare (magari poi confrontiamo i risultati ..) pero' ho dei
dubbi che sia SEMPRE la stessa cosa 28 elementi o 620 terzine, sono
uguali solo nel caso che le sestine diano tutte terzine VALIDE...
Io tento con un altro metodo: genero tutte le terzine, poi analizzo le
sestine e scelgo quella che, volta per volta, copre+terni, scelta la
sestina elimino i terni "coperti" e riparto ad analizzare le sestine
(e' parecchio pesante...)
a tutt'oggi sono arrivato a:
             combinazioni a certezza 3
numeri 	gruppi di 6  gruppi di 7  gruppi di 8
10	 10 (  0)      6	    4
11       15 (  1)      9            5
12       15 (  1)     11            8 
13       24 (  5)     16           10
14       26 ( 10)     19           13
15       34 ( 27)     20           17
16       43 ( 63)     27           17
17       55 (151)     34           23
il programma e' scritto in c, i numeri tra parentesi sono il tempo in
secondi sul mio p133, se non sbaglio i calcoli per n=20 si ha circa 40
minuti (troppo!!!)
Se riesci/riuscite a fare qualcosa di meglio... attendo fiducioso


Maurizio
il problema mi sembra un problema di ottimizzazione tipo alcuni problemi
sui grafi, che se non ricordo male erano tutti NP (non polinomiali) come
complessita', ovvero appena la dim del problema sale ti esplodono in faccia
(esponenziali o giu' di li'...)
appena ho un po' di tempo ritiro fuori i testi scolastici e provo qualcosa,
ciao
Silvio