What is the best way to find all combinations of i

问题:

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

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

回答2:

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}

回答3:

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

回答4:

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

回答5:

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.

回答6:

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

回答7:

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

回答8:

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

回答9:

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}