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

What is the best way to find all combinations of i开发者_StackOverflow社区tems in an array in C#?

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.

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

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

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}

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

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

Regarding Pengyang answer: Here is my generic function which can return all the combinations from a list of 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

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

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

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.

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

First way by using 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();

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

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

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

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

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

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}

permutations with repetitions, but iterative (not recursive). It uses an array with all current indexes, and increments them as if they were the digits of a number :

/// <summary>
/// Generates combinations with repetitions
/// </summary>
/// <typeparam name="T">Type of items to combine.</typeparam>
/// <param name="items">Array of items. Will not be modified.</param>
/// <param name="length">Length of combinations, equal to <paramref name="items"/> length if null</param>
/// <param name="reverse">If changes should begin with array end (high indexes) first</param>
/// <returns>Combinations of input items.</returns>
public static IEnumerable<T[]> Combinations<T>(this T[] items, int? length = null, bool reverse = true)
{
    var itemsLength = items.Length;
    var combinationLength = length ?? itemsLength;
    var indexes = new int[combinationLength];

    var overflow = false;
    while (!overflow)
    {
        var combination = new T[combinationLength];
        for (var i = 0; i < combinationLength; i++)
            combination[i] = items[indexes[reverse ? combinationLength - i - 1 : i]];
        yield return combination;

        overflow = true;
        for (var i = 0; i < combinationLength && overflow; i++)
        {
            var index = indexes[i] + 1;
            overflow = index == itemsLength;
            indexes[i] = overflow ? 0 : index;
        }
    }
}

Output for new[] { 1, 2, 3}.Combinations(2, true) :

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

Output for new[] { 1, 2, 3}.Combinations(2, false) :

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