Problema di combinatoria

Messaggioda ZfreS » 09/07/2019, 15:57

Ho questo problemino: generare tutti i sottoinsiemi di un insieme dato, ordinato per dimensione.
Per esempio: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}.
Il problema in questo caso non è tanto l'implementazione dell'algoritmo, ma capire come ottenere l'algoritmo. Devo implementare qualcosa relativo al calcolo combinatorio per risolverlo?
Potreste darmi una pista su cui ragionare?
Ultima modifica di ZfreS il 09/07/2019, 16:26, modificato 1 volta in totale.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1761 di 1805
Iscritto il: 22/10/2016, 18:52

Re: Problema di

Messaggioda Raptorista » 09/07/2019, 16:12

Un generico sottoinsieme di un insieme dato è un insieme in cui ciascun elemento c'è oppure non c'è. Il numero di sottoinsiemi è quindi dato da tutte le combinazioni possibili di elementi che ci sono o non ci sono. Per esempio, se l'insieme di partenza è {1,2,3}, puoi vedere il sottoinsieme {1,2} come il numero binario 110, eccetera.
Spero che l'indizio sia utile, ma non ne sono sicurissimo :D
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5279 di 5325
Iscritto il: 28/09/2008, 20:58

Re: Problema di combinatoria

Messaggioda ZfreS » 09/07/2019, 16:36

La tua osservazione mi sembra corretta, ho avuto perciò un'idea basato su questo, ma penso che richieda una dimostrazione matematica. Supponiamo che l'insieme sia già ordinato: {1,2,3,4,5}. I sottoinsiemi sono:
{1,2} {2,3} {3,4} {4,5}
{1,3} {2,4} {3,5}
{1,4} {2,5}
{1,5}

In pratica ho notato questo ordine, poi ci sono da aggiungere tutti quelli con gli elementi singoli quindi: {1} {2} {3} {4} {5}
Aspetto la risposta di qualcuno esperto, ma intanto questa è una mia idea di partenza. Poi è da vedere il metodo che le ordina mentre crea i sottoinsiemi.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1762 di 1805
Iscritto il: 22/10/2016, 18:52

Re: Problema di combinatoria

Messaggioda Raptorista » 09/07/2019, 16:39

Quelli non sono tutti i sottoinsiemi però.
Dal punto di vista dell'implementazione, un approccio ricorsivo potrebbe funzionare se l'insieme non è gigantesco.
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5280 di 5325
Iscritto il: 28/09/2008, 20:58

Re: Problema di combinatoria

Messaggioda ZfreS » 09/07/2019, 17:00

Non considero {1,2} e {2,1} come sottoinsiemi diversi. L'algoritmo deve prestarsi bene anche per insiemi di 50 elementi. Quindi penso che l'approccio ricorsivo non sia la miglior soluzione.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1764 di 1805
Iscritto il: 22/10/2016, 18:52

Re: Problema di combinatoria

Messaggioda Raptorista » 09/07/2019, 17:35

ZfreS ha scritto:Non considero {1,2} e {2,1} come sottoinsiemi diversi.

Nemmeno io. Mancano tutti i sottoinsiemi di tre elementi, così come quelli di quattro elementi.
ZfreS ha scritto:L'algoritmo deve prestarsi bene anche per insiemi di 50 elementi. Quindi penso che l'approccio ricorsivo non sia la miglior soluzione.

Mmm, 50 sono tanti in effetti :S
Ho risolto l'esercizio al volo e lo sto eseguendo in Python. Non è una passeggiata con 50 elementi.

Se li vuoi conservare tutti in memoria avrai anche problemi di spazio. Qual è esattamente il tuo obiettivo?
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5281 di 5325
Iscritto il: 28/09/2008, 20:58

Re: Problema di combinatoria

Messaggioda ZfreS » 09/07/2019, 18:08

Hai ragione, mancano tutti gli altri, quindi deve essere semplice. Tu hai già implementato? Beh, non li devo conservare in memoria, dato che il fine dell'esercizio non è tanto la gestione delle risorse quanto l'algoritmo che crea e ordina i sottoinsiemi.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1765 di 1805
Iscritto il: 22/10/2016, 18:52

Re: Problema di combinatoria

Messaggioda Raptorista » 09/07/2019, 18:47

Ok, ma generarli in ordine qualsiasi e poi ordinarli è più semplice che generarli direttamente in ordine. Se non li puoi memorizzare tutti insieme significa che li devi generare già nell'ordine giusto.
Un matematico ha scritto:... come mia nonna che vuole da anni il sistema per vincere al lotto e crede che io, in quanto matematico, sia fallito perché non glielo trovo


Immagine
Avatar utente
Raptorista
Moderatore
Moderatore
 
Messaggio: 5282 di 5325
Iscritto il: 28/09/2008, 20:58

Re: Problema di combinatoria

Messaggioda ZfreS » 09/07/2019, 19:37

Ok, mettiamola in questo modo: i numeri disordinati verranno memorizzati in un array nel main, non a runtime; poi man mano che vengono ordinati vengono anche memorizzati (non se ne può fare a meno). L'importante ora è capire come funziona l'algoritmo.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1766 di 1805
Iscritto il: 22/10/2016, 18:52

Re: Problema di combinatoria

Messaggioda Super Squirrel » 09/07/2019, 20:28

Se ho ben capito, nel caso in cui gli elementi fossero $n=5$, il risultato dovrebbe essere il seguente?

Immagine

Secondo me la cosa più semplice è implementare una funzione in grado di generare tutte le combinazioni semplici di $n$ elementi presi $k$ alla volta e poi mettere tale funzione all'interno di un ciclo che fa variare $k$ da 1 a $n$.
Super Squirrel
Junior Member
Junior Member
 
Messaggio: 355 di 376
Iscritto il: 16/05/2013, 23:05

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti