Help si Numerare le combinazioni, algortmo.

[delfo52]

anche a me appaiono tante crocette rosse.
credevo fossero una nuova forma di arte concettuale.
adesso ho scoperto che se ne può far uscire immagini e formule...
Magia !!!
Lo strano è che alcune formule sono si scoprono da sole; altre devo fare clik.
Mistero !!!

[Admin]

Pasquà, grazie per i complimenti!

Per quanto riguarda le crocette, il problema è sempre quello che si è presentato tempo fa;
in questi mesi mi è sembrato di capire che le crocette nascono dal fatto che lo script cgi che converte le formule in immagini, non riesce a mantenersi in esecuzione per tutta la durata del caricamento della pagina (per dirla con un'espressione locale non "accivisce" a convertire formule in immagini e si blocca;(ciò dipende, penso, dalle risorse limitate dell'account di TopHost) quello che è riuscito a convertire resta, l'altro sono crocette)

in pratica, recentemente ho introdotto l'utilizzo della cache per le immagini tex;
ciò vuol dire che le formule tex non vengono convertite in immagine ogni volta che un utente apre la pagina, ma vengono convertite in immagini una volta sola e si depositano in una cartella dell'account ("cache");
quindi se un altro utente apre la pagina, lo script cgi del tex non viene proprio avviato, e le immagini delle formule tex vengono semplicemente caricate dalla "cache" (tranne se si è fatta qualche modifica alle formule o ci sono nuovi post con formule);
l'utilizzo della cache ha permesso una riduzione drastica delle crocette, che tuttavia non sono scomparse del tutto;

infatti quando un topic è particolarmente lungo e pieno zeppo di formule, può capitare che qualche formula non sia ancora in cache (nel senso che non è stata ancora aperta da nessuno o che è stata modificata di recente); se tale formula si trova in un post che a sua volta si trova in fondo al topic, prima che lo script la converta in immagine c'è bisogno che si carichi tutto quello che viene prima nella pagina; lo script non ce la fa a restare in esecuzione per tutto il tempo e si hanno le crocette.

Almeno questa è l'idea che mi sono fatto;
perchè di certo c'è ben poco, visto che TopHost mi ha dato solo spiegazioni "vaghe".

In ogni caso, come già detto in passato, con Mozilla Firefox si vedono tutte le formule e non si vede alcuna crocetta (almeno a me);
infatti Mozilla visualizza immediatamente tutta la pagina, con il testo, e poi pian piano si carica le immagini;
in tal modo il testo della pagina è già presente e può essere letto, poi man mano vengono caricate le immagini dalla cache e nello stesso tempo lo script converte le formule che non sono in cache;
probabilmente anche con Firefox si possono avere delle crocette, ma per il momento non mi è mai capitato.

Altra cosa:

è bene sempre fare una anteprima di un messaggio con formule prima di inviarlo;
perchè in tal caso le formule vengono convertite in immagini dallo script e vanno già in cache ancor prima di inviare il messaggio.

Comunque, mi sembra che, se non per topic lunghi e con molte formule, anche con Explorer non si hanno crocette;

Confermate?

Ciao
Admin

[Admin]

Ho provato ora a vedere con explorer questo post, e si vede bene;
nessuna crocetta;

fatemi sapere...

Ciao
Admin

[Pasquale]

Veramente io le crocette le vedo anche a posto del tasto modifica, oppure spesso se premo il tast modifica, si apre la finestra a metà, cioè si apre quella per l'mmissione del testo, ma non quella con i tasti dell'anteprima/invia.
Forse bisognerebbe cercare di inserire pochi TEX e accorciare gli interventi (parlo proprio io!)

[Admin]

Allora, c'è qualche altro problema oltre il quantitativo di formule tex, perchè a me i tasti compaiono sempre.

Comunque molto dipende anche dal fatto che abbiamo un 56K;
fortunatamente devo penare ancora per poco;
a Settembre posso ADSLizzarmi anch'io.

In ogni caso, il Tex è stato introdotto per essere utilizzato e migliorare la leggibilità di un post;
il problema è che deve funzionare correttamente;
ho provato negli ultimi mesi altre soluzioni alternative, solo che il sistema della cache sembrava funzionare correttamente (almeno a me non ha mai dato problema) pur sapendo che il problema di fondo restava.

Nei prossimi giorni faccio dei test con altri account, per l'esecuzione dello script cgi.

Admin

[Pasquale]

Già, però c'è solo un problema: questi inconvenienti li noto nonostante la mia ADSL a 4Mega (in ricezione) e 1 Giga di memoria RAM; sarà che dipenda da qualche settaggio del Browser? Perché se premo con il tasto destro "Mostra Immagine", subito compare? Però non è che non mi compare nessuna immagine: alcune si ed altre no. Sarà che sul p.c. ci sono un casino di programmi che lavorano in background, che nemmeno lo sai e ti limitano le possibilità?
Ragazzi, studiate e trovate la soluzione.

[pigi76]

ciao a tutti, sono stato un po assente in questi giorni e vedo che avete fatto notevoli progressi...

admin mi potresti fare un esempio con numeri reali? tipo ad esempio alla posizione 1000000 che combinazione abbiamo?

grazie in adv

[Admin]

Mi sono ora accorto di aver mancato alcuni passaggi essenziali nell'algoritmo generalizzato (a breve vado ad aggiornare i messaggi relativi all'algoritmo);
intanto riporto qui l'algoritmo generalizzato completo:

• Passo 1 (id=1):
  
  $d_{\small1}={90 \choose k}-p$
  conoscendo $p$ ed $k$ ci ricaviamo $d_{\small1}$.
  
  $d_{\small1}={c_{\small1}+k-1 \choose k}$
  conoscendo $d_{\small1}$ ci ricaviamo $c_{\small1}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small1}\rceil$);
  
  il 1° numero della combinazione è $n_{\small1}=90-k+id+1-\lceil c_{\small1}\rceil$ (l'id è il numero del passo)
• Passo 2 (id=2):
  
  $d_{\small2}=d_{\small1}-{\lfloor c_{\small1} \rfloor+k-1 \choose k}$
  conoscendo $d_{\small1}$ e $c_{\small1}$ e $k$ ci ricaviamo $d_{\small2}$;
  
  $d_{\small2}={c_{\small2}+k-2 \choose k-1}$
  conoscendo $d_{\small2}$ ed $k$ ci ricaviamo $c_{\small2}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small2}\rceil$);
  
  il 2° numero della combinazione è $n_{\small2}=90-k+id+1-\lceil c_{\small2}\rceil$
• Passo ...:
  
  ...
• Passo k-1 (id=k-1):
  
  $d_{\small k-1}=d_{\small k-2}-{\lfloor c_{\small k-2} \rfloor+2 \choose 3}$
  
  conoscendo $c_{\small k-2}$ e $d_{\small k-2}$ e $k$ ci ricaviamo $d_{\small k-1}$;
  
  $d_{\small k-1}={c_{\small k-1}+1 \choose 2}$
  
  conoscendo $d_{\small k-1}$ ci ricaviamo $c_{\small k-1}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small k-1}\rceil$);
  
  il (k-1)-numero della combinazione è $n_2=90-\lceil c_{\small k-1}\rceil$
• Passo k (id=k):
  
  $d_{\small k}=d_{\small k-1}-{\lfloor c_{\small k-1} \rfloor+1 \choose 2}$
  
  conoscendo $c_{\small k-1}$ e $d_{\small k-1}$ ed $k$ ci ricaviamo $d_{\small k}$;
  
  il k-esimo numero della combinazione ci è dato da $n_{\small k}=90-d_{\small k}$.

Ora, supponiamo di avere 90 elementi e combinazioni di 5 elementi;
vogliamo sapere la combinazione in posizione 100000;

quindi si ha $n=5$ e $p=1000000$;

L'algoritmo consta di 5 passi:
----------------------------------------------------------------------------------------

• Passo 1 (id=1):
  
  $d_{\small1}={90 \choose k}-p$
  conoscendo $p$ ed $k$ ci ricaviamo $d_{\small1}$.
  
  $d_{\small1}={c_{\small1}+k-1 \choose k}$
  conoscendo $d_{\small1}$ ci ricaviamo $c_{\small1}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small1}\rceil$);
  
  il 1° numero della combinazione è $n_{\small 1}=90-k+id+1-\lceil c_{\small1}\rceil$

Nel nostro caso, $d_{\small1}={90 \choose 5}-1000000=\frac{90\cdot 89\cdot 88\cdot 87\cdot 86}{5!}-100000=43949268-1000000=42949268$

Quindi $42949268={c_{\small1}+4 \choose 5}$

da cui $42949268=\frac{(c_{\small1}+4)(c_{\small1}+3)(c_{\small1}+2)(c_{\small1}+1)c_{\small1}}{5!}$

la soluzione di tale equazione è (si deve utilizzare il PC o una buona calcolatrice; a mano non si fa niente): $c_{\small1}=85.59594757$;

approssimiamo per eccesso: $\lceil c_{\small1}\rceil=86$;
il 1° numero della combinazione è $n_{\small 1}=90-5+1+1-86=1\quad\Rightarrow\quad n_{\small 1}=1$;

• Passo 2 (id=2):
  
  $d_{\small2}=d_{\small1}-{\lfloor c_{\small1} \rfloor+k-1 \choose k}$
  conoscendo $d_{\small1}$ e $c_{\small1}$ e $k$ ci ricaviamo $d_{\small2}$;
  
  $d_{\small2}={c_{\small2}+k-2 \choose k-1}$
  conoscendo $d_{\small2}$ ed $k$ ci ricaviamo $c_{\small2}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small2}\rceil$);
  
  il 2° numero della combinazione è $n_{\small2}=90-k+id+1-\lceil c_{\small2}\rceil$

Nel nostro caso, si ha $d_{\small2}=42949268-{85+4 \choose 5}=42949268-\frac{89\cdot 88\cdot 87\cdot 86\cdot85}{5!}=42949268-41507642=1441626$

Quindi $1441626={c_{\small2}+3 \choose 4}$

da cui $1441626=\frac{(c_{\small2}+3)(c_{\small2}+2)(c_{\small2}+1)c_{\small2}}{4!}$

la soluzione di tale equazione è: $c_{\small2}=75.20295685$;

approssimiamo per eccesso: $\lceil c_{\small2}\rceil=76$;
il 2° numero della combinazione è $n_{\small 2}=90-5+2+1-76=12\quad\Rightarrow\quad n_{\small 2}=12$;

• Passo 3 (id=3):
  
  $d_{\small 3}=d_{\small 2}-{\lfloor c_{\small 2} \rfloor+k-2 \choose k-1}$
  
  conoscendo $c_{\small 2}$ e $d_{\small 2}$ e $k$ ci ricaviamo $d_{\small 2}$;
  
  $d_{\small 3}={c_{\small 3}+k-3 \choose k-2}$
  
  conoscendo $d_{\small 3}$ ci ricaviamo $c_{\small 3}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small 3}\rceil$);
  
  il 3° numero della combinazione è $n_{\small3}=90-k+id+1-\lceil c_{\small 3}\rceil$

Nel nostro caso, si ha $d_{\small3}=1441626-{75+3 \choose 4}=\frac{78\cdot 77\cdot 76\cdot 75}{4!}=1441626-1426425=15201$

Quindi $15201={c_{\small3}+2 \choose 3}$

da cui $15201=\frac{(c_{\small2}+2)(c_{\small2}+1)c_{\small2}}{3!}$

la soluzione di tale equazione è: $c_{\small2}=44.02073459$;

approssimiamo per eccesso: $\lceil c_{\small2}\rceil=45$;
il 2° numero della combinazione è $n_{\small 2}=90-5+3+1-45=44\quad\Rightarrow\quad n_{\small 2}=44$;

• Passo 4 (id=4):
  
  $d_{\small 4}=d_{\small 3}-{\lfloor c_{\small 3} \rfloor+k-3 \choose k-2}$
  
  conoscendo $c_{\small 3}$ e $d_{\small 3}$ e $k$ ci ricaviamo $d_{\small 4}$;
  
  $d_{\small 4}={c_{\small 4}+k-4 \choose k-3}$
  
  conoscendo $d_{\small 4}$ ci ricaviamo $c_{\small 4}$;
  lo approssimiamo per eccesso all'intero più vicino ($\lceil c_{\small 4}\rceil$);
  
  il 4° numero della combinazione è $n_{\small4}=90-k+id+1-\lceil c_{\small 4}\rceil$

Nel nostro caso, si ha $d_{\small4}=15201-{44+2 \choose 3}=\frac{46\cdot 45\cdot 44}{3!}=15201-15180=21$

Quindi $21={c_{\small4}+1 \choose 2}$

da cui $21=\frac{(c_{\small4}+1)c_{\small4}}{2!}$

la soluzione di tale equazione è: $c_{\small4}=6$;

approssimiamo per eccesso: $\lceil c_{\small2}\rceil=7$;
il 4° numero della combinazione è $n_{\small 4}=90-5+4+1-7=83\quad\Rightarrow\quad n_{\small 4}=83$;

• Passo 5 (id=5):
  
  $d_{\small 5}=d_{\small 4}-{\lfloor c_{\small 4} \rfloor+k-4 \choose k-3}$
  
  conoscendo $c_{\small 4}$ e $d_{\small 4}$ e $k$ ci ricaviamo $d_{\small 5}$;
  
  il 5° numero della combinazione ci è dato da $n_{\small 5}=90-d_{\small 5}$.

Nel nostro caso, si ha $d_{\small5}=21-{6+1 \choose 2}=\frac{7\cdot 6}{2!}=21-21=0$ (da notare che l'approssimazione per difetto non viene effettuata se il numero in esame è già intero (per questo 6 resta 6))

Quindi il 5° numero della combinazione ci è dato da $n_{\small 5}=90-0=90\quad\Rightarrow\quad n_{\small 5}=90$

In definitiva, la combinazione in posizione $1000000$ è $1-12-44-83-90$.

Possiamo verificare la correttezza del risultato utilizzando la seguente formula:

${90 \choose k}-\displaystyle\sum_{i=1}^{k}{90-n_i \choose k-i+1}$

che restituisce la posizione a partire dalla combinazione.
(come già detto tale formula è la generalizzazione della formula da te postata per il caso specifico di combinazioni di 3 numeri)

Nel nostro caso si ha:

${90 \choose 5}-\displaystyle\sum_{i=1}^{5}{90-n_{\small i} \choose 5-i+1}\quad\Rightarrow\quad {90 \choose 5}-{90-n_{\small1} \choose 5}-{90-n_{\small2} \choose 4}-{90-n_{\small3} \choose 3}-{90-n_{\small4} \choose 2}-{90-n_{\small5} \choose 1}$

${90 \choose 5}-{90-1 \choose 5}-{90-12 \choose 4}-{90-44 \choose 3}-{90-83 \choose 2}-{90-90 \choose 1}=\\43949268-41507642-1426425-15180-21-0=1000000$

Purtroppo l'algoritmo non è il massimo, però ha una buona "manuabilità";
se invece si vuole realizzare un programma per PC, allora l'algoritmo concentrato di Pasquale è sicuramente migliore.

A tal proposito ho ultimato il "programmino" in java che calcola la combinazione a partire dalla posizione e viceversa; più altri calcoli vari.

Domani lo posto.

Ciao
Admin

[Admin]

Bene,
ho terminato il programmino in java per il calcolo di posizioni, combinazioni ed altro.

Ci sono dei bug che si verificano con numeri troppo grandi, ma in linea di massima funziona.

Questo è uno screenshot:



e questo è il link da cui poterlo scaricare:

https://www.base5forum.it/upload/CombinationN.zip

Scompattate lo zip, e cliccate su run.bat per avviare il programma.
N.B.: bisogna avere installata la Java Virtual Machine.

Se non ce l'avete (se il prog. non parte quasi sicuramente è così), potete scaricarla da qui:

http://www.java.com/it/download/index.jsp



Ciao
Admin

[Pasquale]

Senz'altro i bug saranno dovuti all'approssimazione dei numeri a partire da una certa lunghezza.

[pigi76]

Admin se non ti fa fatica potresti spiegarmi come hai risolto al pc questa equazione: $42949268=\frac{(c_{\small1}+4)(c_{\small1}+3)(c_{\small1}+2)(c_{\small1}+1)c_{\small1}}{5!}$ ?

Anche un esempio manuale mi andrebbe bene.
Sto cercando di ricavare una formula che un tempo avevo e che era basata sulla divisione con resto, magari ricordando qualche passaggio da quella equazione mi torna in mente...
grazie

[Admin]

Admin se non ti fa fatica potresti spiegarmi come hai risolto al pc questa equazione: $42949268=\frac{(c_{\small1}+4)(c_{\small1}+3)(c_{\small1}+2)(c_{\small1}+1)c_{\small1}}{5!}$?

semplicemente ho utilizzato un programma di calcolo, nella fattispecie 'Derive 6';
ce ne sono molti altri, anche freeware; se fai una ricerca in rete li trovi.

Tuttavia, visto che comunque si deve utilizzare il PC, potresti utilizzare il mio programmino per calcolare direttamente le posizione a partire dalla combinazione, oppure il contrario, oppure per visualizzare tutte le combinazioni (o quasi).

A questo punto, mi incuriosisce sapere la finalità per cui ti serve il procedimento;
ti serve come algoritmo da implementare in qualche linguaggio di programmazione?
o altro?

Sono curioso...
sempre se non sono indiscreto.

Ciao
Admin

[pigi76]

Mi sever per un programmino per il lotto che sto cercando di realizzare, dove in base alla posizione mi ricavo una statistica sui numeri, tutto qui.
Il tuo programma è ottimo, ma mi servirebbe una function rimplementabile all'interno del mio altrimenti non potrei interagire con esso.

scusa l'attesa, ma nel frattempo son diventato papà

saluti

[Bruno]

(...) scusa l'attesa, ma nel frattempo son diventato papà

...congratulazioni vivissime, Pigi!

[Admin]

scusa l'attesa, ma nel frattempo son diventato papà

mille di queste attese!
Auguri!

Dunque, che linguaggio di programmazione utilizzi?
il programmino l'ho realizzato in java, per cui se ti va bene il codice java, ti posto il codice della funzione;

quale funzione ti serve esattamente?

Ciao
Admin