Come ottenere tutti i sottoinsiemi di un array?

Question

dato un array: [dog, cat, mouse]

qual è il modo più elegante per creare:

[,,] 
[,,mouse] 
[,cat,] 
[,cat,mouse] 
[dog,,] 
[dog,,mouse] 
[dog,cat,] 
[dog,cat,mouse] 

Ho bisogno di questo a lavorare per qualsiasi array di dimensioni.

Questo è essenzialmente un contatore binario, in cui gli indici di matrice rappresentano bit. Ciò presumibilmente mi consente di utilizzare alcune operazioni bit a bit per contare, ma non riesco a vedere un buon modo di tradurlo in indici di array.

Answer 1

string[] source = new string[] { "dog", "cat", "mouse" }; 
for (int i = 0; i < Math.Pow(2, source.Length); i++) 
{ 
    string[] combination = new string[source.Length]; 
    for (int j = 0; j < source.Length; j++) 
    { 
     if ((i & (1 << (source.Length - j - 1))) != 0) 
     { 
      combination[j] = source[j]; 
     } 
    } 
    Console.WriteLine("[{0}, {1}, {2}]", combination[0], combination[1], combination[2]); 
} 

Answer 2

static IEnumerable<IEnumerable<T>> GetSubsets<T>(IList<T> set) 
{ 
    var state = new BitArray(set.Count); 
    do 
     yield return Enumerable.Range(0, state.Count) 
           .Select(i => state[i] ? set[i] : default(T)); 
    while (Increment(state)); 
} 

static bool Increment(BitArray flags) 
{ 
    int x = flags.Count - 1; 
    while (x >= 0 && flags[x]) flags[x--] = false ; 
    if (x >= 0) flags[x] = true; 
    return x >= 0; 
} 

Usage:

foreach(var strings in GetSubsets(new[] { "dog", "cat", "mouse" })) 
    Console.WriteLine(string.Join(", ", strings.ToArray())); 

Answer 3

Io non sono molto familiare con C#, ma sono sicuro che ci sia qualcosa di simile:

// input: Array A 
foreach S in AllSubsetsOf1ToN(A.Length): 
    print (S.toArray().map(lambda x |> A[x])); 

---

Ok, Mi è stato detto che la risposta sopra non funzionerà. Se il valore eleganza sull'efficienza, vorrei provare la ricorsione, nel mio pseudocodice schifosa:

Array_Of_Sets subsets(Array a) 
{ 
    if (a.length == 0) 
     return [new Set();] // emptyset 
    return subsets(a[1:]) + subsets(a[1:]) . map(lambda x |> x.add a[0]) 
} 

Answer 4

Ecco una soluzione facile da seguire lungo le linee di vostra concezione:

private static void Test() 
{ 
    string[] test = new string[3] { "dog", "cat", "mouse" }; 

    foreach (var x in Subsets(test)) 
     Console.WriteLine("[{0}]", string.Join(",", x)); 
} 

public static IEnumerable<T[]> Subsets<T>(T[] source) 
{ 
    int max = 1 << source.Length; 
    for (int i = 0; i < max; i++) 
    { 
     T[] combination = new T[source.Length]; 

     for (int j = 0; j < source.Length; j++) 
     { 
      int tailIndex = source.Length - j - 1; 
      combination[tailIndex] = 
       ((i & (1 << j)) != 0) ? source[tailIndex] : default(T); 
     } 

     yield return combination; 
    } 
} 

Answer 5

Puoi utilizzare la classe BitArray di accedere facilmente i bit di un numero:

string[] animals = { "Dog", "Cat", "Mouse" }; 
List<string[]> result = new List<string[]>(); 
int cnt = 1 << animals.Length; 
for (int i = 0; i < cnt; i++) { 
    string[] item = new string[animals.Length]; 
    BitArray b = new BitArray(i); 
    for (int j = 0; j < item.Length; j++) { 
     item[j] = b[j] ? animals[j] : null; 
    } 
    result.Add(item); 
} 

Answer 6

Questo è un piccolo cambiamento di soluzione di Mehrdad sopra:

static IEnumerable<T[]> GetSubsets<T>(T[] set) { 
    bool[] state = new bool[set.Length+1]; 
    for (int x; !state[set.Length]; state[x] = true) { 
     yield return Enumerable.Range(0, state.Length) 
           .Where(i => state[i]) 
           .Select(i => set[i]) 
           .ToArray(); 
     for (x = 0; state[x]; state[x++] = false); 
    } 
} 

o con i puntatori

static IEnumerable<T[]> GetSubsets<T>(T[] set) { 
    bool[] state = new bool[set.Length+1]; 
    for (bool *x; !state[set.Length]; *x = true) { 
     yield return Enumerable.Range(0, state.Length) 
           .Where(i => state[i]) 
           .Select(i => set[i]) 
           .ToArray(); 
     for (x = state; *x; *x++ = false); 
    } 
} 

Answer 7

elegante? Perché non Linq it.

public static IEnumerable<IEnumerable<T>> SubSetsOf<T>(IEnumerable<T> source) 
    { 
     if (!source.Any()) 
      return Enumerable.Repeat(Enumerable.Empty<T>(), 1); 

     var element = source.Take(1); 

     var haveNots = SubSetsOf(source.Skip(1)); 
     var haves = haveNots.Select(set => element.Concat(set)); 

     return haves.Concat(haveNots); 
    } 

Answer 8

Ecco una soluzione simile a quella del metodo di David B, ma forse più adatto se è davvero un requisito che si ottiene indietro set con il numero originale di elementi (anche se vuoto) :.

static public List<List<T>> GetSubsets<T>(IEnumerable<T> originalList) 
{ 
    if (originalList.Count() == 0) 
     return new List<List<T>>() { new List<T>() }; 

    var setsFound = new List<List<T>>(); 
    foreach (var list in GetSubsets(originalList.Skip(1))) 
    {     
     setsFound.Add(originalList.Take(1).Concat(list).ToList()); 
     setsFound.Add(new List<T>() { default(T) }.Concat(list).ToList()); 
    } 
    return setsFound; 
} 

Se si passa in un elenco di tre corde, si otterrà indietro otto liste con tre elementi ciascuno (ma alcuni elementi sarà nullo).

Answer 9

risposta di Guffa aveva la funzionalità di base che stavo cercando, ma la linea con

BitArray b = new BitArray(i); 

non ha funzionato per me, ha dato un ArgumentOutOfRangeException. Ecco il mio codice di alcuni adattamenti ed a lavorare:

string[] array = { "A", "B", "C","D" }; 
int count = 1 << array.Length; // 2^n 

for (int i = 0; i < count; i++) 
{ 
    string[] items = new string[array.Length]; 
    BitArray b = new BitArray(BitConverter.GetBytes(i)); 
    for (int bit = 0; bit < array.Length; bit++) { 
     items[bit] = b[bit] ? array[bit] : ""; 
    } 
    Console.WriteLine(String.Join("",items)); 
}