¿Cómo puedo obtener toda la combinación posible de un subconjunto?

Considere esta List

 List data = new List(); data.Add("Text1"); data.Add("Text2"); data.Add("Text3"); data.Add("Text4"); 

El problema que tuve fue: ¿cómo puedo obtener cada combinación de un subconjunto de la lista? Un poco como esto:

 #Subset Dimension 4 Text1;Text2;Text3;Text4 #Subset Dimension 3 Text1;Text2;Text3; Text1;Text2;Text4; Text1;Text3;Text4; Text2;Text3;Text4; #Subset Dimension 2 Text1;Text2; Text1;Text3; Text1;Text4; Text2;Text3; Text2;Text4; #Subset Dimension 1 Text1; Text2; Text3; Text4; 

Se me ocurrió una solución decente que creo que vale la pena compartir aquí.

Creo que las respuestas en esta pregunta necesitan algunas pruebas de rendimiento. Voy a darle una oportunidad. Es wiki de la comunidad , no dude en actualizarlo.

 void PerfTest() { var list = Enumerable.Range(0, 21).ToList(); var t1 = GetDurationInMs(list.SubSets_LB); var t2 = GetDurationInMs(list.SubSets_Jodrell2); var t3 = GetDurationInMs(() => list.CalcCombinations(20)); Console.WriteLine("{0}\n{1}\n{2}", t1, t2, t3); } long GetDurationInMs(Func>> fxn) { fxn(); //JIT??? var count = 0; var sw = Stopwatch.StartNew(); foreach (var ss in fxn()) { count = ss.Sum(); } return sw.ElapsedMilliseconds; } 

SALIDA:

 1281 1604 (_Jodrell not _Jodrell2) 6817 

Actualización de Jodrell

He construido en modo de lanzamiento, es decir, optimizaciones en. Cuando corro a través de Visual Studio no obtengo un sesgo consistente entre 1 o 2, pero después de repetidas ejecuciones la respuesta de LB gana, obtengo respuestas que se aproximan a algo así como:

 1190 1260 more 

pero si ejecuto el arnés de prueba desde la línea de comandos, no desde Visual Studio, obtengo resultados como este

 987 879 still more 

Lógica similar a la respuesta de Abaco, implementación diferente …

 foreach (var ss in data.SubSets_LB()) { Console.WriteLine(String.Join("; ",ss)); } public static class SO_EXTENSIONS { public static IEnumerable> SubSets_LB( this IEnumerable enumerable) { List list = enumerable.ToList(); ulong upper = (ulong)1 << list.Count; for (ulong i = 0; i < upper; i++) { List l = new List(list.Count); for (int j = 0; j < sizeof(ulong) * 8; j++) { if (((ulong)1 << j) >= upper) break; if (((i >> j) & 1) == 1) { l.Add(list[j]); } } yield return l; } } } 

EDITAR

He aceptado el guante de rendimiento, lo que sigue es mi amalgama que toma la mejor de todas las respuestas. En mi prueba, parece tener el mejor rendimiento hasta ahora.

 public static IEnumerable> SubSets_Jodrell2( this IEnumerable source) { var list = source.ToList(); var limit = (ulong)(1 << list.Count); for (var i = limit; i > 0; i--) { yield return list.SubSet(i); } } private static IEnumerable SubSet( this IList source, ulong bits) { for (var i = 0; i < source.Count; i++) { if (((bits >> i) & 1) == 1) { yield return source[i]; } } } 

La misma idea otra vez, casi lo mismo que la respuesta de LB pero mi propia interpretación.

Math.Pow el uso de una List interna y Math.Pow .

 public static IEnumerable> SubSets_Jodrell( this IEnumerable source) { var count = source.Count(); if (count > 64) { throw new OverflowException("Not Supported ..."); } var limit = (ulong)(1 << count) - 2; for (var i = limit; i > 0; i--) { yield return source.SubSet(i); } } private static IEnumerable SubSet( this IEnumerable source, ulong bits) { var check = (ulong)1; foreach (var t in source) { if ((bits & check) > 0) { yield return t; } check <<= 1; } } 

Notará que estos métodos no funcionan con más de 64 elementos en el conjunto inicial, pero de todos modos comienza a tomar un tiempo.

Desarrollé un método de extensión simple para las listas:

  ///  /// Obtain all the combinations of the elements contained in a list ///  /// Subset Dimension /// IEnumerable containing all the differents subsets public static IEnumerable> CalcCombinations(this List list, int subsetDimension) { //First of all we will create a binary matrix. The dimension of a single row //must be the dimension of list //on which we are working (we need a 0 or a 1 for every single element) so row //dimension is to obtain a row-length = list.count we have to //populate the matrix with the first 2^list.Count binary numbers int rowDimension = Convert.ToInt32(Math.Pow(2, list.Count)); //Now we start counting! We will fill our matrix with every number from 1 //(0 is meaningless) to rowDimension //we are creating binary mask, hence the name List combinationMasks = new List(); for (int i = 1; i < rowDimension; i++) { //I'll grab the binary rapresentation of the number string binaryString = Convert.ToString(i, 2); //I'll initialize an array of the apropriate dimension int[] mask = new int[list.Count]; //Now, we have to convert our string in a array of 0 and 1, so first we //obtain an array of int then we have to copy it inside our mask //(which have the appropriate dimension), the Reverse() //is used because of the behaviour of CopyTo() binaryString.Select(x => x == '0' ? 0 : 1).Reverse().ToArray().CopyTo(mask, 0); //Why should we keep masks of a dimension which isn't the one of the subset? // We have to filter it then! if (mask.Sum() == subsetDimension) combinationMasks.Add(mask); } //And now we apply the matrix to our list foreach (int[] mask in combinationMasks) { List temporaryList = new List(list); //Executes the cycle in reverse order to avoid index out of bound for (int iter = mask.Length - 1; iter >= 0; iter--) { //Whenever a 0 is found the correspondent item is removed from the list if (mask[iter] == 0) temporaryList.RemoveAt(iter); } yield return temporaryList; } } } 

Entonces, considerando el ejemplo en la pregunta:

 # Row Dimension of 4 (list.Count) Binary Numbers to 2^4 # Binary Matrix 0 0 0 1 => skip 0 0 1 0 => skip [...] 0 1 1 1 => added // Text2;Text3;Text4 [...] 1 0 1 1 => added // Text1;Text3;Text4 1 1 0 0 => skip 1 1 0 1 => added // Text1;Text2;Text4 1 1 1 0 => added // Text1;Text2;Text3 1 1 1 1 => skip 

Espero que esto pueda ayudar a alguién 🙂

Si necesita una aclaración o desea contribuir, no dude en agregar respuestas o comentarios (cuál es más apropiado).