Problema combinatorio
Supponendo di avere k oggetti differenti m1, m2, ..., mk è possibile elencarli nel modo (esempio fatto con k = 6)
1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m2
8. m1 m3
9. m1 m4
10. m1 m5
11. m1 m6
12. m2 m1
13. m2 m3
14. m2 m4
15. m2 m5
16. m2 m6
17. m3 m1
18. m3 m2
19. m3 m4
20. m3 m5
21. m3 m6
e sperare che esista un algoritmo veloce (che non richieda di calcolare sempre da 1) per avere una trasformazione da numero naturale a sequenza di oggetti e/o viceversa?
Quello che mi interessa è sapere se c'è un algoritmo immediato che dato il 16, per esempio, fornisca i coefficienti 2 e 6 e/o viceversa.
Se si giungesse alla conclusione che un tale algoritmo non è possibile, è invece possibile ottenerlo per la sequenza:
1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m1
8. m1 m2
9. m1 m3
10. m1 m4
11. m1 m5
12. m1 m6
13. m2 m1
14. m2 m2
15. m2 m3
16. m2 m4
17. m2 m5
18. m2 m6
19. m3 m1
20. m3 m2
Ovviamente non conta tanto l'ordine delle sequenze quanto il fatto che le sequenze con un numero più piccolo di mosse vengano sempre prima di quelle con un numero più grande.
Notare che nel primo caso la particolarità sta nel fatto che non ripeto mai due volte di seguito lo stesso oggetto, a differenza del secondo esempio.
1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m2
8. m1 m3
9. m1 m4
10. m1 m5
11. m1 m6
12. m2 m1
13. m2 m3
14. m2 m4
15. m2 m5
16. m2 m6
17. m3 m1
18. m3 m2
19. m3 m4
20. m3 m5
21. m3 m6
e sperare che esista un algoritmo veloce (che non richieda di calcolare sempre da 1) per avere una trasformazione da numero naturale a sequenza di oggetti e/o viceversa?
Quello che mi interessa è sapere se c'è un algoritmo immediato che dato il 16, per esempio, fornisca i coefficienti 2 e 6 e/o viceversa.
Se si giungesse alla conclusione che un tale algoritmo non è possibile, è invece possibile ottenerlo per la sequenza:
1. m1
2. m2
3. m3
4. m4
5. m5
6. m6
7. m1 m1
8. m1 m2
9. m1 m3
10. m1 m4
11. m1 m5
12. m1 m6
13. m2 m1
14. m2 m2
15. m2 m3
16. m2 m4
17. m2 m5
18. m2 m6
19. m3 m1
20. m3 m2
Ovviamente non conta tanto l'ordine delle sequenze quanto il fatto che le sequenze con un numero più piccolo di mosse vengano sempre prima di quelle con un numero più grande.
Notare che nel primo caso la particolarità sta nel fatto che non ripeto mai due volte di seguito lo stesso oggetto, a differenza del secondo esempio.
Risposte
Scusa, ma non ho capito una cosa: nel tuo elenco di disposizioni di N oggetti (per N=6, il tuo elenco constava solo di 21 sequenze) ci sono solo oggetti singoli e coppie di oggetti, oppure anche terne, quaterne, etc... ?
Per esempio il tuo elenco per 6 oggetti, dopo il 21.mo, immagino che prosegua senz'altro fino al 36.mo che è "m6 m5".
Poi cosa devo supporre? Che il tuo elenco è finito? Oppure si va avanti con le terne? cioè
37) m1 m2 m3
38) m1 m2 m4
... etc
Se sì, immagino che si debba continuare ad elencare anche le quaterne, le cinquine, etc.
Nel caso di 6 oggetti si dovrà continuare l'elenco fino all'ultima sestina che è: m6 m5 m4 m3 m2 m1. Giusto?
A proposito, se gli oggetti sono n, il numero di righe nell'elenco sarebbe
n + n(n-1) + n(n-1)(n-2) + ..... + n! = $\sum_{k=1}^n((n),(k))k!$
C'è qualcuno che conosce una formula chiusa per questa somma? Puzza lontano un miglio di "numeri di Stirling"!
Per esempio il tuo elenco per 6 oggetti, dopo il 21.mo, immagino che prosegua senz'altro fino al 36.mo che è "m6 m5".
Poi cosa devo supporre? Che il tuo elenco è finito? Oppure si va avanti con le terne? cioè
37) m1 m2 m3
38) m1 m2 m4
... etc
Se sì, immagino che si debba continuare ad elencare anche le quaterne, le cinquine, etc.
Nel caso di 6 oggetti si dovrà continuare l'elenco fino all'ultima sestina che è: m6 m5 m4 m3 m2 m1. Giusto?
A proposito, se gli oggetti sono n, il numero di righe nell'elenco sarebbe
n + n(n-1) + n(n-1)(n-2) + ..... + n! = $\sum_{k=1}^n((n),(k))k!$
C'è qualcuno che conosce una formula chiusa per questa somma? Puzza lontano un miglio di "numeri di Stirling"!
"seascoli":
37) m1 m2 m3
38) m1 m2 m4
... etc
a me sembra che l'utente abbia proposto le disposizioni "con ripetizione" infatti parla anche di m1-m1 e m2-m2
Te, invece, sembra che lo hai inteso "senza ripetizioni" m1-m2-m3 .....
Se leggi attentamente il suo primo intervento, Pandino82 dice che gli interessa un algoritmo di "tracciamento" per le disposizioni semplici (vedi il suo primo elenco) e solo come ripiego, cioè solo se
"Se si giungesse alla conclusione che un tale algoritmo non è possibile" gli interessa sapere se,"è invece possibile ottenerlo per la sequenza" delle disposizioni con ripetizione (vedi il suo secondo elenco).
Aggiungo che il topic da te indicato come riferimento, dove, a tuo dire "L'argomento è stato ampiamente trattato", in realtà mi pare che tratti un altro problema (quello delle permutazioni di n oggetti e del loro tracciamento seriale), quindi gli algoritmi ivi discussi non penso siano pertinenti ma solo di natura affine. Mi sbaglio?
"Se si giungesse alla conclusione che un tale algoritmo non è possibile" gli interessa sapere se,"è invece possibile ottenerlo per la sequenza" delle disposizioni con ripetizione (vedi il suo secondo elenco).
Aggiungo che il topic da te indicato come riferimento, dove, a tuo dire "L'argomento è stato ampiamente trattato", in realtà mi pare che tratti un altro problema (quello delle permutazioni di n oggetti e del loro tracciamento seriale), quindi gli algoritmi ivi discussi non penso siano pertinenti ma solo di natura affine. Mi sbaglio?
"seascoli":
Mi sbaglio?
Non ti sbagli.
Effettivamente Pandino aveva elencato sia quello con ripetizioni, e che quello senza.
L'argomento da me segnalato è simile. Semmai Pandino leggendolo puo' ricavarsi la soluzione del suo .... chissà.
Nuova precisazione e richiesta di chiarimenti.
Pandino82 ha scritto nel suo primo intervento:
"Ovviamente non conta tanto l'ordine delle sequenze quanto il fatto che le sequenze con un numero più piccolo di mosse vengano sempre prima di quelle con un numero più grande".
Che significa questo? Perchè si parla di "mosse"? Di che mosse si tratta? I suoi oggetti sono "mosse" in una partita di scacchi? Non vedo come.
E poi, cosa intende per "sequenze"? Disposizioni? come per esempio m2-m6 ? oppure sub-elenchi estratti dal suo elenco di disposizioni?
Infine cosa intende per "ordine delle sequenze"? L'ordine seriale con cui si susseguono le disposizioni nell'intero elenco? o l'ordine interno degli oggetti all'interno di una data disposizione?
Ora, se si guarda il suo primo elenco, altro che se conta l'ordine! e sia nel primo significato, sia nel secondo.
Chiedo quindi urgenti chiarimenti a Pandino82. Grazie
Sempre per Umby, cito la frase finale di Pandino82 (suo primo interventi)
<>
Pandino82 ha scritto nel suo primo intervento:
"Ovviamente non conta tanto l'ordine delle sequenze quanto il fatto che le sequenze con un numero più piccolo di mosse vengano sempre prima di quelle con un numero più grande".
Che significa questo? Perchè si parla di "mosse"? Di che mosse si tratta? I suoi oggetti sono "mosse" in una partita di scacchi? Non vedo come.
E poi, cosa intende per "sequenze"? Disposizioni? come per esempio m2-m6 ? oppure sub-elenchi estratti dal suo elenco di disposizioni?
Infine cosa intende per "ordine delle sequenze"? L'ordine seriale con cui si susseguono le disposizioni nell'intero elenco? o l'ordine interno degli oggetti all'interno di una data disposizione?
Ora, se si guarda il suo primo elenco, altro che se conta l'ordine! e sia nel primo significato, sia nel secondo.
Chiedo quindi urgenti chiarimenti a Pandino82. Grazie
Sempre per Umby, cito la frase finale di Pandino82 (suo primo interventi)
<
Affronto il problema "minimo" del tracciamento inverso degli ambi, cioè, dato un elenco di tutti gli ambi:
1) 1-2
2) 1-3
3) 1-4
...
...
89) 1-90
90) 2-3
91) 2-4
etc..
si vuole rispondere alla seguente domanda:
"Dato un posto nel suddetto elenco, qual è l'ambo che occupa tale posto?"
Il problema del tracciamento diretto è più facile e consiste nell'assegnare il posto giusto ad un dato ambo h - k.
Ovvero: Assegnato un ambo (h,k) dire che posto occupa nel precedente elenco.
A questo quesito più facile ha già dato una risposta Ada nel topic "Un terno al Lotto".
La risposta è $N(h,k) = h(90-(h+1)/2)+k-90$, anche se Ada ha preferito una ieratica, asettica forma polinomiale
Per esempio: l'ambo 3-6 occupa il posto N= 3(90-4/2)+6-90 = 180, cioè il 180.mo nel suddetto elenco (è facile verificarlo, perchè gli ambi che cominciano per 1 sono 89 e quelli che cominciano per 2 sono 88 ...)
Ora, invece, dato il posto N, dobbiamo trovare due interi h(N) e k(N) che definiscono l'ambo che occupa il posto N nell'elenco. Ecco l'algoritmo risolutivo.
Sia $F(n) = n/2(179-n)$ una funzione che mappa interi in interi (ci interessa solo per n=1,2,...,89)
Per la cronaca si ha: f(1) = 89, f(2)=177, f(3)=264, ...., f(87)=4002, f(88)=4004, f(89)=4005 .
Conviene compilare una tantum una tabella completa di f(n). Ovviamente f(n) è monotona crescente in n da 1 a 89.
Dato il posto N dell'ambo, definiamo ora la differenza $D(n) = f(n)-N$.
Sia h il primo dei valori di $n$ per cui risulta $D(n)>=0$. Allora l'ambo cercato è: ${h, k=90 - D(h)}$
Esempi
N=1: f(1)=89 , D = 89 - 1 = 88 >0 , quindi h=1, k = 90 - 88 = 2 cioè l'ambo è: (1,2), il primo, appunto.
N=89: f(1)=89, D=89-89=0 , quindi è (per un pelo!) ancora h=1, k = 90 - 0 = 90, cioè l'ambo è: (1,90), l'89.mo appunto.
N=100: f(1)=89 , 89 - 100<0 no!, f(2)=177-100=77>0 sì, quindi h=2, k = 90 - 77 = 13, cioè l'ambo è: (2,13).
Infatti il l'89.mo ambo è 1-90, il 90.mo è 2-3, e il 100.mo è 10 posti più avanti, cioè (2, 3+10) = (2,13) .
Gli ambi in tutto sono 45*89 = 4005. Vediamo quale ambo occupa il posto n. 4005 (sappiamo già la risposta).
N=4005, f(88)=4004 troppo piccolo, f(89)=4005 ok, D=4005-4005=0, h=89, k = 90 - 0 = 90, e l'ambo è (89,90).
Ultimo esempio, meno banale.
N=3741. Dalla tabella di f(n) si vedrà che f(65)=3705 (NO), f(66)=3729 (NO), f(67)=3752, sì, con D=3752-3741=11>0
Quindi h=67 e k=90-11=79, cioè l'ambo cercato è: (67,79).
Controlliamo la risposta usando la formula di Ada:
h=67, k=79, N(67,79)=h(90-{h+1}/2)+(k-90)=67(90-34)+(79-90)= 3752 - 11 = 3741 QED
Ciò conferma (nel senso di Popper) che ... la formula di Ada è esatta.
1) 1-2
2) 1-3
3) 1-4
...
...
89) 1-90
90) 2-3
91) 2-4
etc..
si vuole rispondere alla seguente domanda:
"Dato un posto nel suddetto elenco, qual è l'ambo che occupa tale posto?"
Il problema del tracciamento diretto è più facile e consiste nell'assegnare il posto giusto ad un dato ambo h - k.
Ovvero: Assegnato un ambo (h,k) dire che posto occupa nel precedente elenco.
A questo quesito più facile ha già dato una risposta Ada nel topic "Un terno al Lotto".
La risposta è $N(h,k) = h(90-(h+1)/2)+k-90$, anche se Ada ha preferito una ieratica, asettica forma polinomiale
Per esempio: l'ambo 3-6 occupa il posto N= 3(90-4/2)+6-90 = 180, cioè il 180.mo nel suddetto elenco (è facile verificarlo, perchè gli ambi che cominciano per 1 sono 89 e quelli che cominciano per 2 sono 88 ...)
Ora, invece, dato il posto N, dobbiamo trovare due interi h(N) e k(N) che definiscono l'ambo che occupa il posto N nell'elenco. Ecco l'algoritmo risolutivo.
Sia $F(n) = n/2(179-n)$ una funzione che mappa interi in interi (ci interessa solo per n=1,2,...,89)
Per la cronaca si ha: f(1) = 89, f(2)=177, f(3)=264, ...., f(87)=4002, f(88)=4004, f(89)=4005 .
Conviene compilare una tantum una tabella completa di f(n). Ovviamente f(n) è monotona crescente in n da 1 a 89.
Dato il posto N dell'ambo, definiamo ora la differenza $D(n) = f(n)-N$.
Sia h il primo dei valori di $n$ per cui risulta $D(n)>=0$. Allora l'ambo cercato è: ${h, k=90 - D(h)}$
Esempi
N=1: f(1)=89 , D = 89 - 1 = 88 >0 , quindi h=1, k = 90 - 88 = 2 cioè l'ambo è: (1,2), il primo, appunto.
N=89: f(1)=89, D=89-89=0 , quindi è (per un pelo!) ancora h=1, k = 90 - 0 = 90, cioè l'ambo è: (1,90), l'89.mo appunto.
N=100: f(1)=89 , 89 - 100<0 no!, f(2)=177-100=77>0 sì, quindi h=2, k = 90 - 77 = 13, cioè l'ambo è: (2,13).
Infatti il l'89.mo ambo è 1-90, il 90.mo è 2-3, e il 100.mo è 10 posti più avanti, cioè (2, 3+10) = (2,13) .
Gli ambi in tutto sono 45*89 = 4005. Vediamo quale ambo occupa il posto n. 4005 (sappiamo già la risposta).
N=4005, f(88)=4004 troppo piccolo, f(89)=4005 ok, D=4005-4005=0, h=89, k = 90 - 0 = 90, e l'ambo è (89,90).
Ultimo esempio, meno banale.
N=3741. Dalla tabella di f(n) si vedrà che f(65)=3705 (NO), f(66)=3729 (NO), f(67)=3752, sì, con D=3752-3741=11>0
Quindi h=67 e k=90-11=79, cioè l'ambo cercato è: (67,79).
Controlliamo la risposta usando la formula di Ada:
h=67, k=79, N(67,79)=h(90-{h+1}/2)+(k-90)=67(90-34)+(79-90)= 3752 - 11 = 3741 QED
Ciò conferma (nel senso di Popper) che ... la formula di Ada è esatta.
Ammettiamo di avere una n.pla di segni compresi fra 1 e N (N=90 per il lotto)
Una n.pla così è $(h_1, h_2, ..., h_n)$ con $h_i
Mah! così mi sembra troppo generale! Lasciamo perdere. Nel prossimo intervento tratterò solo le terne.
Una n.pla così è $(h_1, h_2, ..., h_n)$ con $h_i
Mah! così mi sembra troppo generale! Lasciamo perdere. Nel prossimo intervento tratterò solo le terne.
Si ha un elenco delle combinazioni di N oggetti a 3 a 3. L'elenco ha il solito ordine
{ 123, 124, 125, ....., 12N, 134, 135, ..., 13N, 145, ..., 1(N-1)N, 234, e così via}
Quest'elenco è lungo $((N),(3))$ terne. Dato ora un "posto" P nell'elenco con $1<= P<=((N),(3))$, si chiede:
Qual è la terna che occupa il posto P ?
RISPOSTA
Introduciamo le due funzioni di interi a valori interi:
$F_N(m)=((N),(3))-((N+1-m),(3))$ con $1<=m<=N-2$
$G_N(m,n)=(n-m)(N-\frac{m+n+1}{2})$ con $m
Allora, posto $A=\hat m -1$, sia $B$ il più piccolo valore di $n$ per cui si ha $G_N(A,m)>=P-F_N(A)$.
Allora il terno cercato è
${A, B, C}$ dove $C-=P+N-F_N(A)-G_N(A,B)$
Nel mio prossimo intervento farò un esempio.
{ 123, 124, 125, ....., 12N, 134, 135, ..., 13N, 145, ..., 1(N-1)N, 234, e così via}
Quest'elenco è lungo $((N),(3))$ terne. Dato ora un "posto" P nell'elenco con $1<= P<=((N),(3))$, si chiede:
Qual è la terna che occupa il posto P ?
RISPOSTA
Introduciamo le due funzioni di interi a valori interi:
$F_N(m)=((N),(3))-((N+1-m),(3))$ con $1<=m<=N-2$
$G_N(m,n)=(n-m)(N-\frac{m+n+1}{2})$ con $m
Allora, posto $A=\hat m -1$, sia $B$ il più piccolo valore di $n$ per cui si ha $G_N(A,m)>=P-F_N(A)$.
Allora il terno cercato è
${A, B, C}$ dove $C-=P+N-F_N(A)-G_N(A,B)$
Nel mio prossimo intervento farò un esempio.
Ecco l'esempio promesso.
Intanto ricordo la mia formula che risolve il problema del TRACCIAMENTO DIRETTO delle terne fatte di N oggetti.
Data una terna $(A,B,C)$, il posto $P$ che esso occupa nell'elenco seriale di tutte le terne è
(T1) $P_3^N(A,B,C)=(C-N)+(B-A)(N-(A+B+1)/2) +((N),(3)) - ((N+1-A),(3))$
Tale formula l'ho data nella sezione "Statistica e Probabilità", Topic: "Un terno al lotto"
Ora facciamo l'esempio: Sia N=9, cioè le terne si fanno partendo da un totale di 9 oggetti.
Quale terna occupa il 69.mo posto?
Si ha $F_9(m)= ((9),(3))-((10-m),(3)) = {0, 28, 49, 64, 74, ...}$, quindi $\hatm=5$ , $A=4$ e $F_9(4)=64$.
Cerchiamo ora B come il minimo valore di n tale che
$G_9(4,n)> P-F_9(4)=69-64=5$
Si ha per n=5, 6, ... : $G(4,n)=(n-4)(9-(5+n)/2)={4, 7, ...}$, quindi $B=6$ e $G_9(4,6)=7$
Quindi il terno cercato è:
${4, 6, 7}$ dato che C=69+9-(64+7)=78-71
Facciamo la verifica con la mia formula diretta (T1)
$P_3^9(4,6,7)= (7-9)+(6-4)(9-11/2)+((9),(3))-((10-4),(3))= -2+7+84-20=91-22=69 $. QED
A voi la palla per le quaterne, gringos !
Intanto ricordo la mia formula che risolve il problema del TRACCIAMENTO DIRETTO delle terne fatte di N oggetti.
Data una terna $(A,B,C)$, il posto $P$ che esso occupa nell'elenco seriale di tutte le terne è
(T1) $P_3^N(A,B,C)=(C-N)+(B-A)(N-(A+B+1)/2) +((N),(3)) - ((N+1-A),(3))$
Tale formula l'ho data nella sezione "Statistica e Probabilità", Topic: "Un terno al lotto"
Ora facciamo l'esempio: Sia N=9, cioè le terne si fanno partendo da un totale di 9 oggetti.
Quale terna occupa il 69.mo posto?
Si ha $F_9(m)= ((9),(3))-((10-m),(3)) = {0, 28, 49, 64, 74, ...}$, quindi $\hatm=5$ , $A=4$ e $F_9(4)=64$.
Cerchiamo ora B come il minimo valore di n tale che
$G_9(4,n)> P-F_9(4)=69-64=5$
Si ha per n=5, 6, ... : $G(4,n)=(n-4)(9-(5+n)/2)={4, 7, ...}$, quindi $B=6$ e $G_9(4,6)=7$
Quindi il terno cercato è:
${4, 6, 7}$ dato che C=69+9-(64+7)=78-71
Facciamo la verifica con la mia formula diretta (T1)
$P_3^9(4,6,7)= (7-9)+(6-4)(9-11/2)+((9),(3))-((10-4),(3))= -2+7+84-20=91-22=69 $. QED
A voi la palla per le quaterne, gringos !
Questo problema l'ho affrontato tempo fa da quando la Sisal ha introdotto il superenalotto e trovai una formula generale che indica il posto di una lista combinatoria di N elementi di lunghezza L (numero di elementi della lista) senza ripetizioni nell'ordine di generazione lessicografca; che qui scriverò, sperando che si capisca perchè non so come usare il codice per scrivere le formule in questi post.
allora:
Data una lista di N elementi di lunghezza L {v1,v2,v3.............vj} dove vj è il valore delle elemento nel posto j e P come posto della lista e indico come binomiale il sequedente simbolismo ,ad esempio binomiale 10 su 5 così (10 | 5).
P= (sommatoria per k=1 a k=V1 di ( (N-k) | (N-L+1-k) )) ) - ( sommatoria per j=2 a j=L della sommatoria per i=0 a i =(N-L+j-vj-1) di ( (L-j+i) | i ).
spero che possa tornare utile
saluti eugenio
allora:
Data una lista di N elementi di lunghezza L {v1,v2,v3.............vj} dove vj è il valore delle elemento nel posto j e P come posto della lista e indico come binomiale il sequedente simbolismo ,ad esempio binomiale 10 su 5 così (10 | 5).
P= (sommatoria per k=1 a k=V1 di ( (N-k) | (N-L+1-k) )) ) - ( sommatoria per j=2 a j=L della sommatoria per i=0 a i =(N-L+j-vj-1) di ( (L-j+i) | i ).
spero che possa tornare utile
saluti eugenio
Se è giusta certo che torna utile.
Ma lasciami il tempo per controllare.
Per scrivere meglio le formule cfr. Indice del forum $->$ Il nostro Forum: come si usa e come migliorarlo
Ma lasciami il tempo per controllare.
Per scrivere meglio le formule cfr. Indice del forum $->$ Il nostro Forum: come si usa e come migliorarlo
seascoli ,grazie per la dritta per srivere in codice
La formula generale e' questa
$\sum_{k=1}^ (k=v_1) $ $ ((N-k),(N-L+1-k))$ $ - $ $\sum_{j=2}^(j=L)$ $\sum_{i=0}^(i=N-L+j-v_j-1)$ $((L-j+i),(i))$
Questa formula funziona e ne ho verificato la validità con molti test al computer
saluti eugenio
La formula generale e' questa
$\sum_{k=1}^ (k=v_1) $ $ ((N-k),(N-L+1-k))$ $ - $ $\sum_{j=2}^(j=L)$ $\sum_{i=0}^(i=N-L+j-v_j-1)$ $((L-j+i),(i))$
Questa formula funziona e ne ho verificato la validità con molti test al computer
saluti eugenio
Non hai specificato se hai assunto N e L qualsiasi o, come mi sembra di capire, N>=L.
Per sicurezza di aver capito, riassumo la situazione.
Allora tu hai N segni ("non elementi") distinti, per esempio: le sette lettere A,B,C,...,G.
Usando questi segni tu formi delle combinazioni a L a L (per favore, non usare il termine "liste", chè non lo capisce nessuno), per cui, siccome l'ordine interno nelle combinazioni non importa , puoi sempre mettere gli L segni in ordine alfabetico. Giusto?
Bene. ora ti chiedo. Si tratta di combinazioni semplici o di combinazioni con ripetizione?
In parole povere, se fai combinazioni di 7 segni a 4 a 4 sono ammesse "parole del tipo:
AABC, ABBC, BEGG e persino, quindi FFFF ?
Questo va detto subito, se no non posso controllare niente della tua formula.
Adesso andiamo anche oltre. Se con i tuoi N segni provi a fare "parole" lunghe più di N caratteri (per esempio con le 7 lettere da A a G, provi a comporre una "parola" lunga 10 caratteri) allora non puoi evitare la ripetizione dei tuoi segni. Non puoi evitare la ripetizione addirittura in nessuna delle tue parole (o combinazioni che dir si vogliano).
Aspetto quindi tuoi lumi in proposito, ma lasciami fare un tentativo di indovinare.
C'è una parola che credo ti tradisca, ed é SuperEnalotto!
Allora credo che tu hai sempre avuto in mente N=90 e L=6. Giusto? E non ti sei nemmeno posto il problema delle ripetizioni dei segni all'interno di una stessa parola, perchè i meccanismi di formazione della sestina vincente sono tali da proibire categoricamente la possibilità che nella sestina vincente vi siano numeri ripetuti.
Ci ho preso? A presto.
PS: Devo avere anch'io, da qualche parte nei miei appunti, una formula che serve allo stesso scopo, ma mi sa che la mia funzionava solo se valevano le due condizioni: a) L<=N e b)i segni non si possono ripetere dentro una stessa parola (sono cioè combinazioni semplici di N segni presi a L a L).
A presto.
Per sicurezza di aver capito, riassumo la situazione.
Allora tu hai N segni ("non elementi") distinti, per esempio: le sette lettere A,B,C,...,G.
Usando questi segni tu formi delle combinazioni a L a L (per favore, non usare il termine "liste", chè non lo capisce nessuno), per cui, siccome l'ordine interno nelle combinazioni non importa , puoi sempre mettere gli L segni in ordine alfabetico. Giusto?
Bene. ora ti chiedo. Si tratta di combinazioni semplici o di combinazioni con ripetizione?
In parole povere, se fai combinazioni di 7 segni a 4 a 4 sono ammesse "parole del tipo:
AABC, ABBC, BEGG e persino, quindi FFFF ?
Questo va detto subito, se no non posso controllare niente della tua formula.
Adesso andiamo anche oltre. Se con i tuoi N segni provi a fare "parole" lunghe più di N caratteri (per esempio con le 7 lettere da A a G, provi a comporre una "parola" lunga 10 caratteri) allora non puoi evitare la ripetizione dei tuoi segni. Non puoi evitare la ripetizione addirittura in nessuna delle tue parole (o combinazioni che dir si vogliano).
Aspetto quindi tuoi lumi in proposito, ma lasciami fare un tentativo di indovinare.
C'è una parola che credo ti tradisca, ed é SuperEnalotto!
Allora credo che tu hai sempre avuto in mente N=90 e L=6. Giusto? E non ti sei nemmeno posto il problema delle ripetizioni dei segni all'interno di una stessa parola, perchè i meccanismi di formazione della sestina vincente sono tali da proibire categoricamente la possibilità che nella sestina vincente vi siano numeri ripetuti.
Ci ho preso? A presto.
PS: Devo avere anch'io, da qualche parte nei miei appunti, una formula che serve allo stesso scopo, ma mi sa che la mia funzionava solo se valevano le due condizioni: a) L<=N e b)i segni non si possono ripetere dentro una stessa parola (sono cioè combinazioni semplici di N segni presi a L a L).
A presto.
Ah, ecco, ho ritrovato fra i miei appunti la seguente formula che risolve la tua stessa questione per N non inferiore a L e per combinazioni semplici di N segni a L a L:
$P(v_1,v_2,....,v_L)=((N),(L))-\sum_{k=1}^L((N-v_k),(L+1-k))$
Tutto qui. Questa formula, che ora non ricordo come ho derivato, sembra molto più semplice della tua, per cui, se fosse esatta come tu dici essere la tua, le sarebbe senz'altro preferibile, già soltanto per la facilità di calcolo. Allora ti chiedo:
Potresti fare qualche verifica al computer e segnalarmi eventuali discrepanze fra la tua formula e la mia in qualche caso concreto? Grazie molte.
$P(v_1,v_2,....,v_L)=((N),(L))-\sum_{k=1}^L((N-v_k),(L+1-k))$
Tutto qui. Questa formula, che ora non ricordo come ho derivato, sembra molto più semplice della tua, per cui, se fosse esatta come tu dici essere la tua, le sarebbe senz'altro preferibile, già soltanto per la facilità di calcolo. Allora ti chiedo:
Potresti fare qualche verifica al computer e segnalarmi eventuali discrepanze fra la tua formula e la mia in qualche caso concreto? Grazie molte.
Nel tuo intervento, credo il quinto più su ,(Ecco l'esempio promesso) stavi parlado di trovare il posto di una combinazione di un terna senza ripetizioni.
e poi hai passato la palla per le quaterne.
Quind ti ho scritto la mia risposta inerente a questa ,intruducendo una formula generale per qualunque valore di N e di L .
Quindi non parlo di combinazioni con ripetizioni, anche perchè il metodo per trovarne la posizione è completamente diverso , semplice ed elementare .
Come mi hai chiesto ,verificherò la tua soluzione e ti farò sapere.
cardiali saluti i eugenio
e poi hai passato la palla per le quaterne.
Quind ti ho scritto la mia risposta inerente a questa ,intruducendo una formula generale per qualunque valore di N e di L .
Quindi non parlo di combinazioni con ripetizioni, anche perchè il metodo per trovarne la posizione è completamente diverso , semplice ed elementare .
Come mi hai chiesto ,verificherò la tua soluzione e ti farò sapere.
cardiali saluti i eugenio
Primo. No, non hai capito qual era il problema (posto all'inizio da Pandino82, l'iniziatore di questo topic) che io stavo cominciando a risolvere per ambi e terni lasciando la "palla" ad altri per le quaterne. Io l'ho chiamato il problema del tracciamento inverso mentre la tua formula (e la mia inviatati di rimando) sono pertinenti solo nella risoluzione del problema del tracciamento diretto.
Per chiarezza ripeto l'enunciato dei due distinti problemi, problemi di cui quello inverso risulta ben più arduo del primo.
In entrambi i problemi si suppone si abbia l'elenco (in ordime lessicografico) di tutte le combinazioni semplici di N segni a L a L.
TRACCIAMENTO DIRETTO. Data una combinazione $(v_1, v_2, ...,v_L)$ , dire che posto P essa occupa nel suddetto elenco. Ovviamente sarà $1<=P<=((N),(L))$
TRACCIAMENTO INVERSO. Fissato un posto P nel suddetto elenco, quale combinazione occupa quel posto P ?
Che il primo problema sia molto più abbordabile del secondo te lo dice già il fatto che, mentre nel primo caso devi trovare un solo numero P, dati L numeri, nel secondo invece ti è dato un solo numero, P, e tu da quello devi far uscire (come da un unico cappello a cilindro) anche decine di numeri (per es. se N=90 e L=32).
Insomma, tu con la tua formula ed io con la mia (se é esatta) abbiamo solo risolto il problema del "tracciamento diretto" e non di quello "inverso". Per questo più difficile problema non so se esista una formula generale unica per ogni N e L con N non inferiore a L, cioè una formula analoga per potenza a quella che noi pensiamo di aver trovato nel problema diretto. Io ho qualche dubbio in proposito (AdaBTTLS ha persino affermato -cfr. Sezione: Statistica e Probabilità, Topic: Un terno al Lotto! - che non è un problema combinatorio, ma un problema di ricerca di algortimi ottimali, e forse non ha tutti i torti), ma, ammesso che una formula del genere esiste, allora è difficile da trovare. Basta guardare le mie due formule in questo "topic" che risolvono completamente il problema del "tracciamento inverso" per ambi e terni, cioè per N qualsiasi, ma solo per L=2,3.
Sono stato chiaro?
Infine, mi interessa molto quello che dici sulle "combinazioni con ripetizione". Mi sembra di capire che ci sia un algoritmo "elementare" per risolvere il problema del loro tracciamento diretto. E' così? Puoi essere più esplicito in proposito? Grazie
Per chiarezza ripeto l'enunciato dei due distinti problemi, problemi di cui quello inverso risulta ben più arduo del primo.
In entrambi i problemi si suppone si abbia l'elenco (in ordime lessicografico) di tutte le combinazioni semplici di N segni a L a L.
TRACCIAMENTO DIRETTO. Data una combinazione $(v_1, v_2, ...,v_L)$ , dire che posto P essa occupa nel suddetto elenco. Ovviamente sarà $1<=P<=((N),(L))$
TRACCIAMENTO INVERSO. Fissato un posto P nel suddetto elenco, quale combinazione occupa quel posto P ?
Che il primo problema sia molto più abbordabile del secondo te lo dice già il fatto che, mentre nel primo caso devi trovare un solo numero P, dati L numeri, nel secondo invece ti è dato un solo numero, P, e tu da quello devi far uscire (come da un unico cappello a cilindro) anche decine di numeri (per es. se N=90 e L=32).
Insomma, tu con la tua formula ed io con la mia (se é esatta) abbiamo solo risolto il problema del "tracciamento diretto" e non di quello "inverso". Per questo più difficile problema non so se esista una formula generale unica per ogni N e L con N non inferiore a L, cioè una formula analoga per potenza a quella che noi pensiamo di aver trovato nel problema diretto. Io ho qualche dubbio in proposito (AdaBTTLS ha persino affermato -cfr. Sezione: Statistica e Probabilità, Topic: Un terno al Lotto! - che non è un problema combinatorio, ma un problema di ricerca di algortimi ottimali, e forse non ha tutti i torti), ma, ammesso che una formula del genere esiste, allora è difficile da trovare. Basta guardare le mie due formule in questo "topic" che risolvono completamente il problema del "tracciamento inverso" per ambi e terni, cioè per N qualsiasi, ma solo per L=2,3.
Sono stato chiaro?
Infine, mi interessa molto quello che dici sulle "combinazioni con ripetizione". Mi sembra di capire che ci sia un algoritmo "elementare" per risolvere il problema del loro tracciamento diretto. E' così? Puoi essere più esplicito in proposito? Grazie
non so se ho capito il problema, ma se si tratta dell'ordine "alfabetico" di una parola di di L lettere tra tutte le perole di L lettere costruite su un alfabeto di K simboli, allora, se le lettere possono essere ripetute in qualunque modo, il problema è veramente molto più semplice, perché tutte le possibili parole sono $K^L$, e,
se si associa ad ogni lettera dell'alfabeto il numero corrispondente del relativo ordine: $l_i -> k_i$, dove $l_i$ è la i-esima lettera della parola di L lettere e $k_i$ è il relativo ordine nell'alfabeto dei K simboli,
allora la parola che appare con la seguente successione di simboli $l_1,l_2,...,l_L$, ove chiamiamo $k_1,k_2,...,k_L$ i rispettivi ordini dei simboli nell'alfabeto
è la n° : $1+sum_(i=1)^L\(k_i-1)*K^(L-i)$.
quanto all'affermazione citata, potete verificare nel topic in questione, ma ho riportato una mia prima impressione, non vedendo una semplice soluzione "combinatoria" al problema proposto e suggerendo una strada inversa, mentre intendevo suggerire di proporre il problema originario in un'altra sezione.
ciao.
se si associa ad ogni lettera dell'alfabeto il numero corrispondente del relativo ordine: $l_i -> k_i$, dove $l_i$ è la i-esima lettera della parola di L lettere e $k_i$ è il relativo ordine nell'alfabeto dei K simboli,
allora la parola che appare con la seguente successione di simboli $l_1,l_2,...,l_L$, ove chiamiamo $k_1,k_2,...,k_L$ i rispettivi ordini dei simboli nell'alfabeto
è la n° : $1+sum_(i=1)^L\(k_i-1)*K^(L-i)$.
quanto all'affermazione citata, potete verificare nel topic in questione, ma ho riportato una mia prima impressione, non vedendo una semplice soluzione "combinatoria" al problema proposto e suggerendo una strada inversa, mentre intendevo suggerire di proporre il problema originario in un'altra sezione.
ciao.
Eugenio54 scripsit (7/2/09 12:16) : "Quindi non parlo di combinazioni con ripetizioni, anche perchè il metodo per trovarne la posizione è completamente diverso , semplice ed elementare."
Seascoli respondit: "Infine, mi interessa molto quello che dici sulle "combinazioni con ripetizione". Mi sembra di capire che ci sia un algoritmo "elementare" per risolvere il problema del loro tracciamento diretto. E' così? Puoi essere più esplicito in proposito?"
-----------------------------------------------------------
Si era detto "combinazioni con ripetizione" non "disposizioni con ripetizione". Nessuno, appena un po' esperto, si sognerebbe di porre il problema del tracciamento per le disposizioni con ripetizione, dato che c'è un algoritmo elementare (quello scritto da AdaBTTLS), un algoritmo che si potrebbe chiamare lapidariamente "l'algortimo del contachilometri".
Ma per le combinazioni con ripetizione non vedo un algoritmo altrettanto banale (in realtà, non ci ho ancora pensato su granchè)
L'elenco "lessicografico" dei "terni" fatti con 4 segni sarebbe questo (cfr. peraltro il primo elenco scritto da Pandino82 quando ha aperto questo topic, che è quello delle "disposizioni semplici" di N segni, prima a 1 a 1, poi a 2 a 2, poi a 3 a 3, etc..., mentre il suo secondo elenco è quello analogo delle disposizioni con ripetizione):
111
112
113
114
122 (e non 121, come si dovrebbe scrivere se si trattasse di disposizioni con ripetizione)
123
124
....
344
444 , e questo è l'ultimo terno, e sta al posto n. 20 (non al posto n. 64, come avverrebbe con le disposizioni con r.)
Bene! Chiedo di nuovo a Eugenio54 (o a chiunque altro) di esibire una formula per il tracciamento diretto delle combinazioni con ripetizione di N segni presi a L a L, nel consueto ordine lessicografico. Ovviamente ora deve cadere il vincolo che sia $L<=N$.
Seascoli respondit: "Infine, mi interessa molto quello che dici sulle "combinazioni con ripetizione". Mi sembra di capire che ci sia un algoritmo "elementare" per risolvere il problema del loro tracciamento diretto. E' così? Puoi essere più esplicito in proposito?"
-----------------------------------------------------------
Si era detto "combinazioni con ripetizione" non "disposizioni con ripetizione". Nessuno, appena un po' esperto, si sognerebbe di porre il problema del tracciamento per le disposizioni con ripetizione, dato che c'è un algoritmo elementare (quello scritto da AdaBTTLS), un algoritmo che si potrebbe chiamare lapidariamente "l'algortimo del contachilometri".
Ma per le combinazioni con ripetizione non vedo un algoritmo altrettanto banale (in realtà, non ci ho ancora pensato su granchè)
L'elenco "lessicografico" dei "terni" fatti con 4 segni sarebbe questo (cfr. peraltro il primo elenco scritto da Pandino82 quando ha aperto questo topic, che è quello delle "disposizioni semplici" di N segni, prima a 1 a 1, poi a 2 a 2, poi a 3 a 3, etc..., mentre il suo secondo elenco è quello analogo delle disposizioni con ripetizione):
111
112
113
114
122 (e non 121, come si dovrebbe scrivere se si trattasse di disposizioni con ripetizione)
123
124
....
344
444 , e questo è l'ultimo terno, e sta al posto n. 20 (non al posto n. 64, come avverrebbe con le disposizioni con r.)
Bene! Chiedo di nuovo a Eugenio54 (o a chiunque altro) di esibire una formula per il tracciamento diretto delle combinazioni con ripetizione di N segni presi a L a L, nel consueto ordine lessicografico. Ovviamente ora deve cadere il vincolo che sia $L<=N$.
Ecco, l'ho trovata dopo una mezz'oretta di riflessione.
Il "rationale" è lo stesso che sta alla base della mia formula per le combinazioni semplici:
(1) $P^r(n_1,n_2, ......., n_L) = C^r(N,L)-\sum_{k=1}^L C^r(N-n_k,L+1-k)$
dove $C^r(N,p)$ indica il numero delle "combinazioni con ripetizione di N oggetti su p posti",
numero che fa $((N+p-1),(p))$.
Trattandosi di combinazioni con ripetizione, deve risultare (ovviamente): $n_1<=n_2<=..... <=n_L$.
Peraltro N e L sono del tutto generici.
Si noti che, se nella (1) togliamo dappertutto l'apice r e accettiamo i vincoli $N>=L$ e $n_1
contando ogni volta quante combinazioni con ripetizione vanno saltate all'indietro per raggiungere la tappa successiva ...
Ogni volta il numero di comb_r da saltare sono le comb_r di $N-n_k$ simboli restanti su $L+1-k$ posti restanti, da cui la formula.
Un ragionamento perfettamente analogo si può fare per le combinazioni semplici
Il "rationale" è lo stesso che sta alla base della mia formula per le combinazioni semplici:
(1) $P^r(n_1,n_2, ......., n_L) = C^r(N,L)-\sum_{k=1}^L C^r(N-n_k,L+1-k)$
dove $C^r(N,p)$ indica il numero delle "combinazioni con ripetizione di N oggetti su p posti",
numero che fa $((N+p-1),(p))$.
Trattandosi di combinazioni con ripetizione, deve risultare (ovviamente): $n_1<=n_2<=..... <=n_L$.
Peraltro N e L sono del tutto generici.
Si noti che, se nella (1) togliamo dappertutto l'apice r e accettiamo i vincoli $N>=L$ e $n_1
contando ogni volta quante combinazioni con ripetizione vanno saltate all'indietro per raggiungere la tappa successiva ...
Ogni volta il numero di comb_r da saltare sono le comb_r di $N-n_k$ simboli restanti su $L+1-k$ posti restanti, da cui la formula.
Un ragionamento perfettamente analogo si può fare per le combinazioni semplici
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo