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

Question

As the title...

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

Answer 1

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

Answer 2

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

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.

Answer 3

Use backtracking

Answer 4

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

Answer 5

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