Re: Problema di combinatoria

Messaggioda Ledel » 13/07/2019, 16: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 4
Iscritto il: 30/06/2019, 15:38

Re: Problema di combinatoria

Messaggioda Super Squirrel » 13/07/2019, 21: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'!
Super Squirrel
Junior Member
Junior Member
 
Messaggio: 366 di 374
Iscritto il: 16/05/2013, 23:05

Precedente

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti