c# - todas - generador de combinaciones sin repeticion
Obteniendo todas las combinaciones posibles de una lista de números (3)
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!
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.
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];
}
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.