¿Cómo obtener todos los subconjuntos de una matriz?

Question

Dado un vector: [dog, cat, mouse]

lo que es la forma más elegante para crear:

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

Necesito que esto funcione para cualquier matriz de tamaño.

Esto es esencialmente un contador binario, donde los índices de matriz representan bits. Esto presumiblemente me permite usar una operación bit a bit para contar, pero no puedo ver una buena forma de traducir esto a índices de matriz.

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

Uso:

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

Answer 3

No estoy muy familiarizado con C#, pero estoy seguro de que hay algo así como:

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

---

Ok, Me dijeron que la respuesta anterior no funcionará. Si el valor de elegancia sobre la eficiencia, me gustaría probar la recursividad, en mi pseudocódigo chungo:

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

Aquí es una solución fácil de seguir a lo largo de las líneas de su concepción:

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

Puede utilizar la clase BitArray de acceder fácilmente a los bits de un número:

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

Este es un pequeño cambio en la solución de Mehrdad arriba:

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 punteros

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? ¿Por qué no 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

he aquí una solución similar al método de David B, pero quizá lo más adecuado si es realmente un requisito que vuelvas conjuntos con el número original de elementos (aunque estén vacíos) :.

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 se pasa en una lista de tres cuerdas, que pondremos en ocho listas con tres elementos cada uno (pero algunos elementos será nula).

Answer 9

respuesta de Guffa tenía la funcionalidad básica que yo estaba buscando, sin embargo la línea con

BitArray b = new BitArray(i); 

no funcionó para mí, se dio una ArgumentOutOfRangeException. Este es mi código ligeramente ajustado y funcional:

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