Как рассчитать комбинации n элементов без повторений [дубликат]

Относительно ответа 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/ вики / Комбинация

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

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

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

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

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

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

Другая версия решения, предоставленного 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 ...

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

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

UPDATED

Вот набор общих функций (требуется .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}