Comment obtenir tous les sous-ensembles d'un tableau?

Question

voit attribuer une série: [dog, cat, mouse]

ce qui est la façon la plus élégante de créer:

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

Je en ai besoin de travailler pour une gamme de taille.

Il s'agit essentiellement d'un compteur binaire, où les indices de tableau représentent des bits. Cela me permet vraisemblablement d'utiliser une opération au niveau du bit pour compter, mais je ne vois pas de bonne façon de traduire cela en indices de tableau.

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; 
} 

Utilisation:

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

Answer 3

Je ne suis pas très familier avec C#, mais je suis sûr qu'il ya quelque chose comme:

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

---

Ok, On m'a dit que la réponse ci-dessus ne fonctionnera pas. Si vous appréciez l'élégance sur l'efficacité, je voudrais essayer récursion, dans mon merdique pseudocode:

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

est ici une solution facile à suivre le long des lignes de votre conception:

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

Vous pouvez utiliser la classe BitArray pour accéder facilement aux bits dans un numéro:

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

Ce petit changement à la solution de Mehrdad ci-dessus:

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); 
    } 
} 

ou avec des pointeurs

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

élégant? Pourquoi pas Linq.

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

Voici une solution similaire à la méthode de David B, mais peut-être plus approprié si elle est vraiment une exigence que vous revenez avec le nombre des ensembles d'origine d'éléments (même si elle est vide) :.

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; 
} 

Si vous passez dans une liste de trois chaînes, vous récupérerez huit listes avec trois éléments chacun (mais certains éléments seront nuls).

Answer 9

réponse de Guffa avait les fonctionnalités de base que je cherchais, mais la ligne avec

BitArray b = new BitArray(i); 

ne fonctionnait pas pour moi, il a donné un ArgumentOutOfRangeException. Voici mon code légèrement ajusté et fonctionnant:

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)); 
}