Как получить все уникальные n-длинные комбинации из набора дублирующихся элементов?

c# algorithm combinatorics

1743 просмотра

5 ответа

28462 Репутация автора

Я нашел много решений, дающих элементы коллекции, объединенные во всех возможных порядках, но все они используют каждый элемент только один раз в каждом результате, в то время как мне нужно, чтобы они рассматривались как повторно используемые.

Например, если входными элементами являются {"a", "b", "c"} и число равно 2, выходные данные должны быть {"a", "a"}, {"a", "b"}, { "a", "c"}, {"b", "a"}, {"b", "b"}, {"b", "c"}, {"c", "a"}, { "c", "b"}, {"a", "c"}.

Автор: Ivan Источник Размещён: 23.06.2013 04:18

Ответы (5)


1 плюс

2945 Репутация автора

Допустим, у вас есть N входных элементов, и вы хотите комбинацию K-long.

Все, что вам нужно сделать, это посчитать в базе N, конечно же, для всех чисел, которые имеют K цифр.

Итак, скажем, N = {n0, n1, ... nN}

Вы начинаете с числа [n0 n0 ... n0] и отсчитываете до [nN nN ... nN]

Если вам нужна помощь в понимании того, как считать в другой базе, вы можете получить это здесь

Каждое вычисляемое вами число соответствует одной из нужных вам комбинаций K-длины.

Думаю пример поможет

Я буду использовать ваши ценности. N = {a, b, c} Итак, мы хотим сосчитать в базе 3. Поскольку нам нужны комбинации из двух длин, нам важны только двузначные числа. Наименьшее 2-значное основание 3 - 00, поэтому мы начнем с него. Подсчитав в базе 3, мы получим:

00
01
02
10
11
12
20
21
22

Итак, теперь, чтобы преобразовать эти числа в комбинацию.

Помните, что наш набор {a, b, c}

Таким образом, всякий раз, когда мы видим 0, это подразумевает 1. Где бы мы ни видели 1, это подразумевает 2, и я уверен, что вы можете догадаться, что подразумевает 2 :)

00              aa
01              ab
02              ac
10   0 => a     ba
11   1 => b     bb
12   2 => c     bc
20              ca
21              cb
22              cc
Автор: Vivek Maharajh Размещён: 23.06.2013 04:36

0 плюса

30375 Репутация автора

Просто - считай. Если у вас есть 3 элемента, как в вашем примере, и вы хотите получить все двухэлементные комбинации, вы просто считаете от 0 до 8 (3 ^ 2 - 1) и рассматриваете результат как число base-3 с вашими элементами в качестве цифр ,

Если у вас 15 элементов и вы хотите комбинации из 8 элементов, вы считаете от 0 до 15 ^ 8-1 и рассматриваете свой результат как число с базовым числом 15.

Автор: zmbq Размещён: 23.06.2013 05:45

1 плюс

0 Репутация автора

Вы можете использовать поиск в глубину :

class Program
{
    private static string[] letters = {"a", "b", "c"};
    private static void dfs(string accum, int depth)
    {
        if (depth == 0)
        {
            System.Console.WriteLine(accum);
            return;
        }
        foreach (string c in letters)
            dfs(accum + c, depth - 1);
    }
    public static void Main()
    {
        int depth = 2; //Number of letters in each result
        dfs("", depth);
        System.Console.ReadLine();
    }
}


Выход:

aa
ab
ac
ba
bb
bc
ca
cb
cc
Автор: user2134086 Размещён: 23.06.2013 05:47

1 плюс

77760 Репутация автора

Эрик Липперт представил универсальный метод генерации декартового произведения из любого числа последовательностей, о которых он пишет здесь .

Он написал метод расширения, который выглядит следующим образом:

public static class Combinations
{
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
            emptyProduct,
            (accumulator, sequence) =>
            from accseq in accumulator
            from item in sequence
            select accseq.Concat<T>(new[] { item }));
    }
}

Учитывая этот метод расширения, решение исходной проблемы может быть сделано следующим образом:

var items = new[] { "a", "b", "c" };

int numInEachSelection = 2;

var combs = Enumerable.Repeat(items, numInEachSelection).CartesianProduct();

foreach (var comb in combs)
    Console.WriteLine(string.Join(", ", comb));

Обратите внимание, что combsэто IEnumerable<IEnumerable<string>>- это последовательность перечислимых элементов, каждая из которых представляет собой последовательность, представляющую одну комбинацию.

Если вам не нужен такой метод общего назначения, и вы рады, что каждая комбинация находится в отдельном объекте с вызываемыми свойствами Item1и Item2для двух комбинированных элементов, самый простой способ это:

var items = new[] { "a", "b", "c" };

var combs = from Item1 in items from Item2 in items select new {Item1, Item2};

foreach (var comb in combs)
    Console.WriteLine(comb);
Автор: Matthew Watson Размещён: 23.06.2013 09:09

0 плюса

315 Репутация автора

То, что вы просите, это перестановки, а не комбинации. Уникальные комбинации могут быть найдены путем обхода дерева k из n элементов. Если вы хотите, чтобы n из n элементов были уникальными, ответ будет 1

Автор: TheJackal Размещён: 20.09.2013 08:44
Вопросы из категории :
32x32