Problema combinatorio

[seascoli]

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 !

[eugenio54]

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

[seascoli]

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

[eugenio54]

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

[seascoli]

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.

[seascoli]

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.

[eugenio54]

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

[seascoli]

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

[adaBTTLS]

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.

[seascoli]

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$.