Help si Numerare le combinazioni, algortmo.

[pigi76]

Salve a tutti,
Volevo porre un quesito che da giorni mi fa versare fiumi di carta ed esempi.

Vi faccio direttamente un esempio facile, il gioco del lotto:
Disposizioni senza ripetizione di 90 numeri classe 5, ovvero
90x89x88x87x86/5! = 43949268 di combinazioni
fin ora tutto facile il difficle e quanto segue:

Sapendo che la combinazione N° 1 è (1-2-3-4-5) e la combinazione N°43949268 è
ovviamente (86x87x88x89x90), chi mi sa dire alla pozione 100000 che combinazione troviamo?
Ecco e da giorni che impazizsco sul algoritimo...
Qualcuno di voi mi sa aiutare?


grazie
pigi76

[Admin]

Disposizioni senza ripetizione di 90 numeri classe 5, ovvero
90x89x88x87x86/5! = 43949268 di combinazioni

La formula da te citata si riferisce alle combinazioni senza ripetizione di 90 numeri in classe 5;
invece le disposizioni senza ripetizione di 90 numeri in classe 5 sono:

$D_5^{90}=90\cdot89\cdot...\cdot(90-5+1)=90\cdot89\cdot\88\cdot87\cdot86=5273912160$

la domanda da te posta è confusa; non si capisce se ti riferisci a disposizioni o a combinazioni;
in ogni caso per sapere che combinazione o disposizione ci sia in posizione 100000, bisogna sapere secondo che logica vengono ordinate le combinazioni o disposizioni;
nel senso che, se dopo la combinazione 1-2-3-4-5 e logico pensare che venga 1-2-3-4-6, dopo la combinazione 1-2-3-4-90 cosa verrà?

facci sapere...

Admin

[pigi76]

si forse non sono bravo coi "termini", in ogni caso dopo la combinazione 1-2-3-4-5 viene 1-2-3-4-6, e dopo 1-2-3-4-90 viene 1-2-3-5-6
percui la forumla di calcolo del totale è: (90*89*88*87*86)/(5*4*3*2*1)...
quindi credo parliamo di combinazioni e non di disposizioni... i termini li confondo prutroppo

in ogni modo intuisco che il ragionamento di debba fare con i 'resti' tant'e vero che so come ricavare da una combinazione la posizione, ma non so fare il contrario!

esempio con terno: 90*89*88/ 3! = 117480 comb totali.


Volgiamo sapere che posizione occupa la combinazione 10-20-30
quindi facciamo:

[(90-10)*(90-10-1)*(90-10-2) / 3! ] +
[(90-20)*(90-20-1)/2!]+
[(90-30)]

quindi la combinazione 10-20-30 è in poszione 84635.


Ecco a me interessa il contrario, cioe la forumla per sapere ce ad esempio nella posizone 64636 che combinazione troveremo?

grazie
pigi76

[Admin]

Veramente un problema interessante;
mi è piaciuto molto, anche per il fatto che la risoluzione coinvolge l'aritmetica modulare di cui si discute in questi giorni sul forum.

Dunque, abbiamo 90 numeri combinati in classe 5;
le prime $t^'$ combinazioni inizieranno per 1.
Vediamo quanto vale $t^'$;
$t^'$ ci sarà dato dalle combinazioni di 89 elementi in classe 4 (l'1 all'inizio resta fisso); per cui

$t^'=\frac{89!}{4!\,85!}=\frac{89\cdot88\cdot87\cdot86}{4!}$

Quindi le prime $\frac{89\cdot88\cdot87\cdot86}{4!}$ avranno un 1 come 1° numero.
Le seconde $\frac{89\cdot88\cdot87\cdot86}{4!}$ avranno un 2 come 2° numero; e così via...
Per cui possiamo dividere l'insieme di tutte le combinazioni in 90 intervalli ciascuno dei quali contiene $\frac{89\cdot88\cdot87\cdot86}{4!}$ combinazioni che cominciano con uno stesso numero.
Quindi per sapere il 1° numero di una combinazione che si trova in una posizione $n$ dobbiamo effettuare la divisione intera tra $n$ e $\frac{89\cdot88\cdot87\cdot86}{4!}$;
il quoziente intero della divisione aumentato di 1, ossia $q_1+1$, ci da il 1° numero della combinazione; il resto $r_1$ invece ci serve per determinare gli altri numeri della combinazione.

Veniamo al 2° numero della combinazione;
all'interno di un intervallo abbiamo 89 sotto-intervalli ciascuno dei quali contiene un numero $t^{''}$ di combinazioni che hanno il 1° e 2° numero uguale;
tale numero $t^{''}$ di combinazioni è pari alle combinazioni di 88 elementi in classe 3, ossia:

$t^{''}=\frac{88!}{3!\,85!}=\frac{88\cdot87\cdot86}{3!}$

Per cui per trovare il 2° numero della combinazione di posizione $n$ dobbiamo effettuare la divisione intera tra $r_1$ e $\frac{88\cdot87\cdot86}{3!}$;
il quoziente intero aumentato di 2, ossia $q_2+2$ ci da il 2° numero della combinazione; il resto $r_2$ ci serve invece per determinare il 3° numero della combinazione.

Veniamo al 3° numero;
ricapitolando, abbiamo i 90 intervalli relativi al 1° numero della combinazione;
ognuno di essi è diviso in 89 sotto-intervalli relativi al 2° numero;
ora ognuno di questi sotto-intervalli,è diviso in 88 sotto-intervalli che contengono $t^{'''}$ combinazioni che hanno 1°, 2° e 3° numero uguale;
tale numero $t^{'''}$ è pari alle combinazioni di 87 elementi in classe 2; per cui:

$t^{'''}=\frac{87!}{2!\,85!}=\frac{87\cdot86}{2!}$;

Quindi, per trovare il 3° numero della combinazione in posizione $n$ dobbiamo effettuare la divisione intera tra $r_2$ e $\frac{87\cdot86}{2!}$;
il quoziente intero aumentato di 3, ossia $q_3+3$, ci da il 3° numero, mentre il resto $r_3$ ci serve per trovare il 4° numero.

Ora, analogamente ai casi precedenti, per trovare il 4° numero della combinazione in posizione $n$, dobbiamo dividere $r_3$ per $\frac{86}{1!}=86$; il quoziente aumentato di 4, ossia $q_4+4$, ci da il 4° numero, mentre il resto $r_4$ aumentato di 5, ossia $r_4+5$ ci da il 5° ed ultimo numero.
Questo è l'algoritmo.

Importante: affinchè l'algoritmo funzioni correttamente c'è bisogno che le combinazioni vadano numerate partendo da 0; per cui se vogliamo sapere qual'è la combinazione che si trova ad es. in 48988-esima posizione dobbiamo eseguire l'algoritmo con $n=48988-1$.

Correzione: va apportata una correzione all'algoritmo nel caso in cui si stia calcolando l' $n$-esimo numero della combinazione e il quoziente $q_n=n$; ad es. se stiamo calcolando il 2° numero della combinazione e $q_2=2$; in tal caso e solo in tale caso, si aumenta il quoziente di 1, per cui, ad. es., se $q_2=2$ si pone $q_2=3$.

Quindi l'algoritmo si può riassumere con i seguenti passaggi:

Detta $n$ la posizione della combinazione da individuare:

1) si effettua la divisione intera tra $n$ e $\frac{89\cdot88\cdot87\cdot86}{4!}$; si ottiene $q_1$ e $r_1$;
2) si effettua la divisione intera tra $r_1$ e $\frac{88\cdot87\cdot86}{3!}$; si ottiene $q_2$ e $r_2$;
3) si effettua la divisione intera tra $r_2$ e $\frac{87\cdot86}{2!}$; si ottiene $q_3$ e $r_3$;
4) si effettua la divisione intera tra $r_3$ e $86$; si ottiene $q_4$ e $r_4$.

Effettuate queste divisioni, la combinazione, salvo eventuali correzioni da apportare, ci è data da:

$(q_1+1)--(q_2+2)--(q_3+3)--(q_4+4)--(r_4+5)$

Il tutto SE&O

Admin

[pigi76]

non mi ridà il calcolo su numeri reali, faccoi un esempio con i numeri:

Faccio l'esempio del terno per fare prima: (90x89x88/3!) = 117480 combinazioni

Volgiamo sapere quale combianzione cade alla posizione 117480
percui faremo 117480 -1 = n = 117479

117479 / (89*88 / 2!) quindi avremo q = 29 ??? (quindi non ridà, dovrebbe essere 88)


Inloltre analizzando la formula ho notato una differenza tra la prima parte e il reassunto: Perche in prima aprte si parte da 89x88x87x86 / 4! mentre nel reassunto si parte da 90x89x88x87x86 / 5! ???

perche nel reassunto manca la divisione per 2! ???

grazie ancora per l'auito

[Admin]

Scusami,
per la fretta avevo commesso vari errori nel riassunto finale;
adesso li ho corretti.

In ogni caso, grazie alla tua segnalazione, mi sono accorto che l'algoritmo in sè non è corretto;
infatti nella varie iterazioni considera più volte una stessa combinazione, che invece va presa una sola volta;

pertanto necessita delle correzioni.

Ci provo, e ti faccio sapere.

Ciao
Admin

[Admin]

In effetti, il problema è più complesso del previsto;
sono arrivato ad un buon punto;
per andare avanti però mi serve un'espressione in $n$ della seguente sommatoria:

$\displaystyle \sum_{i=1}^{n} \frac{(90-i-1)(90-i)}{2}$

cioè la somma dei primi $n$ termini della serie

$\frac{89\cdot88}{2}+\frac{88\cdot87}{2}+\frac{87\cdot86}{2}+...+\frac{(90-n-1)\cdot(90-n)}{2}+...$

idee in proposito?

P.S.: ho corretto il post; chiedo scusa agli eventuali ri-lettori del post.

Ciao
Admin

[pigi76]

io sto certcando di arrvarci per ragionamento contrario, ovvero: partendo dal fattore certo che si riesca a sapere da una combinaizone la sua relativa posizione (come esempio in alto)

Il problema non si presentava se erano combinazioni semplici, e ragionando sui resti analogamente alla 1° soluzione si arrivava al risultato finale.

Il problema che mi pongo è sempre il seguente, ragionando per insiemi sappiamo che l'insime + grande e dato dall'universo 90x89x88/3! (ragiono col terno per semplicità di calcolo) quindi ipotizzando una divisone per ottere il suo resto uguale al inverse mode di questo:
combinazione 1-2-3

90-1 =89
90-2=88
90-3=87

89*88*87 / 3! = 113564 +
88*87 / 2! = 3828 +
87 / 1! = 87

= 117479

percui universo 117480 - 117479 = 1 che è la posione della combinazione 1-2-3


ora sto tentanto di percorrere la stada al contrario, e da giorni che mi applico.

[pigi76]

mi son registrato

cmq tonrando all'esempio di prima:

volgiamo sapere che combinazione occupa la posizione 1°

faremo 117480-1 = 117479

117479 / (un numero ed un quoziente che mi dia resto sottratto a 113564)
113564
----------------
3915

ecco questo è il tipo di ragionamento, ma dopo km e km di fogli e prove posso dire che non è la strada giusta da paercorrere.

torno a fare altre prove

[Admin]

Ritornando alla sommatoria
$\displaystyle \sum_{i=1}^{n} \frac{(90-i-1)(90-i)}{2}$;
cioè la somma dei primi n termini della serie
$\frac{89\cdot88}{2}+\frac{88\cdot87}{2}+\frac{87\cdot86}{2}+...+\frac{(90-n-1)\cdot(90-n)}{2}+...$

la soluzione si trova stesso sul forum, grazie agli interventi di Bruno e Leandro nel seguente topic: https://www.base5forum.it/viewtopic.php?t=351

pertanto avendo risolto con la sommatoria, provo ad andare avanti.

Admin

[Admin]

Dunque,
premetto che l'algoritmo che ho postato in primis è da accantonare in quanto prende in considerazione più volte le stesse combinazioni e quindi da luogo a risultati non corretti.

Per cui sono ripartito da zero;
per il momento ho trovato l'espressione che ci permette di ricavare il 1° numero della combinazione (ho preso in esame solo il caso di combinazioni di 3 numeri, ma il tutto è facilmente estendibile a 5 numeri o n numeri);

comincio a postare i passaggi relativi a questa espressione;

dunque le possibili combinazioni di 90 numeri in classe 3 sono, come già detto.

${{90}\choose3} =\frac{90!}{3!\,87!}=\frac{90\cdot89\cdot88}{3!}=117480$

ora il numero di combinazioni che cominciano con 1 ci è dato dalle combinazioni di 89 elementi in classe 2, ossia $\frac{89\cdot88}{2!}$;
invece, il numero di combinazioni che cominciano con 2, non ci sarà dato da $\frac{89\cdot88}{2!}$ in quanto le combinazioni che contengono 2 ed 1 sono già state tutte conteggiate nelle combinazioni che cominciano per 1;
per cui le combinazioni che cominciano per 2 ci sono date dalle combinazioni di 88 elementi in classe 2 ossia $\frac{88\cdot87}{2!}$;
procedendo allo stesso modo per le combinazioni che cominciano con 3, con 4,..., fino a 88 ottengono i seguenti risultati:

N° combinazioni del tipo $1-x-x\quad\Rightarrow\quad \frac{89\cdot88}{2!}$
N° combinazioni del tipo $2-x-x\quad\Rightarrow\quad \frac{88\cdot87}{2!}$
N° combinazioni del tipo $3-x-x\quad\Rightarrow\quad \frac{87\cdot86}{2!}$
$...$
$...$
N° combinazioni del tipo $88-x-x\quad\Rightarrow\quad \frac{2\cdot1}{2!}=1$

non vi saranno combinazioni che cominciano per 89 e 90 in quanto sono state tutte conteggiate nelle precedenti.

In pratica si può trovare una espressione in $n$, $F(n)$, tale che, uguagliata alla posizione, ci permette di ricavare il valore $n$.

è facile vedere dallo schema fatto sopra che, ad es. la posizione dell'ultima combinazione che inizia per 2 ci è data da $\frac{89\cdot88}{2!}+\frac{88\cdot87}{2!}$
allo stesso modo, la posizione dell'ultima combinazione che inizia per $n$ ci sarà data dalla somma
$\frac{89\cdot88}{2!}+\frac{88\cdot87}{2!}+\frac{87\cdot86}{2!}+...+\frac{(90-n)\cdot(90-n-1)}{2!}$

tale somma per un $n$ generico risulta uguale alle combinazioni totali, cioè 117480, meno la somma dei primi $c=88-n$ termini della serie

$\frac{1\cdot2}{2}+\frac{2\cdot3}{2}+\frac{3\cdot4}{2}+...+\frac{c\cdot(c+1)}{2}+...$

sulla base dei contributi di Bruno e Leandro nel topic che ho linkato,
tale serie può essere riscritta sommando i suoi membri due a due; si ottiene:
$\frac{8\cdot1}{2}+\frac{8\cdot2^2}{2}+\frac{8\cdot3^2}{2}+...+\frac{8\cdot(\frac{c}{2})^2}{2}$
da cui
$4\cdot\left(1+2^2+3^2+...+(\frac{c}{2})^2\right)$
Essendo la somma dei primi $n$ termini di una serie geometrica pari a $\frac{n(n+1)(2n+1)}{6}$, la somma è pari a:

$\displaystyle\4\cdot\frac{\frac{n}{2}(\frac{c}{2}+1)(2\frac{c}{2}+1)}{6}$
da cui, semplificando

$\frac{c(c+1)(c+2)}{6}$ con $c=88-n$

quindi la somma
$\frac{89\cdot88}{2!}+\frac{88\cdot87}{2!}+\frac{87\cdot86}{2!}+...+\frac{(90-n)\cdot(90-n-1)}{2!}$
sarà uguale a:

$117480-\frac{c(c+1)(c+2)}{6}$

per cui detta $p$ la posizione della combinazione che vogliamo calcolare si deve avere:

$117480-\frac{c(c+1)(c+2)}{6}=p$
da cui
$c(c+1)(c+2)=6\cdot(117480-p)$
in definitiva:
$c^3+3c^2+2c-6\cdot(117480-p)=0$

la soluzione di questa equazione, approssimata per difetto all'intero più vicino, ci da il valore di c; essendo $c=88-n$ il 1° numero della combinazione cercata ci è poi dato da $n=88-c$

L'equazione non è delle più semplice, ma meglio di questo non sono riuscito a fare.

Faccio un esempio semplice:

Voglio calcolare il primo numero della combinazione in posizione 3 (che chiaramente è 1);
abbiamo quindi $p=3$;
lo sostituiamo nella nostra equazione, ed otteniamo:
$c^3+3c^2+2c-6\cdot(117477)=0\quad\Rightarrow\quad c^3+3c^2+2c-704862=0$
a questo punto dobbiamo risolvere l'equazione (io l'ho fatto col computer, ma si può fare anche con una buona calcolatrice o con metodi approssimati)
si ottiene $c=87.99924248$;
approssimiamo per difetto ottenendo $c=87$;
da cui $n=88-c=88-87=1$.

Nei prossimi giorni provo per gli altri numeri.

Il tutto SE&O.

Ciao
Admin

[Admin]

Il procedimento da me postato per l'individuazione del 1° numero di una combinazione di posizione p è corretto;
però, a rigor di procedimento, deve essere $c=89-n$ e bisogna approssimare per eccesso e non per difetto.

E chiarò che ai fine dell'individuazione del 1° numero non cambia nulla.

Admin

[Admin]

Individuazione del 2° numero:

Partiamo dal valore $c$ ricavato dall'equazione relativa al primo numero ed approssimato per difetto all'intero più vicino.

(per evitare confusione indico con $\lceil c \rceil$ l'approssimazione per eccesso e con $\lfloor c \rfloor$ l'approssimazione per difetto di $c$)

Andiamolo a sostituire nella differenza

$d_2=117480-p-\frac{(\lfloor c \rfloor)(\lfloor c \rfloor+1)(\lfloor c \rfloor+2)}{6}$

Otteniamo quindi $d_2$.

Questo $d_2$ non è altro che il numero di combinazioni che vanno da quella in posizione $p$ all'ultima che comincia per $n$ (n è il primo numero trovato).

Ora vediamo come sono distribuite le combinazioni che iniziano con uno stesso numero (ad es. con 1):

N° comb. del tipo $1-2-x\quad\Rightarrow\quad 88$
N° comb. del tipo $1-3-x\quad\Rightarrow\quad 87$
N° comb. del tipo $1-4-x\quad\Rightarrow\quad 86$
$...$
$...$
N° comb. del tipo $1-88-x\quad\Rightarrow\quad 2$
N° comb. del tipo $1-89-x\quad\Rightarrow\quad 1$

ossia in generale,
N° comb. del tipo $1-n_2-x\quad\Rightarrow\quad 90-n_2$

Si vede chiaramente che il numero di combinazioni che vanno dalla 1° all'ultima dell'esempio è $1+2+...+88=\frac{88\cdot89}{2}$

in generale, il numero di combinazioni che vanno dalla 1° del tipo $1-n_2-x$ all'ultima dell'esempio (1-89-90) sono $\frac{(90-n_2)(90-n_2+1)}{2}=\frac{c_2\cdot(c_2+1)}{2}$
con $c_2=90-n_2$

uguagliando tale numero di combinazioni con la differenza $d_2$ possiamo ricavarci il valore di $n_2$;
si ha:

$d_2=\frac{c_2\cdot(c_2+1)}{2}$

ossia

$c_{\footnotesize2}^{\,2}+c_{\footnotesize2}-2\cdot d_2=0$

Risolvendo questa equazione si ottengono 2 valori per $c_2$;
consideriamo il positivo e lo approssiamiamo per eccesso all'intero più vicino;
ricordando che $c_2=90-n_2$ ci ricaviamo il valore di $n_2$ che costituisce il 2° numero della combinazione.

Faccio un esempio, riprendendo quello fatto per la determinazione del 1° numero;
per cui la posizione in esame è $p=3$;
abbiamo visto che $c=87.99924248$;
mentre per il calcolo del 1° numero ci siamo serviti di c approssimato per eccesso, per il calcolo del 2° ci serve approssimato per difetto;
andiamo a calcolare il secondo:
calcoliamo $d_2$

$d_2=117480-p-\frac{(\lfloor c \rfloor)(\lfloor c \rfloor+1)(\lfloor c \rfloor+2)}{6}=117480-3-\frac{87\cdot88\cdot89}{6}=117477-113564=3913$

ricaviamo $c_2$ dall'equazione

$c_{\footnotesize2}^{\,2}+c_{\footnotesize2}-2\cdot 3913=0\quad\Rightarrow\quad c_{\footnotesize2}^{\,2}+c_{\footnotesize2}-7826=0$

la soluzione positiva è: $c_2=87.96609520$
approssiamiamo per eccesso all'intero più vicino: $\lceil c_2 \rceil =88$
essendo $c_2=90-n$, si ha $n_2=90-\lceil c_2 \rceil=2$.

Il secondo numero della combinazione in posizione $p=3$ è $2$.

Individuazione del 3° numero:

Il procedimento è analogo a quello per il 2° numero, ma più semplice;

si calcola anzitutto la differenza

$d_3=d_2-\frac{(\lfloor c_2 \rfloor)(\lfloor c_2 \rfloor+1)}{2}$

a questo punto il 3° numero della combinazione ci è dato da
$n_3=90-d_3$

Per cui sempre continuando il nostro esempio si ha $p=3$, $d_2=3913$ e $\lfloor c_2 \rfloor=87$ da cui

$d_3=3913-\frac{87\cdot88}{2}=3913-3828=85$
quindi
$n_3=90-d_3=90-85=5$

il 3° numero della combinazione di posizione $p=3$ è $5$.

Esempio generale per il calcolo dei 3 numeri:

vogliamo trovare la combinazione di 3 numeri di posizione 8790.

$p=8790$

consideriamo l'equazione $c^3+3c+2c-6\cdot(117480-p)=0$
sostituendo $p$ si ottiene:
$c^3+3c^2+2c-652140=0$
la cui soluzione è $c = 85.72271442$
da cui $n_1=89-\lceil c \rceil=3$
Il 1° numero è $3$.

ora calcoliamo $d_2$

$d_2=117480-p-\frac{(\lfloor c \rfloor)(\lfloor c \rfloor+1)(\lfloor c \rfloor+2)}{6}=117480-8790-\frac{85\cdot86\cdot87}{6}=108690-105995=2695$

consideriamo l'equazione $c_{\footnotesize2}^{\,2}+c_{\footnotesize2}-2\cdot d_2=0$
sostituendo $d_2$ si ottiene:

$c_{\footnotesize2}^{\,2}+c_{\footnotesize2}-5390=0$
la cui soluzione positiva è $c_2 = 72.91832196$
quindi
$n_2=90-\lceil c_2 \rceil=90-73=17$
il 2° numero è $17$.

ora calcoliamo $d_3$:

$d_3=d_2-\frac{(\lfloor c_2 \rfloor)(\lfloor c_2 \rfloor+1)}{2}=2695-\frac{72\cdot73}{2}=2695-2628=67$
quindi
$n_3=90-d_3=90-67=23$

il 3° numero è $23$.

Quindi la combinazione di posizione $8790$ è $3-17-23$.

Per verificare se ciò è vero ci vorrebbe un programmino che elenchi tutte le combinazioni; se hai già una lista fammi sapere se tale risultato è corretto;
altrimenti faccio il programmino.

Il tutto SE&O

Ciao
Admin

[Admin]

sto cercando di estendere l'algoritmo al caso di combinazioni di 5 numeri;
(penso che si ha a che fare con equazioni di 5° grado)

in ogni caso, mi sono bloccato di nuovo di fronte ad una sommatoria;
questa volta, la sommatoria è la seguente:

$\sum_{i=1}^{c} \frac{i\cdot(i+1)\cdot(i+2)\cdot(i+3)}{4!}$

ossia la somma dei primi $c$ termini della serie

$\frac{1\cdot2\cdot3\cdot4}{4!}+\frac{2\cdot3\cdot4\cdot5}{4!}+...+\frac{c\cdot(c+1)\cdot(c+2)\cdot(c+3)}{4!}+...$

quanto vale?

Ciao
Admin

[giobimbo]

Nel suo secondo intervento pigi76 dava una formula con cui ricavare la posizione date le combinazioni, dimenticando però di dire che il numero così ottenuto dev'essere sottratto da 117.490, il numero della combinazione 88-89-90. Mettendo la combinazione 3-17-23 in tale formula si ottiene (105.995 + 2.628 + 67), che sottratto da 117.490 dà appunto 8.790. Bravo Pietro!

Mettendo delle incognite nella formula mi era parso appunto di capire che nella conversione fosse coinvolta un'equazione di quinto grado, il che rende il problema di pigi76 complicato da risolvere. Mi domando se non sia meglio cercare piuttosto di cambiare il modo di codificare le combinazioni...