C# Permutación de una matriz de listas de arreglos?

Question

Tengo un ArrayList [] myList y estoy tratando de crear una lista de todas las permutaciones de los valores en las matrices.

EJEMPLO: (todos los valores son cadenas)

myList[0] = { "1", "5", "3", "9" }; 
myList[1] = { "2", "3" }; 
myList[2] = { "93" }; 

El recuento de myList puede variarse de modo que su longitud no se conoce de antemano.

Me gustaría poder generar una lista de todas las permutaciones similares a las siguientes (pero con algún formato adicional).

1 2 93 
1 3 93 
5 2 93 
5 3 93 
3 2 93 
3 3 93 
9 2 93 
9 3 93 

¿Esto tiene sentido de lo que estoy tratando de lograr? Parece que no puedo encontrar un buen método para hacer esto (si hay alguno).

Edit:
No estoy seguro de si la recursión podría interferir con mi deseo de formatear la salida de mi propia manera. Lamento no haber mencionado antes cuál era mi formato.

I quiere terminar la construcción de una cadena de array [] de todas las combinaciones que sigue el formato, como a continuación:

para la permutación "1 2 93"

Quiero que la salida sea "val0 = 1; val1 = 2; val2 = 93; "

Voy a experimentar con la recursividad por el momento. Gracias DrJokepu

Answer 1

solución no recursivo:

foreach (String s1 in array1) { 
    foreach (String s2 in array2) { 
     foreach (String s3 in array3) { 
      String result = s1 + " " + s2 + " " + s3; 
      //do something with the result 
     } 
    } 
} 

solución recursiva:

private ArrayList<String> permute(ArrayList<ArrayList<String>> ar, int startIndex) { 
    if (ar.Count == 1) { 
     foreach(String s in ar.Value(0)) { 
      ar.Value(0) = "val" + startIndex + "=" + ar.Value(0); 
     return ar.Value(0); 
    } 
    ArrayList<String> ret = new ArrayList<String>(); 
    ArrayList<String> tmp1 ar.Value(0); 
    ar.remove(0); 
    ArrayList<String> tmp2 = permute(ar, startIndex+1); 
    foreach (String s in tmp1) { 
     foreach (String s2 in tmp2) { 
      ret.Add("val" + startIndex + "=" + s + " " + s2); 
     } 
    } 
    return ret; 
} 

Answer 2

solución recursiva

static List<string> foo(int a, List<Array> x) 
    { 
     List<string> retval= new List<string>(); 
     if (a == x.Count) 
     { 
      retval.Add(""); 
      return retval; 
     } 
     foreach (Object y in x[a]) 
     { 
      foreach (string x2 in foo(a + 1, x)) 
      { 
       retval.Add(y.ToString() + " " + x2.ToString()); 
      } 

     } 
     return retval; 
    } 
    static void Main(string[] args) 
    { 
     List<Array> myList = new List<Array>(); 
     myList.Add(new string[0]); 
     myList.Add(new string[0]); 
     myList.Add(new string[0]); 
     myList[0] = new string[]{ "1", "5", "3", "9" }; 
     myList[1] = new string[] { "2", "3" }; 
     myList[2] = new string[] { "93" }; 
     foreach (string x in foo(0, myList)) 
     { 
      Console.WriteLine(x); 
     } 

     Console.ReadKey(); 
    } 

Nota que sería bastante fácil para devolver una lista o array en lugar de una cadena cambiando el retorno para que sea una lista de cadenas y cambie la retícula .add llamada a trabajar con una lista en lugar de utilizar la concatenación.

Cómo funciona:

Se trata de un algoritmo recursivo clásico. El caso base es foo(myList.Count, myList), que devuelve una lista que contiene un elemento, la cadena vacía. La permutación de una lista de matrices de n cadenas s1, s2, ..., sN es igual a cada miembro de sA1 prefijado a la permutación de n-1 matrices de cadenas, s2, ..., sN. El caso base está allí para proporcionar algo para cada elemento de sN que se concatenará.

Answer 3

Esto funcionará sin importar cuantas matrices que añadir a su miLista:

 static void Main(string[] args) 
     { 
      string[][] myList = new string[3][]; 
      myList[0] = new string[] { "1", "5", "3", "9" }; 
      myList[1] = new string[] { "2", "3" }; 
      myList[2] = new string[] { "93" }; 

      List<string> permutations = new List<string>(myList[0]); 

      for (int i = 1; i < myList.Length; ++i) 
      { 
       permutations = RecursiveAppend(permutations, myList[i]); 
      } 

      //at this point the permutations variable contains all permutations 

     } 

     static List<string> RecursiveAppend(List<string> priorPermutations, string[] additions) 
     { 
      List<string> newPermutationsResult = new List<string>(); 
      foreach (string priorPermutation in priorPermutations) 
      { 
       foreach (string addition in additions) 
       { 
        newPermutationsResult.Add(priorPermutation + ":" + addition); 
       } 
      } 
      return newPermutationsResult; 
     } 

Tenga en cuenta que en realidad no es recursivo. Probablemente un nombre de función engañoso.

Aquí hay una versión que se adhiere a sus nuevos requisitos.Tenga en cuenta la sección en la salida I a la consola, aquí es donde usted puede hacer su propio formato:

static void Main(string[] args) 
     { 
      string[][] myList = new string[3][]; 
      myList[0] = new string[] { "1", "5", "3", "9" }; 
      myList[1] = new string[] { "2", "3" }; 
      myList[2] = new string[] { "93" }; 

      List<List<string>> permutations = new List<List<string>>(); 

      foreach (string init in myList[0]) 
      { 
       List<string> temp = new List<string>(); 
       temp.Add(init); 
       permutations.Add(temp); 
      } 

      for (int i = 1; i < myList.Length; ++i) 
      { 
       permutations = RecursiveAppend(permutations, myList[i]); 
      } 

      //at this point the permutations variable contains all permutations 

      foreach (List<string> list in permutations) 
      { 
       foreach (string item in list) 
       { 
        Console.Write(item + ":"); 
       } 
       Console.WriteLine(); 
      } 

     } 

     static List<List<string>> RecursiveAppend(List<List<string>> priorPermutations, string[] additions) 
     { 
      List<List<string>> newPermutationsResult = new List<List<string>>(); 
      foreach (List<string> priorPermutation in priorPermutations) 
      { 
       foreach (string addition in additions) 
       { 
        List<string> priorWithAddition = new List<string>(priorPermutation); 
        priorWithAddition.Add(addition); 
        newPermutationsResult.Add(priorWithAddition); 
       } 
      } 
      return newPermutationsResult; 
     } 

Answer 4

Se podría utilizar para generar factoradics la enumeración de permutaciones. Pruebe this article on MSDN para una implementación en C#.

Answer 5

Me sorprende que nadie haya publicado la solución LINQ.

from val0 in new []{ "1", "5", "3", "9" } 
from val1 in new []{ "2", "3" } 
from val2 in new []{ "93" } 
select String.Format("val0={0};val1={1};val2={2}", val0, val1, val2) 

Answer 6

Aquí es una función genérica recursivo que escribí (y una sobrecarga que puede ser conveniente llamar):

Public Shared Function GetCombinationsFromIEnumerables(ByRef chain() As Object, ByRef IEnumerables As IEnumerable(Of IEnumerable(Of Object))) As List(Of Object()) 
    Dim Combinations As New List(Of Object()) 
    If IEnumerables.Any Then 
     For Each v In IEnumerables.First 
      Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(New Object() {v}).ToArray, IEnumerables.Skip(1)).ToArray) 
     Next 
    Else 
     Combinations.Add(chain) 
    End If 
    Return Combinations 
End Function 

Public Shared Function GetCombinationsFromIEnumerables(ByVal ParamArray IEnumerables() As IEnumerable(Of Object)) As List(Of Object()) 
    Return GetCombinationsFromIEnumerables(chain:=New Object() {}, IEnumerables:=IEnumerables.AsEnumerable) 
End Function 

y el equivalente en C#:

public static List<object[]> GetCombinationsFromIEnumerables(ref object[] chain, ref IEnumerable<IEnumerable<object>> IEnumerables) 
{ 
List<object[]> Combinations = new List<object[]>(); 
if (IEnumerables.Any) { 
    foreach (v in IEnumerables.First) { 
     Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(new object[] { v }).ToArray, IEnumerables.Skip(1)).ToArray); 
    } 
} else { 
    Combinations.Add(chain); 
} 
return Combinations; 
} 

public static List<object[]> GetCombinationsFromIEnumerables(params IEnumerable<object>[] IEnumerables) 
{ 
return GetCombinationsFromIEnumerables(chain = new object[], IEnumerables = IEnumerables.AsEnumerable); 
} 

Fácil use:

Dim list1 = New String() {"hello", "bonjour", "hallo", "hola"} 
Dim list2 = New String() {"Erwin", "Larry", "Bill"} 
Dim list3 = New String() {"!", ".."} 
Dim result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3) 
For Each r In result 
    Debug.Print(String.Join(" "c, r)) 
Next 

o en C#:

object list1 = new string[] {"hello","bonjour","hallo","hola"}; 
object list2 = new string[] {"Erwin", "Larry", "Bill"}; 
object list3 = new string[] {"!",".."}; 
object result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3); 
foreach (r in result) { 
Debug.Print(string.Join(' ', r)); 
} 

Answer 7

Recientemente me encontré con un problema similar en un proyecto mío y tropecé con esta pregunta. Necesitaba una solución no recursiva que pudiera funcionar con listas de objetos arbitrarios. Esto es lo que se me ocurrió. Básicamente, estoy formando una lista de enumeradores para cada una de las sublistas e incrementándolas iterativamente.

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists) 
{ 
    // Check against an empty list. 
    if (!lists.Any()) 
    { 
     yield break; 
    } 

    // Create a list of iterators into each of the sub-lists. 
    List<IEnumerator<T>> iterators = new List<IEnumerator<T>>(); 
    foreach (var list in lists) 
    { 
     var it = list.GetEnumerator(); 
     // Ensure empty sub-lists are excluded. 
     if (!it.MoveNext()) 
     { 
      continue; 
     } 
     iterators.Add(it); 
    } 

    bool done = false; 
    while (!done) 
    { 
     // Return the current state of all the iterator, this permutation. 
     yield return from it in iterators select it.Current; 

     // Move to the next permutation. 
     bool recurse = false; 
     var mainIt = iterators.GetEnumerator(); 
     mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty. 
     do 
     { 
      recurse = false; 
      var subIt = mainIt.Current; 
      if (!subIt.MoveNext()) 
      { 
       subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable! 
       subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty. 

       if (!mainIt.MoveNext()) 
       { 
        done = true; 
       } 
       else 
       { 
        recurse = true; 
       } 
      } 
     } 
     while (recurse); 
    } 
} 

Answer 8

Aquí es una versión que utiliza muy poco código, y es totalmente declarativa

public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> collection) where T : IComparable 
    { 
     if (!collection.Any()) 
     { 
      return new List<IEnumerable<T>>() {Enumerable.Empty<T>() }; 
     } 
     var sequence = collection.OrderBy(s => s).ToArray(); 
     return sequence.SelectMany(s => GetPermutations(sequence.Where(s2 => !s2.Equals(s))).Select(sq => (new T[] {s}).Concat(sq))); 
    } 

Answer 9

class Program 
{ 
    static void Main(string[] args) 
    { 
     var listofInts = new List<List<int>>(3); 
     listofInts.Add(new List<int>{1, 2, 3}); 
     listofInts.Add(new List<int> { 4,5,6 }); 
     listofInts.Add(new List<int> { 7,8,9,10 }); 

     var temp = CrossJoinLists(listofInts); 
     foreach (var l in temp) 
     { 
      foreach (var i in l) 
       Console.Write(i + ","); 
      Console.WriteLine(); 
     } 
    } 

    private static IEnumerable<List<T>> CrossJoinLists<T>(IEnumerable<List<T>> listofObjects) 
    { 
     var result = from obj in listofObjects.First() 
        select new List<T> {obj}; 

     for (var i = 1; i < listofObjects.Count(); i++) 
     { 
      var iLocal = i; 
      result = from obj in result 
        from obj2 in listofObjects.ElementAt(iLocal) 
        select new List<T>(obj){ obj2 }; 
     } 

     return result; 
    } 
} 

Answer 10

Lo que está pidiendo que se llama el producto cartesiano. Una vez que sepa cómo se llama, hay varias preguntas similares sobre Stack Overflow. Todos ellos parecen acabe apuntando a una respuesta que terminó escrita como una entrada de blog:

http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx

Answer 11

Aquí es una solución no recursivo, no LINQ. No puedo evitar sentir que podría tener menos bucles y calcular las posiciones con división y módulo, pero no puedo entender bien eso.

static void Main(string[] args) 
    { 
     //build test list 
     List<string[]> myList = new List<string[]>(); 
     myList.Add(new string[0]); 
     myList.Add(new string[0]); 
     myList.Add(new string[0]); 
     myList[0] = new string[] { "1", "2", "3"}; 
     myList[1] = new string[] { "4", "5" }; 
     myList[2] = new string[] { "7", "8", "9" }; 

     object[][] xProds = GetProducts(myList.ToArray()); 
     foreach(object[] os in xProds) 
     { 
      foreach(object o in os) 
      { 
       Console.Write(o.ToString() + " "); 
      } 
      Console.WriteLine(); 
     } 
     Console.ReadKey(); 
    } 

    static object[][] GetProducts(object[][] jaggedArray){ 
     int numLists = jaggedArray.Length; 
     int nProducts = 1; 
     foreach (object[] oArray in jaggedArray) 
     { 
      nProducts *= oArray.Length; 
     } 
     object[][] productAry = new object[nProducts][];//holds the results 
     int[] listIdxArray = new int[numLists]; 
     listIdxArray.Initialize(); 
     int listPtr = 0;//point to current list 

     for(int rowcounter = 0; rowcounter < nProducts; rowcounter++) 
     { 
      //create a result row 
      object[] prodRow = new object[numLists]; 
      //get values for each column 
      for(int i=0;i<numLists;i++) 
      { 
       prodRow[i] = jaggedArray[i][listIdxArray[i]]; 
      } 
      productAry[rowcounter] = prodRow; 
      //move the list pointer 
      //possible states 
      // 1) in a list, has room to move down 
      // 2) at bottom of list, can move to next list 
      // 3) at bottom of list, no more lists left 
      //in a list, can move down 
      if (listIdxArray[listPtr] < (jaggedArray[listPtr].Length - 1)) 
      { 
       listIdxArray[listPtr]++; 
      } 
      else 
      { 
       //can move to next column? 
       //move the pointer over until we find a list, or run out of room 
       while (listPtr < numLists && listIdxArray[listPtr] >= (jaggedArray[listPtr].Length - 1)) 
       { 
        listPtr++; 
       } 
       if (listPtr < listIdxArray.Length && listIdxArray[listPtr] < (jaggedArray[listPtr].Length - 1)) 
       { 
        //zero out the previous stuff 
        for (int k = 0; k < listPtr; k++) 
        { 
         listIdxArray[k] = 0; 
        } 
        listIdxArray[listPtr]++; 
        listPtr = 0; 
       } 
      } 
     } 
     return productAry; 
    } 

Answer 12

Uno de los problemas que encountred cuando estaba haciendo esto por una cantidad muy grande de códigos fue que se dio con el ejemplo Brian De hecho, me quedo sin memoria. Para resolver esto, utilicé el siguiente código.

static void foo(string s, List<Array> x, int a) 
    { 
     if (a == x.Count) 
     { 
      // output here 
      Console.WriteLine(s); 
     } 
     else 
     { 
      foreach (object y in x[a]) 
      { 
       foo(s + y.ToString(), x, a + 1); 
      } 
     } 
    } 

static void Main(string[] args) 
    { 
     List<Array> a = new List<Array>(); 
     a.Add(new string[0]); 
     a.Add(new string[0]); 
     a.Add(new string[0]); 
     a[0] = new string[] { "T", "Z" }; 
     a[1] = new string[] { "N", "Z" }; 
     a[2] = new string[] { "3", "2", "Z" }; 

     foo("", a, 0); 
     Console.Read(); 
    }