Ottenere tutte le combinazioni possibili da un elenco di numeri

Question

che sto cercando un modo efficace per raggiungere questo obiettivo:

• si dispone di un elenco di numeri 1 ..... n (tipicamente: 1 .. 5 o 1..7 circa - ragionevolmente piccolo, ma può variare da caso a caso)

• occorrono tutte le combinazioni di tutte le lunghezze per tali numeri, ad es. tutte le combinazioni di un solo numero ({1}, {2}, .... {n}), quindi tutte le combinazioni di due numeri distinti ({1,2}, {1,3}, {1,4}. .... {n-1, n}), allora tutte le combinazioni di fo tre di questi numeri ({1,2,3}, {1,2,4}) e così via

Fondamentalmente, all'interno del gruppo, l'ordine è irrilevante, quindi {1,2,3} equivale a {1,3,2} - è solo questione di ottenere tutti i gruppi di x numeri da quella lista

Sembra che ci dovrebbe essere un semplice algoritmo per questo - ma ho cercato invano finora. La maggior parte degli algoritmi di combinatoria e permutazione sembra a) prendere in considerazione l'ordine (ad esempio 123 non è uguale a 132), e sembra sempre operare su una singola stringa di caratteri o numeri ....

Chiunque ha un grande, bel'n'quick algoritmo nella loro manica ??

Grazie!

Answer 1

Basta incrementare un numero binario e prendere gli elementi corrispondenti ai bit impostati.

Per esempio, 00101101 significherebbe prendere gli elementi a indici 0, 2, 3 e 5. Dal momento che l'elenco è semplicemente 1..n, l'elemento è semplicemente l'indice di + 1.

Questo genererà permuatazioni in corso. In altre parole, verrà generato solo {1, 2, 3}. Non o {2, 1, 3} o {2, 1, 3} o {2, 3, 1}, ecc.

Answer 2

Questo è qualcosa che ho scritto in passato per svolgere tale compito.

List<T[]> CreateSubsets<T>(T[] originalArray) 
{ 
    List<T[]> subsets = new List<T[]>(); 

    for (int i = 0; i < originalArray.Length; i++) 
    { 
     int subsetCount = subsets.Count; 
     subsets.Add(new T[] { originalArray[i] }); 

     for (int j = 0; j < subsetCount; j++) 
     { 
      T[] newSubset = new T[subsets[j].Length + 1]; 
      subsets[j].CopyTo(newSubset, 0); 
      newSubset[newSubset.Length - 1] = originalArray[i]; 
      subsets.Add(newSubset); 
     } 
    } 

    return subsets; 
} 

E 'generica, in modo da funzionare per interi, long, stringhe, Foos, ecc

Answer 3

Non è il mio codice, ma si sta cercando il Powerset. Google mi ha dato questa soluzione, che sembra t lavoro:

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) 
{ 
    return from m in Enumerable.Range(0, 1 << list.Count) 
       select 
        from i in Enumerable.Range(0, list.Count) 
        where (m & (1 << i)) != 0 
        select list[i]; 
} 

Fonte: http://rosettacode.org/wiki/Power_set#C.23