C＃排列的ArrayList的数组？
我有一个ArrayList [] myList，我试图创build一个数组中的所有值的排列列表。
例子:(所有的值都是string）
myList[0] = { "1", "5", "3", "9" }; myList[1] = { "2", "3" }; myList[2] = { "93" }; myList的数量可以改变，所以它的长度是事先不知道的。
我希望能够生成类似于以下的所有排列的列表（但有一些额外的格式）。
1 2 93 1 3 93 5 2 93 5 3 93 3 2 93 3 3 93 9 2 93 9 3 93
这是否意味着我正在努力完成什么？ 我似乎无法想出一个好的方法来做到这一点，（如果有的话）。
编辑：
我不确定recursion是否会干扰我以我自己的方式格式化输出的愿望。 对不起，我没有提到我的格式是什么。
我想最终build立一个如下格式的所有组合的string[]数组：
为“1 2 93”排列
我希望输出为“val0 = 1; val1 = 2; val2 = 93;”
现在我将尝试recursion。 谢谢DrJokepu
我很惊讶没有人发布LINQ解决scheme。
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)
recursion解决scheme
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(); }
请注意，通过将返回值更改为string列表的列表并将retval.add调用更改为使用列表而不是串联来返回列表或数组，而不是string将非常容易。
怎么运行的：
这是一个经典的recursionalgorithm。 基本情况是foo(myList.Count, myList) ，它返回一个List，其中包含一个元素，即空string。 n个string数组s1，s2，…，sN的列表的排列等同于s1的每个成员，前缀为n-1个string数组s2，…，sN的排列。 基本情况就是为了将sN的每个元素连接到一起而提供的东西。
最近我遇到了一个类似的问题，在这个问题上偶然发现。 我需要一个可以处理任意对象列表的非recursion解决scheme。 这是我想出来的。 基本上，我正在为每个子列表形成一个枚举器列表，并迭代递增它们。
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); } }
你可以使用factoradics来产生排列的枚举。 在MSDN上尝试这篇文章，了解C＃中的实现。
无论添加到myList中的数组是多less，这都可以工作：
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; }
请注意，这不是真正的recursion。 可能是一个令人误解的函数名称。
这是一个符合你的新要求的版本。 注意我输出到控制台的部分，这是你可以做自己的格式的地方：
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; }
你要求的是笛卡尔积。 一旦你知道它叫什么，堆栈溢出有几个类似的问题。 他们似乎最终都指出了一个结果写成博客文章的答案：
http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx
非recursion解决scheme：
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 } } }
recursion解决scheme：
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; }
下面是我写的一个通用的recursion函数（和一个可能方便调用的重载）：
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
和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); }
使用方便：
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
或在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)); }
这是一个使用很less代码的版本，完全是声明性的
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))); }
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; } }
这是一个非recursion的非Linq解决scheme。 我不禁感觉到我可以less用循环，用分数和模来计算位置，但是不能把我的头围绕起来。
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; }
当我这样做了大量的代码时，我遇到的一个问题是，在布莱恩的例子中，我实际上已经耗尽了内存。 为了解决这个问题我使用了下面的代
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(); }
