Calcolo combinazioni distinte
Ciao a tutti,
sto cercando di calcolare la quantità di combinazioni distinte considerato uno schema come il seguente:
A
B F
C
D G H
E
le possibili colonne di 5 lettere, con quell'ordine, sono 6, non le vado ad elencare...
Ciascuna di queste colonne le raggruppo per un K a scelta da 2 a 5. Ad esempio 3.
Ho quindi, per ogni colonna, 10 combinazioni semplici di 3 lettere. Moltiplicato per le 6 colonne ho 60 combinazioni.
Qualcuno sa come si può calcolare quante sono quelle distinte che dovrebbero essere 34?
Mi ci sto sbattendo da un po' ma mi mancano probabilmente molte basi
Grazie
sto cercando di calcolare la quantità di combinazioni distinte considerato uno schema come il seguente:
A
B F
C
D G H
E
le possibili colonne di 5 lettere, con quell'ordine, sono 6, non le vado ad elencare...
Ciascuna di queste colonne le raggruppo per un K a scelta da 2 a 5. Ad esempio 3.
Ho quindi, per ogni colonna, 10 combinazioni semplici di 3 lettere. Moltiplicato per le 6 colonne ho 60 combinazioni.
Qualcuno sa come si può calcolare quante sono quelle distinte che dovrebbero essere 34?
Mi ci sto sbattendo da un po' ma mi mancano probabilmente molte basi
Grazie
Risposte
Dunque...
Quando hai trovato tutte le possibili colonne da 5 elementi, le puoi ordinare in moto che tra una colonna e la successiva cambi solamente un elemento.
Nella prima colonna avrai (come hai detto te) 10 combinazioni semplici da 3 lettere.
Nella seconda colonna avrai delle combinazioni uguali alla prima (che non contiamo), con l'aggiunta di tutte le combinazioni che contengono il nuovo termine. Queste saranno : $((4),(2))$.
Lo stesso ragionamento vale per le altre colonne...
Il risultato sarà:
$10*((4),(2))*5=34$
Quando hai trovato tutte le possibili colonne da 5 elementi, le puoi ordinare in moto che tra una colonna e la successiva cambi solamente un elemento.
Nella prima colonna avrai (come hai detto te) 10 combinazioni semplici da 3 lettere.
Nella seconda colonna avrai delle combinazioni uguali alla prima (che non contiamo), con l'aggiunta di tutte le combinazioni che contengono il nuovo termine. Queste saranno : $((4),(2))$.
Lo stesso ragionamento vale per le altre colonne...
Il risultato sarà:
$10*((4),(2))*5=34$
"clrscr":
Dunque...
Il risultato sarà:
$10*((4),(2))*5=34$
Se ho ben capito il tuo ragionamento (che non condivo totalmente), il risultato dovrebbe essere:
$10+((4),(2))*5=40$
Non mi pare che la formula funzioni... la strada credo sia giusta però.
Dovrei capire come ridurre le combinazioni (in modo generalizzato) in base ai termini variabili delle colonne.
Nel caso che ho postato dovrebbe diventare: 10 + 6 + 6 + 6 + 3 + 3 = 34.
Sarebbe bello ci fosse una formula generalizzata per farlo... speriamo!
Dovrei capire come ridurre le combinazioni (in modo generalizzato) in base ai termini variabili delle colonne.
Nel caso che ho postato dovrebbe diventare: 10 + 6 + 6 + 6 + 3 + 3 = 34.
Sarebbe bello ci fosse una formula generalizzata per farlo... speriamo!
"cocco":
Non mi pare che la formula funzioni... la strada credo sia giusta però.
Dovrei capire come ridurre le combinazioni (in modo generalizzato) in base ai termini variabili delle colonne.
Nel caso che ho postato dovrebbe diventare: 10 + 6 + 6 + 6 + 3 + 3 = 34.
Sarebbe bello ci fosse una formula generalizzata per farlo... speriamo!
penso anche io che sia sbagliata,
ho riportato solo il calcolo del ragionamento di cslr
Avete ragione avevo commesso due errori...il primo di distrazione perchè c'è il + in $10+5*((4),(2))$.
Il secondo è che ho ipotizzato una cosa non del tutto giusta...adesso mi spiego:
Riscrivo le colonne dove tra una e quelle vicino cambia solo un termine:
A A A A A A
B B B F F F
C C C C C C
D G H H D G
E E E E E E
Ora la prima ha 10 sottoinsiemi da 3 elementi.
La seconda la terza e la quarta hanno $((4),(2))$ sottoinsiemi (nuovi) da 3 elementi.
La quinta e la sesta hanno solamente quelli che contengolo la D & F e G & F sono 3 + 3.
Estendendo il caso per K=2,3,4,5 avremo:
$((5),(K))+3*((4),(K-1))+((3),(K-2))*2$
Il secondo è che ho ipotizzato una cosa non del tutto giusta...adesso mi spiego:
Riscrivo le colonne dove tra una e quelle vicino cambia solo un termine:
A A A A A A
B B B F F F
C C C C C C
D G H H D G
E E E E E E
Ora la prima ha 10 sottoinsiemi da 3 elementi.
La seconda la terza e la quarta hanno $((4),(2))$ sottoinsiemi (nuovi) da 3 elementi.
La quinta e la sesta hanno solamente quelli che contengolo la D & F e G & F sono 3 + 3.
Estendendo il caso per K=2,3,4,5 avremo:
$((5),(K))+3*((4),(K-1))+((3),(K-2))*2$
Si, così la formula funziona ma se volessi saperlo, ad esempio, per i sottoinsiemi di 4 elementi non potrei più applicarla.
Scusa invece si... ora provo a variare il numero di elementi iniziali...
Ho provato con il seguente schema:
AF
BGH
CIJ
D
E
le colonne possibili risultano così 18 e non riesco a trovare una regola per distribuire le colonne (come sostituire cioè il fattore 3 e 2 usato per l'altro schema).
AF
BGH
CIJ
D
E
le colonne possibili risultano così 18 e non riesco a trovare una regola per distribuire le colonne (come sostituire cioè il fattore 3 e 2 usato per l'altro schema).
non ho seguito molto il topic (ed il forum). il $34$ verrebbe dalla formula $1+3*2+3*3+3*3*2$ in cui il primo addendo si riferisce alla scelta di {A,C,E}, il secondo alla scelta di uno tra B,F e due tra A,C,E, il terzo addendo alla scelta di uno tra D,G,H e due tra A,C,E, il quarto addendo alla scelta di uno tra A,C,E, uno tra B,F ed uno tra D,G,H.
ora devi considerare che hai una doppia, due triple e due singole. se devi scegliere terne di tali elementi, le dieci scelte di tre "righe" riguardano righe contenenti 1,2,3 elementi in questo modo (spero si capisca):
1+1+2 (1 caso)
2+3+3 (1 caso)
1+1+3 (2 casi)
1+3+3 (2 casi)
1+2+3 (4 casi)
dunque $1*1*2*1+2*3*3*1+*1*3*2+1*3*3*2+1*2*3*4=2+18+6+18+24=68$
spero di non aver commesso errori e di aver reso l'idea. ciao.
ora devi considerare che hai una doppia, due triple e due singole. se devi scegliere terne di tali elementi, le dieci scelte di tre "righe" riguardano righe contenenti 1,2,3 elementi in questo modo (spero si capisca):
1+1+2 (1 caso)
2+3+3 (1 caso)
1+1+3 (2 casi)
1+3+3 (2 casi)
1+2+3 (4 casi)
dunque $1*1*2*1+2*3*3*1+*1*3*2+1*3*3*2+1*2*3*4=2+18+6+18+24=68$
spero di non aver commesso errori e di aver reso l'idea. ciao.
Fantastica.... 
Confesso che ci ho messo un po'... ma ho capito!!
Ti ringrazio veramente tanto adaBTTLS!
Avrò a che fare anche con numeri alti, spero di trovare delle logiche preventive per evitare calcoli inutili.
Grazie a tutti per l'aiuto!
Ciao
Ti ringrazio veramente tanto adaBTTLS!
Avrò a che fare anche con numeri alti, spero di trovare delle logiche preventive per evitare calcoli inutili.
Grazie a tutti per l'aiuto!
Ciao
prego.
... e grazie ad Umby.
mi faccio vedere poco in questo periodo perché mi trovo, con portatile e chiavetta, in un posto di montagna in cui il collegamento internet (anche l'antenna televisiva...) fa veramente pena per quanto è lento...
... e grazie ad Umby.
mi faccio vedere poco in questo periodo perché mi trovo, con portatile e chiavetta, in un posto di montagna in cui il collegamento internet (anche l'antenna televisiva...) fa veramente pena per quanto è lento...
Visto che ci sono provo a buttarvene lì un'altra (evoluzione dello stesso argomento ovviamente) sperando di non sembrare troppo approfittatore...
Avrei a questo punto la necessità di scorrermi tutti questi raggruppamenti di k elementi. Finché si tratta di esplodere le varie combinazioni di una singola colonna non ci sono problemi, ho già un algoritmo che lo fa (sia ricorsivo che non) ma volendo esplodere i raggruppamenti tenendo conto di ciò che ci siamo scritti fin'ora (escludendo quindi le ripetizioni), secondo voi è possibile senza dover testare ogni volta se la singola combinazione è stata già utilizzata?
Ciao e grazie
cocco
Avrei a questo punto la necessità di scorrermi tutti questi raggruppamenti di k elementi. Finché si tratta di esplodere le varie combinazioni di una singola colonna non ci sono problemi, ho già un algoritmo che lo fa (sia ricorsivo che non) ma volendo esplodere i raggruppamenti tenendo conto di ciò che ci siamo scritti fin'ora (escludendo quindi le ripetizioni), secondo voi è possibile senza dover testare ogni volta se la singola combinazione è stata già utilizzata?
Ciao e grazie
cocco
Dipende molto dal software che intendi utilizzare per fare un simile algoritmo.
In casi simili io preferisco usare un file di appoggio con chiave univoca (senza duplicazione). Per ogni combinazione generata, faccio una lettura sul file (READ) e se il record già esiste, potrei incrementare di una unita' la frequenza ( cosi potro' sapere anche quali sono le combinazioni che si sono ripetute nel tempo, e quante volte si sono ripetute) (REWRITE). Nel caso in cui il record non esiste, lo genero impostando ad 1 il contatore delle frequenze. (WRITE)
Spero di aver risposto al tuo dubbio.
In casi simili io preferisco usare un file di appoggio con chiave univoca (senza duplicazione). Per ogni combinazione generata, faccio una lettura sul file (READ) e se il record già esiste, potrei incrementare di una unita' la frequenza ( cosi potro' sapere anche quali sono le combinazioni che si sono ripetute nel tempo, e quante volte si sono ripetute) (REWRITE). Nel caso in cui il record non esiste, lo genero impostando ad 1 il contatore delle frequenze. (WRITE)
Spero di aver risposto al tuo dubbio.
Ciao Umby,
quello che vorrei (ma forse non è possibile) è di poter analizzare una per una le combinazioni risultanti, tutto in memoria, e dover per ogni combinazioni cercare se è gia stata utilizzata in una struttura quale Dictionary o simili penso che rallenterebbe veramente tanto il tempo di esecuzione dell'algoritmo... Ovviamente parlando di numeri alti, ad esempio 20 elementi con 30 o 40 colonne da raggruppare ad esempio con un k=9.
Grazie mille comunque! Se trovo qualcosa di performante lo scrivo nel forum, ma dubito
Ciao
quello che vorrei (ma forse non è possibile) è di poter analizzare una per una le combinazioni risultanti, tutto in memoria, e dover per ogni combinazioni cercare se è gia stata utilizzata in una struttura quale Dictionary o simili penso che rallenterebbe veramente tanto il tempo di esecuzione dell'algoritmo... Ovviamente parlando di numeri alti, ad esempio 20 elementi con 30 o 40 colonne da raggruppare ad esempio con un k=9.
Grazie mille comunque! Se trovo qualcosa di performante lo scrivo nel forum, ma dubito
Ciao
"cocco":
.. Ovviamente parlando di numeri alti, ad esempio 20 elementi con 30 o 40 colonne da raggruppare ad esempio con un k=9.
IMHO
Guarda che, proprio quando i numeri diventano alti, hai bisogno di "appoggiare" i dati su un file di transito. Cosi' facendo eviti di fare elaborazioni complesse.
E' vero che l'uso di un file determina un decadimento delle prestazioni, pero' volendo potresti assegnare una partizione ad un pezzo di memoria. Cosi' il file anzichè gestirlo su HD, lo gestisce in memoria, e risolvi i problemi di lentezza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo