[C] Tutte le possibili combinazioni...

[fracarro]

Salve ragazzi. Ho i soliti problemini con gli insiemi e chiedo a voi esperti un aiuto. Allora il problema è questo. Supponiamo di avere una matrice con due righe e tre colonne e i numeri da 1 a 5. Ogni colonna della matrice lo possiamo vedere come uno stack e gli elementi vanno quindi inseriti dal basso verso l'alto.
Vorrei scrivere una funzione iterativa che inserisce nelle 6 caselle a disposizione i 5 numeri dati in tutti i modi possibili (con l'unico vincolo che quando inserisco un elemento in una cella, le celle sottostanti devono essere già riempite). Per esempio:

conf1 conf2 conf3
4 5 4 5 2 4
1 2 3 1 2 3 1 3 5 .....

sono tutte configurazioni valide mentre:

no conf!
3 4 5
1 2

non lo è perchè al di sotto del 5 la cella è vuota.

Non mi interessa la complessità della funzione (che ovviamente è esponenziale) ma solo che mi dia tutti i possibili modi di inserire gli elementi dati nelle caselle a disposizione. Avete idea di come scrivere questa funzione?

[x3d0]

Ciao, ti ho caricato un pdf con un pò di teoria.

http://www.wikiupload.com/download_page.php?id=131089

[gugoXX]

Ipotizza di partire con un insieme di 4 elementi, ovvero 1,2,3,4 (non ne metto 5 come te perche' 5+1 e' gia' il numero delle celle, e si rischia di fare confusione). Potrebbe anche essere 7 o 50, non cambia nulla.

Aggiungi all'insieme l'elemento vuoto, quello che identifichera' nella tua suoluzione la mancanza di un elemento. Ipotizzo lo 0.
Avrai quindi 0,1,2,3,4.
L'insieme ha lunghezza 5.

Effettua l'enumerazione di tutte le disposizioni con ripetizione tra tutti gli elementi del tuo insieme sulle celle possibili, nel tuo esempio 6.

Per fare l'enumerazione di tutte le disposizioni con ripetizione e' sufficiente contare da 0 fino a 6^5, in base 6
(Ovvero 6 loop annidati, oppure un looppone e 6 operazioni di modulo, oppure altro)

Ad ogni iterazione avrai quindi 6 elementi, che saranno da considerare ordinati come sulla tua matricetta 2x3.
Il primo sara' l'elemento (0,0), il secondo l'elemento (0,1), il terzo (1,0) poi (1,1) poi (2,0) e ultimo l'elemento (2,1)

Poi filtra l'enumerazione con il tuo criterio, ovvero che se la cella (0,0) sara' diversa da 0, allora la cella (0,1) non potra' essere 0
cosi' anche per la seconda colonna, la terza, etc.

Finito...

Partirai quindi con il primo risultato che avra' tutti 0, fino all'utlimo che avra' tutti 4

0 0 0
0 0 0

0 0 0
0 0 1

0 0 0
0 0 2

...


4 4 4
4 4 4

[fracarro]

Originariamente inviato da x3d0

Ciao, ti ho caricato un pdf con un pò di teoria.

http://www.wikiupload.com/download_page.php?id=131089

Originariamente inviato da gugoXX

Ipotizza di partire con un insieme di 4 elementi, ovvero 1,2,3,4 (non ne metto 5 come te perche' 5+1 e' gia' il numero delle celle, e si rischia di fare confusione). Potrebbe anche essere 7 o 50, non cambia nulla.

Aggiungi all'insieme l'elemento vuoto, quello che identifichera' nella tua suoluzione la mancanza di un elemento. Ipotizzo lo 0.
Avrai quindi 0,1,2,3,4.
L'insieme ha lunghezza 5.

Effettua l'enumerazione di tutte le disposizioni con ripetizione tra tutti gli elementi del tuo insieme sulle celle possibili, nel tuo esempio 6.
....
[/code]

Grazie dell'aiuto ragazzi.

gugoXX c'è qualcosa che non mi torna nella tua soluzione. Allora, la soluzione con tutti zeri o tutti 4 non sono soluzioni valide perchè date le 6 celle che stiamo considerando io devo metterci dentro gli elementi dell'insieme in tutti i modi possibili ma senza ripetere elementi. Quindi se per esempio abbiamo gli elementi da 1 a 4 su una matrice con le solite sei caselle, avrei soluzioni valide come:

4
1 2 3

4
1 2 3

2
1 4 3 ......................

Ma una soluzione di questo tipo:

4 2
1 2 3 non va bene perchè ripete lo stesso elemento due volte.

Attualmente credo che il modo più semplice di scrivere questo codice consiste nell'utilizzare due funzioni. Una che mi calcola tutti i possibili sottoinsiemi di dimensione k di un dato insieme di n elementi, chiamiamola subset(n,k) e un'altra che invece calcola tutte le possibili permutazioni di un insieme, diciamo perm(n). Date queste due funzioni, io procederei per livelli ossia parto dall'ultima riga della matrice e proseguo a salire. Sull'ultima riga mi faccio restituire tutti i sottoinsiemi di dimensione k(numero di colonne) ricavabili dall'insieme originale n. Per ognuno di questi sottoinsiemi calcolo poi tutte le possibili permutazioni. Dopodichè passo al livello superiore dove avrò k elementi in meno e riappricherò le due funzioni. Credo che in questo modo riuscirò ad ottenere tutte le possibili combinazioni. Voi che dite?

[gugoXX]

Originariamente inviato da fracarro

Grazie dell'aiuto ragazzi.

gugoXX c'è qualcosa che non mi torna nella tua soluzione. Allora, la soluzione con tutti zeri o tutti 4 non sono soluzioni valide perchè date le 6 celle che stiamo considerando io devo metterci dentro gli elementi dell'insieme in tutti i modi possibili ma senza ripetere elementi.

Bene.
Cioe' male, nel senso che allora il tuo primissimo esempio ha qualcosa che non va.

Comunque per farla facile e non dover scrivere la funzione subset, puoi condire il precedente algoritmo con anche il filtro
"e che nessuna cella contenga un valore uguale a nessuna altra cella"
Se vuoi posso provare a buttare giu' qualcosa in C# pero'...

[fracarro]

Originariamente inviato da gugoXX

Bene.
Cioe' male, nel senso che allora il tuo primissimo esempio ha qualcosa che non va.

Comunque per farla facile e non dover scrivere la funzione subset, puoi condire il precedente algoritmo con anche il filtro
"e che nessuna cella contenga un valore uguale a nessuna altra cella"
Se vuoi posso provare a buttare giu' qualcosa in C# pero'...

Sei molto gentile, ma non disturbarti. Mi bastano le soluzioni teoriche che mi date (poi cerco di tradurle in codice io, inoltre non conosco il C# e devo scrivere questo codice in C/C++).

Ora provo con la mia soluzione e se nn va cerco di applicare la tua modificata. Se non ce la faccio torno qui a chiedere aiuto.

Grazie ancora.

[fracarro]

Ho trovato un codice su internet breve e credo utile perchè permette sia la generazione di tutte le permutazioni possibili di un insieme sia l'individuazione di tutti i sottoinsiemi di una certa dimensione a partire da un insieme dato. Lo posto qui sotto sperando possa servire a qualcun'altro:

/*
    genset.c

    This program generates all size-k subsets
    in a set of size n.  The subset is either
    ordered or unordered depending on the mode:

        "permutation" mode is ordered
        "combination" mode is unordered

    Command-line usage for generating permutations:

        genset p [k] [n]

    Command-line usage for generating combinations:

        genset c [k] [n]
*/

#include <stdio.h>
#include <stdlib.h>

static void swap(unsigned *set, unsigned i, unsigned j)
    {
    unsigned temp = set[i];
    set[i] = set[j];
    set[j] = temp;
    }

static void display(unsigned *set, unsigned k)
    {
    unsigned i;
    printf("{ ");
    for (i = 0; i < k; i++)
        printf("%u ", set[i]);
    printf("}\n");
    }

static int in_order(unsigned *set, unsigned k)
    {
    int result = 1;
    if (k > 0)
        {
        unsigned i;
        for (i = 0; i < (k-1); i++)
            if (set[i] > set[i+1])
                {
                result = 0;
                break;
                }
        }
    return (result);
    }

static void visit(char mode, unsigned *set, unsigned k, unsigned n, unsigned
start)
    {
    if (start < k)
        {
        unsigned i;
        for (i = start; i < n; i++)
            {
            swap(set, start, i);
            visit(mode, set, k, n, start+1);
            swap(set, start, i);
            }
        }
    else
        {
        if ((mode == 'p') || ((mode == 'c') && in_order(set, k)))
            {
            display(set, k);
            }
        }
    }

int main(unsigned argc, const char * const *argv)
    {
    unsigned  k = 4;       /* the size of the desired subset */
    unsigned  n = 0;       /* the size of the whole set (defaults to k) */
    unsigned *set = NULL;  /* the whole set */
    char      mode = 'p';  /* 'p' (permutation) or 'c' (combination) */
    unsigned  i;

    if (argc > 1) mode = argv[1][0];
    if (argc > 2) k = atoi(argv[2]);
    if (argc > 3) n = atoi(argv[3]); else n = k;

    if ((mode == 'p') || (mode == 'c'))
        {
        set = (unsigned *)malloc(n * sizeof(unsigned));
        for (i = 0; i < n; i++) set[i] = i;
        visit(mode, set, k, n, 0);
        free(set);
        }
    else
        printf("illegal mode\n");

    return (0);
    }