Re: Problema di combinatoria

Messaggioda Ledel » 13/07/2019, 15:15

Salve.
Per ottenere la lista ordinata dei sottoinsiemi di $k$ elementi presi da un insieme di $n$ ho utilizzato un arcaico "Visual Basic" (del secolo scorso) che però funziona ancora alla perfezione; ho impostato un ciclo For - Next per incrementare il numero degli elementi dell'array da 1 ad n ed ho poi dovuto escogitare una routine personale per il cambio degli indici, non potendo usufruire della funzione next_combination di C++. Qualche riga di programma in più e il risultato è stato raccolto su una List specifica. Come già segnalato il numero dei sottoinsiemi risulta dalla sommatoria delle combinazioni di $1, 2, 3 ... n$ elementi quindi:

$ x=\sum_{k=1}^\n\frac{(n!)}{(n-k)!*(k!)} $ con l'esclusione dell'insieme vuoto.

equivalente a $2^n - 1$ sottoinsiemi

Per n = 14 la lista dei 16384 sottoinsiemi è apparsa dopo 7 secondi.
Ledel
Starting Member
Starting Member
 
Messaggio: 2 di 10
Iscritto il: 30/06/2019, 14:38

Re: Problema di combinatoria

Messaggioda Super Squirrel » 13/07/2019, 20:35

Da quel che so non esiste una funzione next_combination() fornita dalla libreria standard del C++.

Ma i 7'' quali attività comprendono? In ogni caso il dato interessante sarebbe il tempo relativo alla sola generazione delle combinazioni.

ho poi dovuto escogitare una routine personale per il cambio degli indici

Per le combinazioni non è molto difficile, se invece parliamo di permutazioni la faccenda si complica un po'!
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 366 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 25/10/2019, 14:18

Ho ripreso il problema che ho lasciato in sospeso dopo mesi, per mancanza di tempo non l'ho terminato. Volevo capire bene il perchè dell'algoritmo proposto da SuperSquirrel, in particolare come ha dedotto la formula che indica il valore massimo che ogni elemento della combinazione deve raggiungere: $MAX(i)=n-k+i$. C'è un modo intuititivo per arrivarci?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1893 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 26/10/2019, 21:15

Quella formula si riferisce ad un insieme di $n$ elementi ben preciso, costituito da interi che vanno da $0$ a $n-1$. Mesi fa ti chiesi quali fossero le combinazioni semplici in base $3$ dell'insieme ${0, 1, 2, 3, 4}$ (in pratica $n=5$ e $k=3$) e tu scrivesti:
ZfreS ha scritto:sono: {0,1,2} {0,1,3} {0,1,4} {0,2,3} {0,2,4} {0,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4}.

Ovviamente questo è solo uno dei tanti modi in cui le suddette combinazioni possono essere esplicitate, ma utilizzando questo approccio risulta evidente che l'ultima combinazione, che coincide con gli ultimi $k$ elementi dell'insieme di partenza, è costituita dai massimi valori che gli elementi in una determinata posizione (o caratterizzati da un determinato indice, se preferisci) possono raggiungere.
La formula che ti proposi all'epoca, e che tu hai riportato nel post precedente, è solo uno dei tanti modi di formalizzare il concetto appena esposto.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 379 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda Obidream » 27/10/2019, 03:37

Super Squirrel ha scritto:Da quel che so non esiste una funzione next_combination() fornita dalla libreria standard del C++.

Ma i 7'' quali attività comprendono? In ogni caso il dato interessante sarebbe il tempo relativo alla sola generazione delle combinazioni.

Per curiosità ho provato una versione ricorsiva, di cui non sono neanche troppo sicuro, sul mio hardware modesto siamo ben sotto i 7 secondi d'esecuzione:

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

#define N 15

static void print_comb(const int *v, const int k)
{
    int i;

    printf("[%2d", v[0]);
    for (i = 1; i < k; ++i) {
        printf(", %2d", v[i]);
    }
    puts("]");
}

static void gen_comb(int *v, const int p, const int k)
{
    int i;

    if (p < k) {
        if (0 == p) {
            for (i = 1; i < N; ++i) {
                v[p] = i;
                gen_comb(v, p + 1, k);
            }
        }
        else {
            for (i = v[p - 1] + 1; i < N; ++i) {
                v[p] = i;
                gen_comb(v, p + 1, k);
            }
        }
    }
    else {
        print_comb(v, k);
    }
}


int main(void)
{
    int i;
    int v[N];

    for (i = 1; i < N; ++i) {
        gen_comb(v, 0, i);
    }

    return EXIT_SUCCESS;
}



C'è da dire che il tempo d'esecuzione, come già anticipato, cresce in maniera disgustosa per cui ha poco senso buttare numeri come 20-30, perché tra i 2 estremi c'è tanta differenza.
((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000))
Avatar utente
Obidream
Advanced Member
Advanced Member
 
Messaggio: 1070 di 2194
Iscritto il: 07/02/2012, 20:57

Re: Problema di combinatoria

Messaggioda ZfreS » 27/10/2019, 09:31

Ok, osservando le combinazioni si nota che ogni elemento raggiunge un valore massimo, ma hai detto che i sono diversi modi di formalizzarlo, la mia domanda è: come ci si arriva? Quella formula è sempre valida?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1894 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 27/10/2019, 15:54

Obidream ha scritto:Per curiosità ho provato una versione ricorsiva, di cui non sono neanche troppo sicuro, sul mio hardware modesto siamo ben sotto i 7 secondi d'esecuzione...

Per l'array v credo sia sufficiente una dimensione pari a $k$, inoltre, affinché siano calcolate le combinazioni semplici di $n$ (e non $n-1$) elementi, bisogna modificare la condizione dei for all'interno della funzione gen_comb() in <=N.
Apportando le suddette modifiche e qualche piccola semplificazione ho ottenuto il seguente codice:
Codice:
#include <stdio.h>

#define N 7
#define K 4

void print_comb(const unsigned int *v)
{
    for(unsigned int i = 0; i < K; ++i)
    {
        printf("%2d  ", v[i]);
    }
    printf("\n");
}

void gen_comb(unsigned int *v, const unsigned int p)
{
    if(p < K)
    {
        unsigned int i = 1;
        if(p)
        {
            i += v[p - 1];
        }
        for( ; i <= N; ++i)
        {
            v[p] = i;
            gen_comb(v, p + 1);
        }
    }
    else
    {
        print_comb(v);
    }
}

int main()
{
    unsigned int v[K];
    gen_comb(v, 0);
    return 0;
}

Per $n=30$ e $k=19$, e rimuovendo l'output, il tempo di esecuzione si aggira sui 18''. Nelle stesse condizioni il programma che ho postato nelle pagine precedenti impiega circa 2''. Ora non so quanto sia rigoroso il test che ho effettuato, ma penso che il punto sia un altro, ossia che una versione ricorsiva sia di più difficile utilizzo rispetto ad una iterativa in grado di passare da una generica combinazione a quella successiva (per esempio nel tuo codice la funzione print_comb() deve essere richiamata per forza dalla funzione gen_comb() e non dal main()).

ZfreS ha scritto:Ok, osservando le combinazioni si nota che ogni elemento raggiunge un valore massimo, ma hai detto che i sono diversi modi di formalizzarlo, la mia domanda è: come ci si arriva? Quella formula è sempre valida?

Come già detto nel precedente post, quella formula è sempre valida nel momento in cui il set di elementi è costituito dagli interi che vanno da $0$ a $n-1$ e le combinazioni sono esplicitate utilizzando l'approccio:
ZfreS ha scritto:sono: {0,1,2} {0,1,3} {0,1,4} {0,2,3} {0,2,4} {0,3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4}.

Per quanto riguarda l'altra domanda credo di non aver ben capito quale sia il tuo dubbio!
Provo a metterla diversamente:
- il massimo valore assumibile dall'ultimo elemento della generica combinazione è $n-1$;
- il massimo valore assumibile dal penultimo elemento della generica combinazione è $n-2$;
- il massimo valore assumibile dal terzultimo elemento della generica combinazione è $n-3$;
- ...
Ovviamente tale formulazione è equivalente a quella postata in precedenza $MAX(i)=n-k+i$
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 380 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 27/10/2019, 16:29

Hai chiarito tutto, grazie mille superSquirrel!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1895 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda ZfreS » 26/06/2020, 16:13

Super Squiller, ritorno per l'ennesima volta sull'argomento, dopo un po di tempo riprendo sempre dei vecchi problemi per vedere se li avevo capiti bene la prima volta, e fino a u certo puto era vero, però l'ultima volta non avevo prestato attenzione a questo ciclo:
Codice:
for(unsigned int j = k - i; j < k; ++j)
            {
                u[j] = u[j - 1] + 1;
            }
            return true;


Sinceramente non ho ben capito cosa fa questo ciclo, ma ripeto l'altra volta er concentrato su un altro spetto del problema e non ci ho fatto troppa attenzione. Oggi, provando a riscrivere il codice arrivo al punto di non riuscire a continuare come se mi fossi dimenticato una parte del codice, ed in effetti è così.
Non è che gentilmente potresti spiegarmi cosa fa esattamente quel ciclo?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 2108 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 27/06/2020, 00:11

Rieccoci qua! :D

Praticamente partendo dall'elemento immediatamente successivo a quello modificato dall'istruzione
Codice:
++u[k - i - 1];

quindi dall'elemento di indice
$j=(k-i-1)+1=k-i$
e proseguendo fino alla fine dell'array u (definita dalla condizione $j<k$),
quel ciclo for si limita ad assegnare al generico elemento di indice j il valore dell'elemento precedente incrementato di 1.

Riprendendo l'immagine

Immagine

consideriamo per esempio la combinazione n°6:
- partendo dalla fine abbiamo che l'elemento di indice i=2 è uguale al massimo per quella posizione (ossia 4);
- passiamo quindi all'elemento di indice i=1, ma anche lui è uguale al relativo massimo (ossia 3);
- passiamo allora all'elemento di indice i=0, il quale, essendo minore del relativo massimo (che è 2), può essere incrementato passando da 0 al valore 1.
Ed è proprio qui che entra in gioco quel ciclo for, il quale, modificando gli elementi di indici i=1 e i=2, ci consente di avere come combinazione n°7 la sequenza
1 2 3
al posto della sequenza
1 3 4
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 416 di 1486
Iscritto il: 16/05/2013, 22:05

PrecedenteProssimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite