C# 在数组中查找所有项目组合的最佳方法是什么？

What is the best way to find all combinations of items in an array?

提问by Bravax

What is the best way to find all combinations of items in an array in c#?

在 C# 中查找数组中所有项目组合的最佳方法是什么？

采纳答案by Ahmed Said

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

回答by gimel

Maybe kwcombinatoricscan provide some assistance (see example on home page):

也许kwcombinatorics可以提供一些帮助（参见主页上的示例）：

The KwCombinatorics library are 3 classes that provide 3 different ways of generating ordered (ranked) lists of combinations of numbers. These combinatorics are useful for software testing, allowing the generation of various types of possible combinations of input. Other uses include solving mathematical problems and games of chance.

KwCombinatorics 库是 3 个类，它们提供了 3 种不同的方法来生成数字组合的有序（排名）列表。这些组合对软件测试很有用，允许生成各种类型的可能输入组合。其他用途包括解决数学问题和机会游戏。

回答by Guffa

That's called permutations.

这就是所谓的排列。

This can give you the permutations of any collection:

这可以为您提供任何集合的排列：

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

}

Example:

例子：

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

回答by danatel

For detailed answer see: Donald Knuth, The Art of computer programming (aka TAOCP). Volume 4A, Enumeration and Backtracking, chapter 7.2. Generating all possibilities. http://www-cs-faculty.stanford.edu/~uno/taocp.html

有关详细答案，请参阅：Donald Knuth，计算机编程艺术（又名 TAOCP）。第 4A 卷，枚举和回溯，第 7.2 章。产生所有的可能性。 http://www-cs-faculty.stanford.edu/~uno/taocp.html

回答by Pengyang

UPDATED

更新

Here are a set of generic functions (require .net 3.5 or higher) for different scenarios. The outputs are for a list of {1, 2, 3, 4} and a length of 2.

以下是针对不同场景的一组通用函数（需要 .net 3.5 或更高版本）。输出用于 {1, 2, 3, 4} 和长度为 2 的列表。

Permutations with repetition

重复排列

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}

Permutations

排列

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-combinations with repetition

带重复的 K 组合

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

K-组合

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}

回答by abel406

Regarding Pengyang answer: Here is my generic function which can return all the combinations from a list of T:

关于 Pengyang 答案：这是我的通用函数，它可以返回 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 }));
}

Example 1:n=3,k=2

示例 1：n=3,k=2

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

Output - a list of integer-lists:

输出 - 整数列表列表：

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

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

………………………………………………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………………………………………

I ran this example and I am not quite sure about the rightness of the results.

我运行了这个例子，但我不太确定结果的正确性。

Example 2:n=3, k=3

示例 2：n=3，k=3

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

Output - a list of integer-lists:

输出 - 整数列表列表：

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

This should not happen with combinations otherwise it should specify it is with repetition.See article http://en.wikipedia.org/wiki/Combinations

这不应该发生在组合中，否则应该指定它是重复的。参见文章http://en.wikipedia.org/wiki/Combinations

回答by abel406

Another version of the solution given by Gufa. Below the complete source code of the class:

Gufa 给出的另一个版本的解决方案。下面是该类的完整源代码：

using System.Collections.Generic;

namespace ConsoleApplication1
{
    public class Permutation
    {

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

    }
}

This actually worked as it should for combinations.But is does not allow to chose combinations of n in k ...

这实际上适用于组合。但是不允许在 k 中选择 n 的组合......

回答by MANISH KUMAR CHOUDHARY

There are couples of very easy way to find the combination of string input by user.

有几种非常简单的方法可以找到用户输入的字符串组合。

First way by using LINQ

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

Use this function like

使用此功能，如

Console.WriteLine("Enter a sting ");

            var input = Console.ReadLine();

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

Other way is to use loop

另一种方法是使用循环

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

you can use this function like

你可以像这样使用这个功能

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

回答by RBT

I created a method to get the unique combination of all the integer elements in an array as shown below. I've used Tupleto represent a pair or combination of numbers:

我创建了一个方法来获取数组中所有整数元素的唯一组合，如下所示。我曾经用来Tuple表示一对或一组数字：

private static void CombinationsOfItemsInAnArray()    
{
        int[] arr = { 10, 50, 3, 1, 2 }; //unique elements

        var numberSet = new HashSet<int>();
        var combinationList = new List<Tuple<int, int>>();
        foreach (var number in arr)
        {
            if (!numberSet.Contains(number))
            {
                //create all tuple combinations for the current number against all the existing number in the number set
                foreach (var item in numberSet)
                    combinationList.Add(new Tuple<int, int>(number, item));

                numberSet.Add(number);
            }
        }

        foreach (var item in combinationList)
        {
            Console.WriteLine("{{{0}}} - {{{1}}}",item.Item1,item.Item2);
        }
    }

When I invoke this method in a console application then I get below output:

当我在控制台应用程序中调用此方法时，我得到以下输出：

{50} - {10}
{3} - {10}
{3} - {50}
{1} - {10}
{1} - {50}
{1} - {3}
{2} - {10}
{2} - {50}
{2} - {3}
{2} - {1}

回答by RooiWillie

How about some recursion?

一些递归怎么样？

internal HashSet<string> GetAllPermutations(IEnumerable<int> numbers)
{
  HashSet<string> results = new HashSet<string>();

  if (numbers.Count() > 0)
    results.Add(string.Join(",", new SortedSet<int>(numbers)));

  for (int i = 0; i <= numbers.Count() - 1; i++)
  {
    List<int> newNumbers = new List<int>(numbers);
    newNumbers.RemoveAt(i);
    results.UnionWith(GetAllPermutations(newNumbers));
  }

  return results;
}