Re: Problema di combinatoria

Messaggioda Super Squirrel » 10/07/2019, 17:44

Qualcosa ci va pur messo! :D

Scherzi a parte, non è difficile, puoi arrivarci da solo. Indizio: quali sono le combinazioni semplici in base 3 dell'insieme
{0, 1, 2, 3, 4}
?
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 359 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 10/07/2019, 17:59

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}.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1772 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 10/07/2019, 20:44

Bene, ora data una di queste combinazioni (e considerando noti anche i parametri $n$ e $k$), bisogna stabilire se tale combinazione è l'ultima oppure no (e in tal caso bisogna ovviamente anche determinare quella successiva).

Assumiamo che gli elementi della generica combinazione siano individuati da un indice $i$ che parte da $0$ (un po' come avviene con gli array).
L'ultima combinazione può essere vista come quella in cui i singoli elementi che la costituiscono hanno tutti raggiunto un valore $MAX(i)=n-k+i$.
Magari la seguente schematizzazione può essere utile:

Immagine

Quindi la funzione next_combination() andrà ad analizzare la combinazione corrente iniziando dall'ultimo elemento, se esso è minore del relativo massimo allora sarà incrementato di $1$, altrimenti si passerà all'elemento precedente... il resto è facile da intuire.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 360 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 10/07/2019, 21:12

Ma in questo caso la i varia da 0 a 2 perchè k=3, ma k nel frattempo deve variare da 1 a 3. Quindi il massimo elemento di ogni combinazione va calcolato prima di eseguire il ciclo. Poi però non ho ben capito cosa avviene nel main. Perchè c'è un vettore di char e non capisco questo $v[u[i]]$.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1774 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 11/07/2019, 00:10

Cerco di spiegarmi meglio.
Dimentica per il momento quello che era il tuo intento iniziale (poi verrà da sé), e ipotizziamo di voler risolvere il seguente esercizio: stampare a schermo tutte le combinazioni semplici delle prime $5$ lettere dell'alfabeto prese $3$ alla volta.

Sarà ovviamente $n=5$ e $k=3$. Dichiariamo un array $v$ contenente il nostro set di elementi:
Codice:
char v[n] = {a, b, c, d, e};

Riprendiamo ora le e combinazioni semplici in base $3$ dell'insieme ${0, 1, 2, 3, 4}$ che ti ho chiesto in precedenza e ipotizziamo di salvarle in $10$ array di $k=3$ elementi ciascuno:
Codice:
unsigned int u_1[k] = {0,1,2};
unsigned int u_2[k] = {0,1,3};
unsigned int u_3[k] = {0,1,4};
unsigned int u_4[k] = {0,2,3};
unsigned int u_5[k] = {0,2,4};
unsigned int u_6[k] = {0,3,4};
unsigned int u_7[k] = {1,2,3};
unsigned int u_8[k] = {1,2,4};
unsigned int u_9[k] = {1,3,4};
unsigned int u_10[k] = {2,3,4};

Come conseguenza avremo che:
Codice:
{v[u_1[0]], v[u_1[1]], v[u_1[2]]} ≡ {v[0], v[1], v[2]} ≡ {a, b, c}
{v[u_2[0]], v[u_2[1]], v[u_2[2]]} ≡ {v[0], v[1], v[3]} ≡ {a, b, d}
{v[u_3[0]], v[u_3[1]], v[u_3[2]]} ≡ {v[0], v[1], v[4]} ≡ {a, b, e}
...
{v[u_8[0]], v[u_8[1]], v[u_8[2]]} ≡ {v[1], v[2], v[4]} ≡ {b, c, e}
{v[u_9[0]], v[u_9[1]], v[u_9[2]]} ≡ {v[1], v[3], v[4]} ≡ {b, d, e}
{v[u_10[0]], v[u_10[1]], v[u_10[2]]} ≡ {v[2], v[3], v[4]} ≡ {c, d, e}

Dove l'ultima colonna restituisce appunto quello che stavamo cercando, ossia le combinazioni semplici delle prime $5$ lettere dell'alfabeto prese $3$ alla volta. La prima colonna dovrebbe invece chiarirti il significato di quel $v[u[i]]$ di un mio precedente post.

A questo punto risulta evidente che il tutto si riduce ad escogitare un modo per ottenere in modo automatico gli array $u_1,u_2,...,u_9,u_10$.
Ed è qui che entra in gioco la funzione:
Codice:
bool next_combination(unsigned int n, unsigned int k, unsigned int u[k]);

Essa:
- per $u={0,1,2}$ restituirà true e modificherà il suddetto array in $u={0,1,3}$;
- per $u={0,1,3}$ restituirà true e modificherà il suddetto array in $u={0,1,4}$;
...
- per $u={1,3,4}$ restituirà true e modificherà il suddetto array in $u={2,3,4}$;
- per $u={2,3,4}$ restituirà false.

Quindi per risolvere l'esercizio che ho proposto all'inizio di questo messaggio, non resta altro che implementare la funzione next_combination() utilizzando i suggerimenti che ti ho dato nel precedente post. Inizia a buttare giù qualche riga di codice, poi nel caso possiamo ragionarci insieme.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 361 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 11/07/2019, 13:11

Scusami ma ho ancora qualche dubbio: come fà l'indice dell'array u[k] a essere una variabile? Prima di modificare l'array deve stampare quello precedente, giusto? Comunque ho provato a fare questo ma dubito sia giusto:
Codice:
bool next_combination(int n, int k, int u[k])
{
   for (int i = 0; i < k; i++)
   {
      int max = n - k + i;
      if (u[k] < max)
      {
         u[k]= u[k]++;
      }
      else
      {
         u[k]= u[k]--;
      }
   }

   for (int j = 0; j < k; j++)
      cout << u[j] << endl;
return;
}
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1775 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 11/07/2019, 14:45

Ti posto direttamente il codice, in questo modo ti risulterà più chiaro il mio ragionamento:

Codice:
#include <iostream>

//stampare a schermo tutte le combinazioni semplici delle prime 5 lettere dell'alfabeto prese 3 alla volta.

using namespace std;

bool next_combination(unsigned int n, unsigned int k, unsigned int *u)
{
    for(unsigned int i = 0; i < k; ++i)
    {
        if(u[k - i - 1] < n - i - 1) //il secondo termine rappresenta il massimo relativo al generico elemento
        {
            ++u[k - i - 1];
            for(unsigned int j = k - i; j < k; ++j)
            {
                u[j] = u[j - 1] + 1;
            }
            return true;
        }
    }
    return false;
}

int main()
{
    const unsigned int n = 5;
    const unsigned int k = 3;
    char v[n] = {'a', 'b', 'c', 'd', 'e'};
    unsigned int u[k] = {0, 1, 2};
    do
    {
        for(unsigned int i = 0; i < k; ++i)
        {
            cout << v[u[i]] << " ";
        }
        cout << endl;
    }
    while(next_combination(n, k, u));
}


Ora non resta che adattare il codice al tuo esercizio. Se qualcosa non ti è chiaro chiedi pure.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 364 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 11/07/2019, 15:44

Ok, ma in pratica invece di utilizzare i numeri, tu hai creato un array di char. Ora per far variare k bisogna incapsulare tutto in un ciclo, in modo che stampi tutte le combinazioni con 1, 2..n-1 element, giusto? Il codice penso comunque di averlo capito.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1776 di 4589
Iscritto il: 22/10/2016, 17:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 11/07/2019, 19:34

Ok, ma in pratica invece di utilizzare i numeri, tu hai creato un array di char.

In realtà l'ho fatto per sottolineare che il nostro set di $n$ elementi contenuti nell'array $v$ può essere costituito da elementi di qualsiasi tipo (int, char, stringhe, struct, altri array, etc...) e ordinati in vario modo (in ordine crescente, decrescente o disordinati). L'idea è proprio quella di sganciarsi dall'arbitrarietà dell'array $v$ lavorando direttamente su un secondo array $u$ con le seguenti caratteristiche:
- tipo int;
- dimensione $k$;
- inizializzato con valori che vanno da $0$ a $k-1$ disposti in ordine crescente.
Tale array non contiene altro, come già detto in precedenza, che gli indici relativi alla generica combinazione. Ad ogni chiamata della funzione next_combination() l'array $u$ viene aggiornato con gli indici della combinazione successiva.
Ora per far variare k bisogna incapsulare tutto in un ciclo, in modo che stampi tutte le combinazioni con 1, 2..n-1 element, giusto?

Sì, ma $k$ deve variare tra $1$ e $n$ e non tra $1$ e $n-1$.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 365 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Problema di combinatoria

Messaggioda ZfreS » 13/07/2019, 12:37

Va bene. Quindi, per completare il programma, bisogna inserire u[k] in un ciclo che fa variare il numero di elementi, ovvero gli indici. Quindi all'inizio sarà: {0}, {0,1}, {0,1,2}, {0,1,2,3}, {0,1,2,3,4}. Mi hai corretto, giustamente da 1 a n.
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1777 di 4589
Iscritto il: 22/10/2016, 17:52

PrecedenteProssimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite