[C#] Lista di combinazioni

[flx2000]

Ciao a tutti,
da un po' di giorni mi sto cimentando col C#. La mia esperienza è molto approfondita in fatto di programmazione ad oggetti, ma sono specializzato nel mondo open source (PHP, Python, Perl, ecc.).

Nel caso specifico, non riesco a creare un metodo che mi restituisca la lista di tutte le possibili combinazioni degli elementi di un array.

Ad esempio, supponiamo che io abbia la lista così ottenuta:

Oggetto A = new Oggetto();
Oggetto B = new Oggetto();
Oggetto C = new Oggetto();
List<Oggetto> lista = new List<Oggetto>();
lista.Add(A);
lista.Add(B);
lista.Add(C);


Quello che vorrei avere adesso è una lista che contenga una sottolista per ognuna delle possibili combinazioni degli oggetti di questa lista.

Insomma, mi occorre una lista di liste ognuna delle quali è composta da n oggetti in modo da avere tutte e 8 le possibili combinazioni di quei tre oggetti:

lista[0] = {A};
lista[1] = {A, B};
lista[2] = {A, C};
lista[3] = {A, B, C};
lista[4] = {B};
lista[5] = {B, C};
lista[6] = {C};
lista[7] = {};

Immagino che il problema sia risolvibile con una funzione ricorsiva, magari sfruttando la funzionalità yield di C#, ma attualmente non riesco a risolvere questo problema.

Grazie a chiunque conosca una formula standard o voglia aiutarmi in qualche modo, considerando che ovviamente il numero di elementi non sarà sempre 3 ma un numero che potrebbe essere diverso di volta in volta.

[gugoXX]

Ti do una semplice soluzione che funziona fino a 64 elementi

Un metodo che appunto ritorna una lista di liste di Oggetto e che accetta la lista di tutti i miei possibili oggetti (fino a 64 elementi come dicevo)

public List<List<Oggetto>> Esegui(List<Oggetto> src)

dentro il body del metodo inizi a contare con un ulong da 0 a 2^N - 1
dove N e' il numero di oggetti. (Se N e' 64 appunto avarai 2^64 -1, che e' il massimo rappresentabile dagli ulong)
Ad ogni ciclo prendi il contatore, e lo consideri come numero in base 2
Cicli quindi su tutti i bit del numero. Se e' un 1 devi quindi quindi considerare l'oggetto corrispondente in src e aggiungerlo alla List<Oggetto> temporanea che restituirai ad ogni ciclo. Se e' uno 0 no.
Restituisci (con yield) la List<Oggetto> appena costruita e poi temini il ciclo.

[flx2000]

Infatti, avevo già pensato di usare un sistema binario, in modo che il peso del bit fosse la posizione nell'array iniziale, ma so che esiste una soluzione meno meccanica e più logica che però non ricordo.
Ad ogni modo è probabile che farò così, almeno finché qualcuno saprà indicarmi l'altra strada.
Grazie!

[flx2000]

Alla fine un mio collega ha trovato un algoritmo in grado di sbrogliare la matassa e io l'ho convertito nel codice C# che risolve il problema senza utilizzare le ricorsioni.

Si presuppone che oggetti sia una lista di tipo List<Oggetto> contenente tutti gli oggetti da combinare, definita come:
List<Oggetto> oggetti = new List<Oggetto>();
Al quale siano aggiunti i vari oggetti da combinare con dei normali Add(Oggetto).

L'elenco di combinazioni possibili è quindi inteso come un insieme di liste, una per ogni possibile combinazione, ed è così definita:
List<List<Oggetto>> combinazioni = new List<List<Oggetto>>();

A questo punto il problema si risolve in questo modo:


// 1. Si aggiunge alla lista di combinazioni la combinazione vuota.
combinazioni.Add(new List<Oggetto>());

// 2. Si aggiunge alla lista di combinazioni una lista per ognuno degli
// elementi da combinare.
foreach (Oggetto ogg in oggetti)
{
combinazioni.Add(new List<Oggetto> { ogg });
}

// 3. Il numero di combinazioni è 2^n, ma nell'aggiungere gli elementi
// possiamo tralasciare tutte le combinazioni che finiscono con l'ultimo
// oggetto presente nella lista "oggetti", perché non hanno mai altri
// oggetti da concatenare. Il numero di passaggi diventa quindi 2^n-n
// con n il numero di elementi in "oggetti".
int maxidx = (int)Math.Pow(2, oggetti.Count) - oggetti.Count;

// 4. Per ognuna delle combinazioni già realizzate creo una nuova
// combinazione aggiungendo alla combinazione in esame gli elementi in
// "oggetti" che abbiano un indice superiore all'ultimo elemento di questa
// combinazione.
// In questo modo non rischio di aggiungere due volte la stessa combinazione
// e grazie alla variabile maxidx non vengono eseguiti né cicli a vuoto né
// si ha bisogno di istruzioni if.
for (int i = 1; i < maxidx; i++)
{
for (int j = oggetti.IndexOf(combinazioni[i].Last<Oggetto>()) + 1; j < oggetti.Count; j++)
{
combinazioni.Add(combinazioni[i].GetRange(0, combinazioni[i].Count).Concat(new List<Oggetto> { oggetti[j] }).ToList());
}
}


Questo codice ha risolto brillantemente il problema, ma lascio aperta la "sfida" a chiunque riesca a trovare metodi alternativi per risolverlo.
Grazie a tutti.