Newsgroup: it.comp.lang.c
Titolo: combinazioni

Quale e' l'indice di una combinazione di simboli?
Ossia: dati n elementi presi k a k, essi sviluppano comb(n, k) combinazioni.
Ad esempi ocon n=8 e k=3 avrei in ordine: 1-2-3, 1-2-4, 1-2-5,.... 2-3-4,
2-3-5, ..., 6-7-8.
Il problema e' data la combinazione c[i] trovare l'indice i nello sviluppo
(quindi la pos. di 1-2-5 deve essere 3).
Ho risolto momentaneamente con una formula ricorsiva, che fa piu' o meno
cosi':
int     posizione(char c[3], int n, int m)
{
int     p;
char    old;
char    c1[3], c2[3];
        c1[0] = c[0];
        c1[1] = c[1];
        c1[2] = c[2];
        if (m == 1)
                return (int)c[0];
        p = 0;
        old = c[0];
        while (c1[0] > 1)
        {
                p += combinazioni[n - c1[0] + 1][m - 1];
                c1[0]--;
        }
        c2[0] = c[1] - old;
        c2[1] = c[2] - old;
        return p + posizione(c2, n - old, m - 1);
}
La chiamata e' con posizione(c, n, k) se ho n simboli presi k a k, e la
funzione restituisce l'indice nello sviluppo (combinazioni e' un vettore
precalcolato, dal significato ovvio).
Il problema e' che al salire di n e k questa soluzione e' troppo lenta,
anche se cosi' non rischio di mandare in overflow le variabili (sono solo
somme fino al valore desiderato).
C'e' un modo meno stupido (e piu' veloce) di realizzare questa funzione?
Grazie,
Marco


Io non sono un esperto, perň nell'esempio che hai fatto non sembrano
combinazioni ma disposizioni con l'aggiunta della condizione c[n]>c[n+1]
.... giusto?
Per quanto ne so nelle combinazioni č possibile avere [1,1,1] e nelle
disposizioni, dopo [1,2,8] dovrebbe esserci [1,3,2] (se non [1,3,4] o
[2,3,1] o[2,1,3] .... , ma qui la cosa si complica)  .... mi piacerebbe
aiutarti perň č essenziale capire cosa intendi per 'combinazioni' e i
criteri dello sviluppo.
La cosa si potrebbe chiarire studiando la funzione che hai scritto perň č
piů semplice se descrivi meglio i termini del problema.
Ciao.
_sng_

.... giusto?
Forse dall'esempio non si capiva, ma mi sembra siano proprio combinazioni.
Per fare l'esempio chiarificatore prendi lo sviluppo delle colonne al
totogol: quelle sono combinazioni. Immagina un totogol dove devi indovinare
3 partite invece di 8 e ottieni quello di cui parlavo io.
Le colonne al totocalcio invece sono disposizioni (con ripetizione).
Marco

 wrote in message
7nul7v$l7r$1...@nslave1.tin.it...

Hai ragione sono combinazioni.
Ti chiedo scusa ...
L'esempio era giusto.
Immagino che nello sviluppo tu proceda sempre variando per prime le
posizioni che stanno a destra, cioè per n=8 e k=3  :
123...128,134...138,145...148.......234.......678
Purtroppo al momento non saprei che algoritmo usare per velocizzare la
ricerca dell'indice.
Se non hai problemi di memoria e su ogni insieme devi fare un numero
significativo di ricerche dell'indice, potresti memorizzare gli indici in
un'array i cui indici sono le combinazioni ... del tipo:
iCmb[123]=1;...;iCmb[134]=7; ecc...
Certo, la memoria occupata dall'array sarebbe solo parzialmente utilizzata
però in questo modo otterresti l'indice in modo praticamente istantaneo ....
Come sempre o si spende in memoria o in tempo di calcolo.
Se trovo un compromesso migliore te le faccio sapere.
Ciao.
_sng_