Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

C# Permutation of an array of arraylists

By: a guest on Feb 14th, 2012  |  syntax: None  |  size: 9.54 KB  |  hits: 125  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. myList[0] = { "1", "5", "3", "9" };
  2. myList[1] = { "2", "3" };
  3. myList[2] = { "93" };
  4.        
  5. 1 2 93
  6. 1 3 93
  7. 5 2 93
  8. 5 3 93
  9. 3 2 93
  10. 3 3 93
  11. 9 2 93
  12. 9 3 93
  13.        
  14. from val0 in new []{ "1", "5", "3", "9" }
  15. from val1 in new []{ "2", "3" }
  16. from val2 in new []{ "93" }
  17. select String.Format("val0={0};val1={1};val2={2}", val0, val1, val2)
  18.        
  19. static List<string> foo(int a, List<Array> x)
  20.     {
  21.         List<string> retval= new List<string>();
  22.         if (a == x.Count)
  23.         {
  24.             retval.Add("");
  25.             return retval;
  26.         }
  27.         foreach (Object y in x[a])
  28.         {
  29.             foreach (string x2 in foo(a + 1, x))
  30.             {
  31.                 retval.Add(y.ToString() + " " + x2.ToString());
  32.             }
  33.  
  34.         }
  35.         return retval;
  36.     }
  37.     static void Main(string[] args)
  38.     {
  39.         List<Array> myList = new List<Array>();
  40.         myList.Add(new string[0]);
  41.         myList.Add(new string[0]);
  42.         myList.Add(new string[0]);
  43.         myList[0] = new string[]{ "1", "5", "3", "9" };
  44.         myList[1] = new string[] { "2", "3" };
  45.         myList[2] = new string[] { "93" };
  46.         foreach (string x in foo(0, myList))
  47.         {
  48.             Console.WriteLine(x);
  49.         }
  50.  
  51.         Console.ReadKey();
  52.     }
  53.        
  54. foreach (String s1 in array1) {
  55.     foreach (String s2 in array2) {
  56.         foreach (String s3 in array3) {
  57.             String result = s1 + " " + s2 + " " + s3;
  58.             //do something with the result
  59.         }
  60.     }
  61. }
  62.        
  63. private ArrayList<String> permute(ArrayList<ArrayList<String>> ar, int startIndex) {
  64.     if (ar.Count == 1) {
  65.         foreach(String s in ar.Value(0)) {
  66.             ar.Value(0) = "val" + startIndex + "=" + ar.Value(0);
  67.         return ar.Value(0);
  68.     }
  69.     ArrayList<String> ret = new ArrayList<String>();
  70.     ArrayList<String> tmp1 ar.Value(0);
  71.     ar.remove(0);
  72.     ArrayList<String> tmp2 = permute(ar, startIndex+1);
  73.     foreach (String s in tmp1) {
  74.         foreach (String s2 in tmp2) {
  75.             ret.Add("val" + startIndex + "=" + s + " " + s2);
  76.         }
  77.     }
  78.     return ret;
  79. }
  80.        
  81. static void Main(string[] args)
  82.         {
  83.             string[][] myList = new string[3][];
  84.             myList[0] = new string[] { "1", "5", "3", "9" };
  85.             myList[1] = new string[] { "2", "3" };
  86.             myList[2] = new string[] { "93" };
  87.  
  88.             List<string> permutations = new List<string>(myList[0]);
  89.  
  90.             for (int i = 1; i < myList.Length; ++i)
  91.             {
  92.                 permutations = RecursiveAppend(permutations, myList[i]);
  93.             }
  94.  
  95.             //at this point the permutations variable contains all permutations
  96.  
  97.         }
  98.  
  99.         static List<string> RecursiveAppend(List<string> priorPermutations, string[] additions)
  100.         {
  101.             List<string> newPermutationsResult = new List<string>();
  102.             foreach (string priorPermutation in priorPermutations)
  103.             {
  104.                 foreach (string addition in additions)
  105.                 {
  106.                     newPermutationsResult.Add(priorPermutation + ":" + addition);
  107.                 }
  108.             }
  109.             return newPermutationsResult;
  110.         }
  111.        
  112. static void Main(string[] args)
  113.         {
  114.             string[][] myList = new string[3][];
  115.             myList[0] = new string[] { "1", "5", "3", "9" };
  116.             myList[1] = new string[] { "2", "3" };
  117.             myList[2] = new string[] { "93" };
  118.  
  119.             List<List<string>> permutations = new List<List<string>>();
  120.  
  121.             foreach (string init in myList[0])
  122.             {
  123.                 List<string> temp = new List<string>();
  124.                 temp.Add(init);
  125.                 permutations.Add(temp);
  126.             }
  127.  
  128.             for (int i = 1; i < myList.Length; ++i)
  129.             {
  130.                 permutations = RecursiveAppend(permutations, myList[i]);
  131.             }
  132.  
  133.             //at this point the permutations variable contains all permutations
  134.  
  135.             foreach (List<string> list in permutations)
  136.             {
  137.                 foreach (string item in list)
  138.                 {
  139.                     Console.Write(item + ":");
  140.                 }
  141.                 Console.WriteLine();
  142.             }
  143.  
  144.         }
  145.  
  146.         static List<List<string>> RecursiveAppend(List<List<string>> priorPermutations, string[] additions)
  147.         {
  148.             List<List<string>> newPermutationsResult = new List<List<string>>();
  149.             foreach (List<string> priorPermutation in priorPermutations)
  150.             {
  151.                 foreach (string addition in additions)
  152.                 {
  153.                     List<string> priorWithAddition = new List<string>(priorPermutation);
  154.                     priorWithAddition.Add(addition);
  155.                     newPermutationsResult.Add(priorWithAddition);
  156.                 }
  157.             }
  158.             return newPermutationsResult;
  159.         }
  160.        
  161. Public Shared Function GetCombinationsFromIEnumerables(ByRef chain() As Object, ByRef IEnumerables As IEnumerable(Of IEnumerable(Of Object))) As List(Of Object())
  162.     Dim Combinations As New List(Of Object())
  163.     If IEnumerables.Any Then
  164.         For Each v In IEnumerables.First
  165.             Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(New Object() {v}).ToArray, IEnumerables.Skip(1)).ToArray)
  166.         Next
  167.     Else
  168.         Combinations.Add(chain)
  169.     End If
  170.     Return Combinations
  171. End Function
  172.  
  173. Public Shared Function GetCombinationsFromIEnumerables(ByVal ParamArray IEnumerables() As IEnumerable(Of Object)) As List(Of Object())
  174.     Return GetCombinationsFromIEnumerables(chain:=New Object() {}, IEnumerables:=IEnumerables.AsEnumerable)
  175. End Function
  176.        
  177. public static List<object[]> GetCombinationsFromIEnumerables(ref object[] chain, ref IEnumerable<IEnumerable<object>> IEnumerables)
  178. {
  179. List<object[]> Combinations = new List<object[]>();
  180. if (IEnumerables.Any) {
  181.     foreach ( v in IEnumerables.First) {
  182.         Combinations.AddRange(GetCombinationsFromIEnumerables(chain.Concat(new object[] { v }).ToArray, IEnumerables.Skip(1)).ToArray);
  183.     }
  184. } else {
  185.     Combinations.Add(chain);
  186. }
  187. return Combinations;
  188. }
  189.  
  190. public static List<object[]> GetCombinationsFromIEnumerables(params IEnumerable<object>[] IEnumerables)
  191. {
  192. return GetCombinationsFromIEnumerables(chain = new object[], IEnumerables = IEnumerables.AsEnumerable);
  193. }
  194.        
  195. Dim list1 = New String() {"hello", "bonjour", "hallo", "hola"}
  196. Dim list2 = New String() {"Erwin", "Larry", "Bill"}
  197. Dim list3 = New String() {"!", ".."}
  198. Dim result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3)
  199. For Each r In result
  200.     Debug.Print(String.Join(" "c, r))
  201. Next
  202.        
  203. object list1 = new string[] {"hello","bonjour","hallo","hola"};
  204. object list2 = new string[] {"Erwin", "Larry", "Bill"};
  205. object list3 = new string[] {"!",".."};
  206. object result = MyLib.GetCombinationsFromIEnumerables(list1, list2, list3);
  207. foreach (r in result) {
  208. Debug.Print(string.Join(' ', r));
  209. }
  210.        
  211. public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<IEnumerable<T>> lists)
  212. {
  213.     // Check against an empty list.
  214.     if (!lists.Any())
  215.     {
  216.         yield break;
  217.     }
  218.  
  219.     // Create a list of iterators into each of the sub-lists.
  220.     List<IEnumerator<T>> iterators = new List<IEnumerator<T>>();
  221.     foreach (var list in lists)
  222.     {
  223.         var it = list.GetEnumerator();
  224.         // Ensure empty sub-lists are excluded.
  225.         if (!it.MoveNext())
  226.         {
  227.             continue;
  228.         }
  229.         iterators.Add(it);
  230.     }
  231.  
  232.     bool done = false;
  233.     while (!done)
  234.     {
  235.         // Return the current state of all the iterator, this permutation.
  236.         yield return from it in iterators select it.Current;
  237.  
  238.         // Move to the next permutation.
  239.         bool recurse = false;
  240.         var mainIt = iterators.GetEnumerator();
  241.         mainIt.MoveNext(); // Move to the first, succeeds; the main list is not empty.
  242.         do
  243.         {
  244.             recurse = false;
  245.             var subIt = mainIt.Current;
  246.             if (!subIt.MoveNext())
  247.             {
  248.                 subIt.Reset(); // Note the sub-list must be a reset-able IEnumerable!
  249.                 subIt.MoveNext(); // Move to the first, succeeds; each sub-list is not empty.
  250.  
  251.                 if (!mainIt.MoveNext())
  252.                 {
  253.                     done = true;
  254.                 }
  255.                 else
  256.                 {
  257.                     recurse = true;
  258.                 }
  259.             }
  260.         }
  261.         while (recurse);
  262.     }
  263. }
  264.        
  265. public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> collection) where T : IComparable
  266.     {
  267.         if (!collection.Any())
  268.         {
  269.             return new List<IEnumerable<T>>() {Enumerable.Empty<T>() };
  270.         }
  271.         var sequence = collection.OrderBy(s => s).ToArray();
  272.         return sequence.SelectMany(s => GetPermutations(sequence.Where(s2 => !s2.Equals(s))).Select(sq => (new T[] {s}).Concat(sq)));
  273.     }
  274.        
  275. class Program
  276. {
  277.     static void Main(string[] args)
  278.     {
  279.         var listofInts = new List<List<int>>(3);
  280.         listofInts.Add(new List<int>{1, 2, 3});
  281.         listofInts.Add(new List<int> { 4,5,6 });
  282.         listofInts.Add(new List<int> { 7,8,9,10 });
  283.  
  284.         var temp = CrossJoinLists(listofInts);
  285.         foreach (var l in temp)
  286.         {
  287.             foreach (var i in l)
  288.                 Console.Write(i + ",");
  289.             Console.WriteLine();
  290.         }
  291.     }
  292.  
  293.     private static IEnumerable<List<T>> CrossJoinLists<T>(IEnumerable<List<T>> listofObjects)
  294.     {
  295.         var result = from obj in listofObjects.First()
  296.                      select new List<T> {obj};
  297.  
  298.         for (var i = 1; i < listofObjects.Count(); i++)
  299.         {
  300.             var iLocal = i;
  301.             result = from obj  in result
  302.                      from obj2 in listofObjects.ElementAt(iLocal)
  303.                      select new List<T>(obj){ obj2 };
  304.         }
  305.  
  306.         return result;
  307.     }
  308. }