C# Permutazione di un array di arraylists?

Question

Ho una listaArray [] myList e sto provando a creare un elenco di tutte le permutazioni dei valori negli array.

ESEMPIO: (tutti i valori sono stringhe)

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

Numero di myList può essere variata in modo sua lunghezza non è noto in anticipo.

Vorrei essere in grado di generare un elenco di tutte le permutazioni simili alle seguenti (ma con alcune formattazioni aggiuntive).

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

Questo ha senso di ciò che sto cercando di realizzare? Non riesco a trovare un buon metodo per farlo (se esiste).

Modifica:
Non sono sicuro che la ricorsione interferirebbe con il mio desiderio di formattare l'output nel mio modo. Mi spiace di non averlo menzionato prima di quale fosse la mia formattazione.

voglio finire costruire una stringa array [] di tutte le combinazioni che segue il formato come qui sotto:

per la permutazione "1 2 93"

voglio l'uscita sia "VAL0 = 1; val1 = 2; val2 = 93;"

Per ora sperimenterò la ricorsione. Grazie DrJokepu

Answer 1

soluzione non ricorsiva:

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

soluzione ricorsiva:

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

soluzione ricorsiva

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 che sarebbe stato abbastanza facile per restituire un elenco o array invece di una stringa cambiando il ritorno in modo da essere una lista di liste di stringhe e cambiando il retval Chiamata .add per lavorare con una lista invece di usare la concatenazione.

Come funziona:

Si tratta di un algoritmo ricorsivo classico. Il caso base è foo(myList.Count, myList), che restituisce un elenco contenente un elemento, la stringa vuota. La permutazione di una lista di m array di stringhe s1, s2, ..., sN è uguale a ogni membro di sA1 prefissato alla permutazione di matrici di stringhe n-1, s2, ..., sN. Il caso base è solo lì per fornire qualcosa per ogni elemento di sN a cui essere concatenato.

Answer 3

Questo funziona indipendentemente dal numero di matrici si aggiunge al tuo myList:

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

Si noti che non è davvero ricorsivo. Probabilmente un nome di funzione fuorviante.

Ecco una versione che rispetta le vostre nuove esigenze.Si noti la sezione in cui l'uscita da I a console, questo è dove si può fare la propria formattazione:

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

Si potrebbe utilizzare factoradics per generare l'enumerazione di permutazioni. Prova this article on MSDN per un'implementazione in C#.

Answer 5

Sono sorpreso che nessuno abbia pubblicato la soluzione 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

Ecco una generica funzione ricorsiva che ho scritto (e un sovraccarico che può essere conveniente per chiamare):

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 

e l'equivalente in 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); 
} 

Facile utilizzare:

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 

oppure in 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

Recentemente ho riscontrato un problema simile in un mio progetto e sono incappato in questa domanda. Avevo bisogno di una soluzione non ricorsiva che potesse funzionare con elenchi di oggetti arbitrari. Ecco cosa mi è venuto in mente. Fondamentalmente sto formando un elenco di enumeratori per ciascuna delle sotto-liste e incrementandoli 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

Ecco una versione che utilizza pochissimo codice, ed è interamente dichiarativa

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

cosa si sta chiedendo è chiamato il prodotto cartesiano. Una volta che sai come è chiamato, ci sono diverse domande simili su Stack Overflow. Tutti sembrano finire che punta a una risposta che ha finito per scritto come un post sul blog:

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

Answer 11

Ecco una soluzione non ricorsiva, non Linq. Non posso fare a meno di sentirmi come se potessi avere meno loop e calcolare le posizioni con divisione e modulo, ma non riesco a capirlo.

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 dei problemi che ho encountred quando stavo facendo questo per una grande quantità di codici è che è stato dato con l'esempio brian io in realtà a corto di memoria. Per risolvere questo ho usato il seguente codice.

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