Каков наилучший способ найти все комбинации элементов в массиве?

Question

Каков наилучший способ найти все комбинации элементов в массиве в c #?

Answer 1

ОБНОВЛЕНО

Вот набор общих функций (требуется .net 3.5 или выше) для различных сценариев. Выходы для списка {1, 2, 3, 4} и длины 2.

Перестановки с повторением

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

Выход:

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

Перестановка

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

Выход:

{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-комбинации с повторением

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

Выход:

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

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

Выход:

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

Answer 2

Это называется перестановками.

Это может дать вам перестановки любой коллекции:

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

}

Пример:

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

Answer 3

Это 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 4

Относительно ответа 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 }));
}

Пример 1: n = 3, k = 2

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

Вывод - список целочисленных списков:

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

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

Я использовал этот пример, и я не совсем уверен в правильности результатов.

Пример 2: n = 3, k = 3

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

Вывод - список целочисленных списков:

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

Это не должно происходить с комбинациями, в противном случае следует указать, что это повторение. См. Статью http://en.wikipedia.org/wiki/Combinations

Answer 5

Есть пары очень простых способов найти комбинацию ввода строки пользователем.

Первый способ с помощью 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;
        }

Используйте эту функцию как

Console.WriteLine("Enter a sting ");

            var input = Console.ReadLine();

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

Другой способ - использовать цикл

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

Вы можете использовать эту функцию как

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

Answer 6

Может быть kwcombinatorics может оказать некоторую помощь (см. Пример на домашней странице):

Библиотека KwCombinatorics - это 3 класса, которые предоставляют 3 различных способа создания упорядоченных (ранжированных) списков комбинаций чисел. Эти комбинаторики полезны для тестирования программного обеспечения, позволяя генерировать различные типы возможных комбинаций ввода. Другое использование включает решение математических задач и азартных игр.

Answer 7

Еще одна версия решения от 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;
        }

    }
}

Это на самом деле работает как следует для комбинаций. Но это не позволяет выбирать комбинации n в k ...

Answer 8

Подробный ответ см .: Дональд Кнут, Искусство компьютерного программирования (он же TAOCP). Том 4А, Перечисление и возврат, глава 7.2. Генерация всех возможностей. http://www -cs-faculty.stanford.edu / ~ уно / taocp.html

Answer 9

Я создал метод для получения уникальной комбинации всех целочисленных элементов в массиве, как показано ниже. Я использовал 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);
        }
    }

Когда я вызываю этот метод в консольном приложении, я получаю вывод ниже:

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