Calcolare combinazioni di elementi

[Ilgard]

Salve a tutti, sto cercando da tutto il giorno di scrivere un programma che calcoli le combinazioni possibili di un certo numero di elementi. Avrei detto fosse banale, invece non riesco a trovare una soluzione
Per fare un esempio, se ho un array del tipo {a,b,c} voglio ottenere questi risultati: a; b: c; ab; ac; bc; abc.
Qualche idea?

[gila75]

Salve a tutti, sto cercando da tutto il giorno di scrivere un programma che calcoli le combinazioni possibili di un certo numero di elementi.

Il calcolo è il fattoriale 5=5*4*3*2*1=120 combinazioni.
Su come fare non ricordo, ne avevo parlato in una discussione, ma non ricordo.
Prova a vedere in rete gli anagrammi , magari in modo indiretto arrivo all'algoritmo (teorico, non in c) per le combinazioni.
Poi lo adatti al C

[gila75]

Mi è venuto in mente guarda qui :
http://it.wikipedia.org/wiki/Permutazione

[crap0101]

Salve a tutti, sto cercando da tutto il giorno di scrivere un programma che calcoli le combinazioni possibili di un certo numero di elementi.

Il calcolo è il fattoriale 5=5*4*3*2*1=120 combinazioni.

uhm no, quelle sono le permutazioni.

Per fare un esempio, se ho un array del tipo {a,b,c} voglio ottenere questi risultati: a; b: c; ab; ac; bc; abc.
Qualche idea?

tu come l'hai impostato? a vedere da come scrivi il risultato che vuoi ottenere, penso che hai difficoltà perchè usi un modo complicato per "prendere" i vari elementi.

[gila75]

interessa anche a me quindi:

tu come l'hai impostato? a vedere da come scrivi il risultato che vuoi ottenere, penso che hai difficoltà perchè usi un modo complicato per "prendere" i vari elementi.

cosa intendi?

[crap0101]

interessa anche a me quindi:

tu come l'hai impostato? a vedere da come scrivi il risultato che vuoi ottenere, penso che hai difficoltà perchè usi un modo complicato per "prendere" i vari elementi.

cosa intendi?

siccome scrive

a; b: c; ab; ac; bc; abc

mi son fatto l'idea che cerca di impostare l'algoritmo per fargli listare le combinazioni in quel modo... ma sono due problemi diversi e, volendo "forzare" quell'ordine, imho è più complicato da scrivere. Poi non so, dipende da cosa ha fatto in realtà...

[M_A_W_ 1968]

Per gli oggetti combinatori elementari, e anche per molti altri casi non banali, non c'è alcunché da inventare: esiste una cornucopia di riferimenti in letteratura e sul web.

La Mecca per codesti algoritmi, e relative implementazioni in C (noto comunque che non è stato specificato il linguaggio nel titolo del thread) è il famosissimo e arcinoto COS del professor Ruskey. In particolare, in questa pagina si tratta ampiamente la banale generazione esaustiva di combinazioni. I link a sorgenti di esempio più che decorosi si trovano in fondo alla pagina. Di particolare interesse le implementazioni basate su trasposizioni, l'algoritmo di Chase e le implementazioni bit-oriented ivi referenziate.

[Ilgard]

A me servono solo le combinazioni, non le permutazioni, ovvero, per quel che mi serve, "ab" e "ba" sono esattamente la stessa cosa e quindi non devo generarli due volte. L'ordine dei risultati invece non è rilevante.
Comunque darò un'occhiata ai link di M_A_W, anche se forse mi è venuto in mente un algoritmo ricorsivo per ottenere le combinazioni.

[gila75]

A me servono solo le combinazioni, non le permutazioni, ovvero, per quel che mi serve, "ab" e "ba" sono esattamente la stessa cosa e quindi non devo generarli due volte. L'ordine dei risultati invece non è rilevante.

Io non ho capito bene cosa intendi

[Zoff]

@gila75: Le combinazioni nel calcolo combinatorio sono uno strumento ben preciso, non sono semplicemente i possibili abbinamenti tra un gruppo di elementi come si potrebbe intuire con una interpretazione da dizionario della lingua italiana del termine "Combinazione". In particolare, le combinazioni contengono tutti gli abbinamenti realizzabili da un insieme ignorando l'ordine degli elementi. Per maggiori informazioni: http://it.wikipedia.org/wiki/Combinazione. Le Permutazioni invece sono tutti gli abbinamenti possibili (considerando anche l'ordine): http://it.wikipedia.org/wiki/Permutazione

[M_A_W_ 1968]

Risulta arcinota da decenni la mia avversione all'uso di algoritmi ricorsivi con linguaggi imperativi di terza o quarta generazione, quindi basati su call conventions tradizionali nonché sprovvisti d'uno specifico supporto alla tail recursion optimization e dei tanti altri altri ammennicoli secondari che rendono il ricorso a tale pratica prestazionalmente accettabile.

Tuttavia, facendo straordinariamente eccezione, propongo qui uno dei più noti ed intuitivi algoritmi per la generazione esaustiva dell'insieme delle parti di un insieme dato con cardinalità (finita!) n. Insieme la cui ampiezza 2^n coincide, per una delle più straordinarie meraviglie della matematica discreta, con lo spazio di tutte le combinazioni di ampiezza compresa tra zero ed n, cosa che peraltro si può dimostrare banalmente già a livello di una seconda liceo (almeno ai miei tempi).

L'algoritmo è detto "del banchiere" perché fin dal tempo dei Medici, degli Strozzi e dei Sercambi (che finanziavano lo sfarzo delle corti di tutta Europa quando Firenze era la capitale mondiale della cultura e del Rinascimento) veniva usato dai contabili per la quantificazione fisica di mucchietti di denaro e banconote.
Non sono in grado di tracciare all'indietro un eventuale riferimento a terzi per tale implementazione, che sui miei supporti di massa è datata 1992. In ogni caso, è roba di pubblico dominio e da un bel pezzo.

Codice: Seleziona tutto

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

/* Dimensione dell'insieme di partenza */
#define DIM_TUPLA 6

/*
** Triangolo di Tartaglia in forma ridotta per il calcolo efficiente
** del coefficiente binomiale.
*/
#define MAX_BIN 35
const unsigned long Binom[MAX_BIN][18] = {
        {1,  0,   0,    0,     0,      0,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  1,   0,    0,     0,      0,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  2,   1,    0,     0,      0,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  3,   3,    1,     0,      0,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  4,   6,    4,     1,      0,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  5,  10,   10,     5,      1,       0,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  6,  15,   20,    15,      6,       1,       0,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  7,  21,   35,    35,     21,       7,       1,        0,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  8,  28,   56,    70,     56,      28,       8,        1,        0,         0,          0,          0,          0,          0,          0,          0,          0},
        {1,  9,  36,   84,   126,    126,      84,      36,        9,        1,         0,          0,          0,          0,          0,          0,          0,          0},
        {1, 10,  45,  120,   210,    252,     210,     120,       45,       10,         1,          0,          0,          0,          0,          0,          0,          0},
        {1, 11,  55,  165,   330,    462,     462,     330,      165,       55,        11,          1,          0,          0,          0,          0,          0,          0},
        {1, 12,  66,  220,   495,    792,     924,     792,      495,      220,        66,         12,          1,          0,          0,          0,          0,          0},
        {1, 13,  78,  286,   715,   1287,    1716,    1716,     1287,      715,       286,         78,         13,          1,          0,          0,          0,          0},
        {1, 14,  91,  364,  1001,   2002,    3003,    3432,     3003,     2002,      1001,        364,         91,         14,          1,          0,          0,          0},
        {1, 15, 105,  455,  1365,   3003,    5005,    6435,     6435,     5005,      3003,       1365,        455,        105,         15,          1,          0,          0},
        {1, 16, 120,  560,  1820,   4368,    8008,   11440,    12870,    11440,      8008,       4368,       1820,        560,        120,         16,          1,          0},
        {1, 17, 136,  680,  2380,   6188,   12376,   19448,    24310,    24310,     19448,      12376,       6188,       2380,        680,        136,         17,          1},
        {1, 18, 153,  816,  3060,   8568,   18564,   31824,    43758,    48620,     43758,      31824,      18564,       8568,       3060,        816,        153,         18},
        {1, 19, 171,  969,  3876,  11628,   27132,   50388,    75582,    92378,     92378,      75582,      50388,      27132,      11628,       3876,        969,        171},
        {1, 20, 190, 1140,  4845,  15504,   38760,   77520,   125970,   167960,    184756,     167960,     125970,      77520,      38760,      15504,       4845,       1140},
        {1, 21, 210, 1330,  5985,  20349,   54264,  116280,   203490,   293930,    352716,     352716,     293930,     203490,     116280,      54264,      20349,       5985},
        {1, 22, 231, 1540,  7315,  26334,   74613,  170544,   319770,   497420,    646646,     705432,     646646,     497420,     319770,     170544,      74613,      26334},
        {1, 23, 253, 1771,  8855,  33649,  100947,  245157,   490314,   817190,   1144066,    1352078,    1352078,    1144066,     817190,     490314,     245157,     100947},
        {1, 24, 276, 2024, 10626,  42504,  134596,  346104,   735471,  1307504,   1961256,    2496144,    2704156,    2496144,    1961256,    1307504,     735471,     346104},
        {1, 25, 300, 2300, 12650,  53130,  177100,  480700,  1081575,  2042975,   3268760,    4457400,    5200300,    5200300,    4457400,    3268760,    2042975,    1081575},
        {1, 26, 325, 2600, 14950,  65780,  230230,  657800,  1562275,  3124550,   5311735,    7726160,    9657700,   10400600,    9657700,    7726160,    5311735,    3124550},
        {1, 27, 351, 2925, 17550,  80730,  296010,  888030,  2220075,  4686825,   8436285,   13037895,   17383860,   20058300,   20058300,   17383860,   13037895,    8436285},
        {1, 28, 378, 3276, 20475,  98280,  376740, 1184040,  3108105,  6906900,  13123110,   21474180,   30421755,   37442160,   40116600,   37442160,   30421755,   21474180},
        {1, 29, 406, 3654, 23751, 118755,  475020, 1560780,  4292145, 10015005,  20030010,   34597290,   51895935,   67863915,   77558760,   77558760,   67863915,   51895935},
        {1, 30, 435, 4060, 27405, 142506,  593775, 2035800,  5852925, 14307150,  30045015,   54627300,   86493225,  119759850,  145422675,  155117520,  145422675,  119759850},
        {1, 31, 465, 4495, 31465, 169911,  736281, 2629575,  7888725, 20160075,  44352165,   84672315,  141120525,  206253075,  265182525,  300540195,  300540195,  265182525},
        {1, 32, 496, 4960, 35960, 201376,  906192, 3365856, 10518300, 28048800,  64512240,  129024480,  225792840,  347373600,  471435600,  565722720,  601080390,  565722720},
        {1, 33, 528, 5456, 40920, 237336, 1107568, 4272048, 13884156, 38567100,  92561040,  193536720,  354817320,  573166440,  818809200, 1037158320, 1166803110, 1166803110},
        {1, 34, 561, 5984, 46376, 278256, 1344904, 5379616, 18156204, 52451256, 131128140,  286097760,  548354040,  927983760, 1391975640, 1855967520, 2203961430, 2333606220} };

/**************************************************************************/
unsigned long BinCoef(const size_t n, const size_t k);
void PrintSet(const char *T, const size_t k);
void GenBanker(char *T, const size_t pos, const size_t k);
/**************************************************************************/
int main(void)
{
    size_t i;
    char bank[DIM_TUPLA];

    printf("Generazione del Power Set ristretto di rango %d:\n", DIM_TUPLA);

    for (i = 1; i < DIM_TUPLA; ++i)
    {
        GenBanker(bank, 0, i);
    }

    return EXIT_SUCCESS;
}
/**************************************************************************/
unsigned long BinCoef(const size_t n, const size_t k)
{
    if ((n < k) || (n > (MAX_BIN -1)))
    {
        return(0);
    }

    return ((k << 1) > n) ? (Binom[n][n-k]) : (Binom[n][k]);
}
/**************************************************************************/
void PrintSet(const char *T, const size_t k)
{
    size_t i;

    printf("{%d", T[0]);
    for (i = 1; i < k; ++i)
    {
        printf(", %d", T[i]);
    }
    puts("}");
}
/**************************************************************************/
void GenBanker(char *T, const size_t pos, const size_t k)
{
    size_t i;

    if (pos < k)
    {
        if (0 == pos)
        {
            for (i = 0; i < DIM_TUPLA; ++i)
            {
                T[pos] = (char)i;
                GenBanker(T, pos +1, k);
            }
        }
        else
        {
            for (i = T[pos -1] +1; i < DIM_TUPLA; ++i)
            {
                T[pos] = (char)i;
                GenBanker(T, pos +1, k);
            }
        }
    }
    else
    {
        PrintSet(T, k);
    }
}
/**************************************************************************/
/* EOF: Gen_banker.c */

Il power set (insieme potenza, non occorre spiegare il perché, o appunto insieme delle parti) così generato è "ristretto" poiché non enumera l'insieme vuoto e l'insieme di partenza, in quanto sottoinsiemi banali e, nel caso del secondo, anche sottoinsieme improprio. Le modifiche necessarie al sorgente qualora si volesse per qualsivoglia motivo includere tali sottoinsiemi nell'output sono tuttavia risibili.
Il formato interno utilizzato per la rappresentazione dei subset, scelta pressoché universale in campo di generazione combinatoria, è un array di char, nel quale a rigore ciascuna cella contiene un indice che individua un elemento dell'insieme di partenza, in questo caso limitato ad una cardinalità massima di 256 elementi (un valore già ampiamente di frontiera in campo combinatorio, specie per la generazione esaustiva: ma nulla vieta di usare unsigned long e anche uint64 in caso di reale necessità). Tale array è dunque facilmente riconvertibile a qualsiasi altro genere di impiego per la generazione esaustiva di oggetti combinatori semplici, per l'arcinoto lemma che consente di mappare qualsiasi insieme finito sull'intervallo iniziale dei naturali.

Ecco l'output di un test run:

Codice: Seleziona tutto

Generazione del Power Set ristretto di rango 7:
{0}
{1}
{2}
{3}
{4}
{5}
{6}
{0, 1}
{0, 2}
{0, 3}
{0, 4}
{0, 5}
{0, 6}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{1, 6}
{2, 3}
{2, 4}
{2, 5}
{2, 6}
{3, 4}
{3, 5}
{3, 6}
{4, 5}
{4, 6}
{5, 6}
{0, 1, 2}
{0, 1, 3}
{0, 1, 4}
{0, 1, 5}
{0, 1, 6}
{0, 2, 3}
{0, 2, 4}
{0, 2, 5}
{0, 2, 6}
{0, 3, 4}
{0, 3, 5}
{0, 3, 6}
{0, 4, 5}
{0, 4, 6}
{0, 5, 6}
{1, 2, 3}
{1, 2, 4}
{1, 2, 5}
{1, 2, 6}
{1, 3, 4}
{1, 3, 5}
{1, 3, 6}
{1, 4, 5}
{1, 4, 6}
{1, 5, 6}
{2, 3, 4}
{2, 3, 5}
{2, 3, 6}
{2, 4, 5}
{2, 4, 6}
{2, 5, 6}
{3, 4, 5}
{3, 4, 6}
{3, 5, 6}
{4, 5, 6}
{0, 1, 2, 3}
{0, 1, 2, 4}
{0, 1, 2, 5}
{0, 1, 2, 6}
{0, 1, 3, 4}
{0, 1, 3, 5}
{0, 1, 3, 6}
{0, 1, 4, 5}
{0, 1, 4, 6}
{0, 1, 5, 6}
{0, 2, 3, 4}
{0, 2, 3, 5}
{0, 2, 3, 6}
{0, 2, 4, 5}
{0, 2, 4, 6}
{0, 2, 5, 6}
{0, 3, 4, 5}
{0, 3, 4, 6}
{0, 3, 5, 6}
{0, 4, 5, 6}
{1, 2, 3, 4}
{1, 2, 3, 5}
{1, 2, 3, 6}
{1, 2, 4, 5}
{1, 2, 4, 6}
{1, 2, 5, 6}
{1, 3, 4, 5}
{1, 3, 4, 6}
{1, 3, 5, 6}
{1, 4, 5, 6}
{2, 3, 4, 5}
{2, 3, 4, 6}
{2, 3, 5, 6}
{2, 4, 5, 6}
{3, 4, 5, 6}
{0, 1, 2, 3, 4}
{0, 1, 2, 3, 5}
{0, 1, 2, 3, 6}
{0, 1, 2, 4, 5}
{0, 1, 2, 4, 6}
{0, 1, 2, 5, 6}
{0, 1, 3, 4, 5}
{0, 1, 3, 4, 6}
{0, 1, 3, 5, 6}
{0, 1, 4, 5, 6}
{0, 2, 3, 4, 5}
{0, 2, 3, 4, 6}
{0, 2, 3, 5, 6}
{0, 2, 4, 5, 6}
{0, 3, 4, 5, 6}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 6}
{1, 2, 3, 5, 6}
{1, 2, 4, 5, 6}
{1, 3, 4, 5, 6}
{2, 3, 4, 5, 6}
{0, 1, 2, 3, 4, 5}
{0, 1, 2, 3, 4, 6}
{0, 1, 2, 3, 5, 6}
{0, 1, 2, 4, 5, 6}
{0, 1, 3, 4, 5, 6}
{0, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5, 6}

[gila75]

@gila75: Le combinazioni nel calcolo combinatorio sono uno strumento ben preciso, non sono semplicemente i possibili abbinamenti tra un gruppo di elementi come si potrebbe intuire con una interpretazione da dizionario della lingua italiana del termine "Combinazione". In particolare, le combinazioni contengono tutti gli abbinamenti realizzabili da un insieme ignorando l'ordine degli elementi. Per maggiori informazioni: http://it.wikipedia.org/wiki/Combinazione. Le Permutazioni invece sono tutti gli abbinamenti possibili (considerando anche l'ordine): http://it.wikipedia.org/wiki/Permutazione

Grazie della precisazione Zoff.
Pensavo avesse bisogno di un anagramma o cose simili, evidentemente ho letto male o di fretta.