C# Sự hoán vị của một mảng các arraylists?

Question

Tôi có một ArrayList [] myList và tôi đang cố tạo một danh sách tất cả các hoán vị của các giá trị trong mảng.

VÍ DỤ: (tất cả các giá trị là chuỗi)

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

Số đếm myList có thể thay đổi để chiều dài của nó không được biết trước.

Tôi muốn có thể tạo danh sách tất cả các hoán vị tương tự như sau (nhưng với một số định dạng bổ sung).

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

Điều này có ý nghĩa với những gì tôi đang cố gắng hoàn thành không? Tôi dường như không thể đưa ra một phương pháp tốt để làm điều này, (nếu có).

Chỉnh sửa:
Tôi không chắc liệu đệ quy có ảnh hưởng đến mong muốn định dạng đầu ra theo cách của riêng tôi hay không. Xin lỗi tôi đã không đề cập đến trước khi định dạng của tôi là gì.

Tôi muốn kết thúc xây dựng một string [] array của tất cả các kết hợp tuân theo định dạng như dưới đây:

cho "1 2 93" hoán vị

Tôi muốn đầu ra là "val0 = 1; val1 = 2; val2 = 93; "

Tôi sẽ thử nghiệm với đệ quy ngay bây giờ. Cảm ơn bạn DrJokepu

Answer 1

Non-recursive giải pháp:

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

giải pháp đệ quy:

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

giải pháp đệ quy

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

Lưu ý rằng nó sẽ là khá dễ dàng để trả về một danh sách hoặc mảng thay vì một chuỗi bằng cách thay đổi trở lại thành danh sách các chuỗi và thay đổi giá trị .add gọi để làm việc với một danh sách thay vì sử dụng nối.

Cách hoạt động:

Đây là một thuật toán đệ quy cổ điển. Vỏ cơ sở là foo(myList.Count, myList), trả về một Danh sách chứa một phần tử, một chuỗi rỗng. Sự hoán vị của một danh sách các mảng chuỗi n s1, s2, ..., sN bằng với mỗi thành viên của sA1 tiền tố với hoán vị của các mảng chuỗi n-1, s2, ..., sN. Trường hợp cơ sở là chỉ có để cung cấp một cái gì đó cho mỗi phần tử của sN được nối vào.

Answer 3

này sẽ làm việc dù có bao nhiêu mảng bạn thêm vào myList của bạn:

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

Lưu ý rằng nó không thực sự đệ quy. Có thể là tên hàm sai lệch.

Đây là phiên bản tuân thủ các yêu cầu mới của bạn.Lưu ý phần mà tôi ra để an ủi, đây là nơi mà bạn có thể làm định dạng của riêng bạn:

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

Bạn có thể sử dụng để tạo ra các factoradics liệt kê các hoán vị. Hãy thử this article on MSDN để thực hiện trong C#.

Answer 5

Tôi rất ngạc nhiên khi không có ai đăng giải pháp 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

Đây là một hàm tổng quát đệ quy mà tôi đã viết (và một tình trạng quá tải có thể được thuận tiện để gọi):

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 

Và tương đương trong 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); 
} 

Dễ sử dụng:

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 

hoặc trong 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

Gần đây, tôi đã gặp phải vấn đề tương tự trong dự án của tôi và tình cờ gặp phải câu hỏi này. Tôi cần một giải pháp không đệ quy có thể làm việc với các danh sách các đối tượng tùy ý. Đây là những gì tôi nghĩ ra. Về cơ bản tôi đang hình thành một danh sách các điều tra viên cho mỗi danh sách phụ và tăng chúng lặp đi lặp lại.

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

Đây là một phiên bản trong đó sử dụng rất ít mã, và là hoàn toàn declarative

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

gì bạn đang yêu cầu được gọi là sản phẩm Descartes. Một khi bạn biết nó được gọi là gì, có một số câu hỏi tương tự trên Stack Overflow. Họ tất cả dường như kết thúc trỏ đến một câu trả lời mà đã kết thúc được viết như một bài viết trên blog:

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

Answer 11

Dưới đây là một giải pháp không đệ quy, không LINQ. Tôi không thể không cảm thấy như tôi có thể có vòng lặp ít hơn và tính toán các vị trí với phân chia và modulo, nhưng không thể hoàn toàn quấn quanh đầu tôi.

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

Một trong những vấn đề tôi gặp khi tôi làm điều này với số lượng mã rất lớn là với ví dụ brian được cho là tôi thực sự hết bộ nhớ. Để giải quyết điều này tôi đã sử dụng mã sau đây.

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