c# - todas - generador de combinaciones sin repeticion

Obteniendo todas las combinaciones posibles de una lista de números

Question

Estoy buscando una manera eficiente de lograr esto:

• tiene una lista de números 1 ..... n (normalmente: 1..5 o 1..7 o algo así - razonablemente pequeño, pero puede variar de un caso a otro)

• necesita todas las combinaciones de todas las longitudes para esos números, por ejemplo, todas las combinaciones de un solo número ({1}, {2}, .... {n}), luego todas las combinaciones de dos números distintos ({1,2}, {1,3}, {1,4} ..... {n-1, n}), luego todas las combinaciones de tres de esos números ({1,2,3}, {1,2,4}) Etcétera

Básicamente, dentro del grupo, el orden es irrelevante, por lo que {1,2,3} es equivalente a {1,3,2} - solo es cuestión de obtener todos los grupos de x números de esa lista

Parece que debería haber un algoritmo simple para esto, pero hasta ahora he buscado en vano. La mayoría de los algoritmos combinatorios y de permutación parecen a) tener en cuenta el orden (por ejemplo, 123 no es igual a 132), y parece que siempre operan en una sola cadena de caracteres o números ...

¿Alguien tiene un gran algoritmo bonito y bueno en la manga?

¡Gracias!

Answer 1

Esto es algo que he escrito en el pasado para lograr esa tarea.

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

Es genérico, por lo que funcionará para ints, longs, strings, foos, etc.

Answer 2

No es mi código, pero estás buscando el powerset. Google me dio esta solución, que parece que funciona:

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

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

Answer 3

Solo incremente un número binario y tome los elementos correspondientes a los bits que se establecen.

Por ejemplo, 00101101 significaría tomar los elementos en los índices 0, 2, 3 y 5. Como su lista es simplemente 1..n, el elemento es simplemente el índice + 1.

Esto generará permuataciones en orden. En otras palabras, solo se generará {1, 2, 3} . No {1, 3, 2} o {2, 1, 3} o {2, 3, 1} , etc.