Cách tốt nhất để tìm tất cả các kết hợp của các mục trong một mảng là gì?

Question

Cách tốt nhất để tìm tất cả các kết hợp của các mục trong một mảng trong C# là gì?

Answer 1

Nó là O (n!)

static List<List<int>> comb; 
static bool[] used; 
static void GetCombinationSample() 
{ 
    int[] arr = { 10, 50, 3, 1, 2 }; 
    used = new bool[arr.Length]; 
    used.Fill(false); 
    comb = new List<List<int>>(); 
    List<int> c = new List<int>(); 
    GetComb(arr, 0, c); 
    foreach (var item in comb) 
    { 
     foreach (var x in item) 
     { 
      Console.Write(x + ","); 
     } 
     Console.WriteLine(""); 
    } 
} 
static void GetComb(int[] arr, int colindex, List<int> c) 
{ 

    if (colindex >= arr.Length) 
    { 
     comb.Add(new List<int>(c)); 
     return; 
    } 
    for (int i = 0; i < arr.Length; i++) 
    { 
     if (!used[i]) 
     { 
      used[i] = true; 
      c.Add(arr[i]); 
      GetComb(arr, colindex + 1, c); 
      c.RemoveAt(c.Count - 1); 
      used[i] = false; 
     } 
    } 
} 

Answer 2

lẽ kwcombinatorics có thể cung cấp một số hỗ trợ (xem ví dụ trên trang nhà):

Thư viện KwCombinatorics 3 lớp cung cấp 3 cách khác nhau tạo ra các danh sách (xếp hạng) được sắp xếp theo thứ tự các kết hợp các số. Những tổ hợp này rất hữu ích cho việc kiểm thử phần mềm, cho phép tạo ra nhiều loại kết hợp đầu vào có thể có khác nhau. Các ứng dụng khác bao gồm giải quyết các vấn đề toán học và các trò chơi may rủi.

Answer 3

Được gọi là hoán vị.

này có thể cung cấp cho bạn các hoán vị của bất kỳ bộ sưu tập:

public class Permutation { 

    public static IEnumerable<T[]> GetPermutations<T>(T[] items) { 
    int[] work = new int[items.Length]; 
    for (int i = 0; i < work.Length; i++) { 
     work[i] = i; 
    } 
    foreach (int[] index in GetIntPermutations(work, 0, work.Length)) { 
     T[] result = new T[index.Length]; 
     for (int i = 0; i < index.Length; i++) result[i] = items[index[i]]; 
     yield return result; 
    } 
    } 

    public static IEnumerable<int[]> GetIntPermutations(int[] index, int offset, int len) { 
    if (len == 1) { 
     yield return index; 
    } else if (len == 2) { 
     yield return index; 
     Swap(index, offset, offset + 1); 
     yield return index; 
     Swap(index, offset, offset + 1); 
    } else { 
     foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) { 
     yield return result; 
     } 
     for (int i = 1; i < len; i++) { 
     Swap(index, offset, offset + i); 
     foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) { 
      yield return result; 
     } 
     Swap(index, offset, offset + i); 
     } 
    } 
    } 

    private static void Swap(int[] index, int offset1, int offset2) { 
    int temp = index[offset1]; 
    index[offset1] = index[offset2]; 
    index[offset2] = temp; 
    } 

} 

Ví dụ:

string[] items = { "one", "two", "three" }; 
foreach (string[] permutation in Permutation.GetPermutations<string>(items)) { 
    Console.WriteLine(String.Join(", ", permutation)); 
} 

Answer 4

Đối với câu trả lời chi tiết xem: Donald Knuth, Nghệ thuật lập trình máy tính (aka TAOCP). Volume 4A, Enumeration và Backtracking, chương 7.2. Tạo tất cả các khả năng. http://www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 5

CẬP NHẬT

Dưới đây là một tập hợp các chức năng chung (yêu cầu .net 3.5 hoặc cao hơn) cho các kịch bản khác nhau. Các đầu ra là một danh sách {1, 2, 3, 4} và chiều dài là 2.

hoán vị với sự lặp lại

static IEnumerable<IEnumerable<T>> 
    GetPermutationsWithRept<T>(IEnumerable<T> list, int length) 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 
    return GetPermutationsWithRept(list, length - 1) 
     .SelectMany(t => list, 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Output:

{1,1} {1,2} {1,3} {1,4} {2,1} {2,2} {2,3} {2,4} {3,1} {3,2} {3,3} {3,4} {4,1} {4,2} {4,3} {4,4} 

hoán vị

static IEnumerable<IEnumerable<T>> 
    GetPermutations<T>(IEnumerable<T> list, int length) 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 
    return GetPermutations(list, length - 1) 
     .SelectMany(t => list.Where(o => !t.Contains(o)), 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Output:

{1,2} {1,3} {1,4} {2,1} {2,3} {2,4} {3,1} {3,2} {3,4} {4,1} {4,2} {4,3} 

K-kết hợp với sự lặp lại

static IEnumerable<IEnumerable<T>> 
    GetKCombsWithRept<T>(IEnumerable<T> list, int length) where T : IComparable 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 
    return GetKCombsWithRept(list, length - 1) 
     .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0), 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Output:

{1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4} 

K-kết hợp

static IEnumerable<IEnumerable<T>> 
    GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 
    return GetKCombs(list, length - 1) 
     .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
      (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Output :

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4} 

Answer 6

Về Pengyang câu trả lời: Đây là chức năng của tôi chung chung mà có thể trả lại tất cả các kết hợp từ một danh sách các T:

static IEnumerable<IEnumerable<T>> 
    GetCombinations<T>(IEnumerable<T> list, int length) 
{ 
    if (length == 1) return list.Select(t => new T[] { t }); 

    return GetCombinations(list, length - 1) 
     .SelectMany(t => list, (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

Ví dụ 1: n = 3, k = 2

IEnumerable<IEnumerable<int>> result = 
    GetCombinations(Enumerable.Range(1, 3), 2); 

Output - một danh sách các số nguyên-danh sách:

{1, 1} {1, 2} {1, 3} {2, 1} {2, 2} {2, 3} {3, 1} {3, 2} {3, 3} 

................................................ .............................

Tôi đã chạy ví dụ này và tôi không hoàn toàn chắc chắn về tính đúng đắn của kết quả.

Ví dụ 2: n = 3, k = 3

IEnumerable<IEnumerable<int>> result = 
    GetCombinations(Enumerable.Range(1, 3), 3); 

Output - một danh sách các số nguyên-danh sách:

{1, 1, 1} {1, 1, 2} {1, 1, 3} 
{1, 2, 1} {1, 2, 2} {1, 2, 3} 
{1, 3, 1} {1, 3, 2} {1, 3, 3} 
{2, 1, 1} {2, 1, 2} {2, 1, 3} 
{2, 2, 1} {2, 2, 2} {2, 2, 3} 
{2, 3, 1} {2, 3, 2} {2, 3, 3} 
{3, 1, 1} {3, 1, 2} {3, 1, 3} 
{3, 2, 1} {3, 2, 2} {3, 2, 3} 
{3, 3, 1} {3, 3, 2} {3, 3, 3} 

này không nên xảy ra với sự kết hợp nếu không nó nên xác định nó là với repetition.See article http://en.wikipedia.org/wiki/Combinations

Answer 7

Một phiên bản khác của giải pháp do Gufa đưa ra. Bên dưới mã nguồn hoàn chỉnh của lớp học:

bằng System.Collections.Chung;

namespace ConsoleApplication1 { public class hoán vị {

public IEnumerable<T[]> GetPermutations<T>(T[] items) 
    { 
     var work = new int[items.Length]; 
     for (var i = 0; i < work.Length; i++) 
     { 
      work[i] = i; 
     } 
     foreach (var index in GetIntPermutations(work, 0, work.Length)) 
     { 
      var result = new T[index.Length]; 
      for (var i = 0; i < index.Length; i++) result[i] = items[index[i]]; 
      yield return result; 
     } 
    } 

    public IEnumerable<int[]> GetIntPermutations(int[] index, int offset, int len) 
    { 
     switch (len) 
     { 
      case 1: 
       yield return index; 
       break; 
      case 2: 
       yield return index; 
       Swap(index, offset, offset + 1); 
       yield return index; 
       Swap(index, offset, offset + 1); 
       break; 
      default: 
       foreach (var result in GetIntPermutations(index, offset + 1, len - 1)) 
       { 
        yield return result; 
       } 
       for (var i = 1; i < len; i++) 
       { 
        Swap(index, offset, offset + i); 
        foreach (var result in GetIntPermutations(index, offset + 1, len - 1)) 
        { 
         yield return result; 
        } 
        Swap(index, offset, offset + i); 
       } 
       break; 
     } 
    } 

    private static void Swap(IList<int> index, int offset1, int offset2) 
    { 
     var temp = index[offset1]; 
     index[offset1] = index[offset2]; 
     index[offset2] = temp; 
    } 

} 

}

Điều này thực sự làm việc như nó nên cho combinations.But là không cho phép để chọn kết hợp của n trong k ...

Answer 8

Có các cặp vợ chồng rất dễ dàng để tìm ra sự kết hợp đầu vào chuỗi của người dùng.

cách đầu tiên bằng cách sử dụng LINQ

private static IEnumerable<string> FindPermutations(string set) 
     { 
      var output = new List<string>(); 
      switch (set.Length) 
      { 
       case 1: 
        output.Add(set); 
        break; 
       default: 
        output.AddRange(from c in set let tail = set.Remove(set.IndexOf(c), 1) from tailPerms in FindPermutations(tail) select c + tailPerms); 
        break; 
      } 
      return output; 
     } 

Sử dụng chức năng này như

Console.WriteLine("Enter a sting "); 

      var input = Console.ReadLine(); 

      foreach (var stringCombination in FindPermutations(input)) 
      { 
       Console.WriteLine(stringCombination); 
      } 
      Console.ReadLine(); 

cách khác là sử dụng vòng lặp

// 1. remove first char 
    // 2. find permutations of the rest of chars 
    // 3. Attach the first char to each of those permutations. 
    //  3.1 for each permutation, move firstChar in all indexes to produce even more permutations. 
    // 4. Return list of possible permutations. 
    public static string[] FindPermutationsSet(string word) 
    { 
     if (word.Length == 2) 
     { 
      var c = word.ToCharArray(); 
      var s = new string(new char[] { c[1], c[0] }); 
      return new string[] 
      { 
       word, 
       s 
      }; 
     } 
     var result = new List<string>(); 
     var subsetPermutations = (string[])FindPermutationsSet(word.Substring(1)); 
     var firstChar = word[0]; 
     foreach (var temp in subsetPermutations.Select(s => firstChar.ToString() + s).Where(temp => temp != null).Where(temp => temp != null)) 
     { 
      result.Add(temp); 
      var chars = temp.ToCharArray(); 
      for (var i = 0; i < temp.Length - 1; i++) 
      { 
       var t = chars[i]; 
       chars[i] = chars[i + 1]; 
       chars[i + 1] = t; 
       var s2 = new string(chars); 
       result.Add(s2); 
      } 
     } 
     return result.ToArray(); 
    } 

bạn có thể sử dụng chức năng này như

Console.WriteLine("Enter a sting "); 

     var input = Console.ReadLine(); 

     Console.WriteLine("Here is all the possable combination "); 
     foreach (var stringCombination in FindPermutationsSet(input)) 
     { 
      Console.WriteLine(stringCombination); 
     } 
     Console.ReadLine();