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

Question

que estoy buscando una forma eficaz de lograr esto:

• usted tiene una lista de los números 1 ..... n (por lo general: 1 .. 5 o 1..7 más o menos - razonablemente pequeño, pero puede variar según el caso)

• 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}), a continuación, todas las combinaciones de FO tres de esos números ({1,2,3}, {1,2,4}) y así sucesivamente

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

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

Cualquiera tiene un gran, Algoritmo nice'n'quick bajo la manga?

Gracias!

Answer 1

Sólo incrementar un número binario y tomar 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. Debido a que su lista es simplemente 1..n, el elemento es simplemente el índice de + 1.

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

Answer 2

Esto es algo que he escrito en el pasado para lograr tal 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 funciona para los enteros, productos largos, cuerdas, Foos, etc.

Answer 3

No

mi código, pero usted está buscando la powerset. Google me dio esta solución, que parece t trabajo:

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