如何获取一组可重复元素的所有唯一n个元素组合？

Question

我发现很多解决方案会提供一个由所有可能的元素组合而成的集合，但它们在每个结果中只使用每个元素一次，而我需要将它们视为可重复使用。

例如，如果输入元素是 {"a", "b", "c"}，数目为 2，则输出应为 {"a", "a" }，{"a", "b"}，{"a", "c"}，{"b", "a"}，{"b", "b"}，{"b", "c"}，{"c", "a"}，{"c", "b"}，{"c", "c"}。

- Ivan

---

这被称为“带替换的组合”，在数学上等同于给定集合与集合{1,2,3...n}的笛卡尔积。通常你不会在库中找到它，因为它被认为太简单而不需要一个。正如你所指出的，不带替换的组合在库中很常见，因为它们更加棘手。 - Lee Daniel Crocker

Answer 1

假设你有N个输入元素，想要一个长度为K的组合。

你需要做的就是在基数为N的情况下计数，当然是限定范围的，只到所有K位数字的数。

所以，假设N={n0, n1, ... nN}，

你可以从数字[n0 n0 ... n0]开始，一直数到[nN nN ... nN]。

如果你需要帮助理解如何在另一个基数中计数，可以在这里找到。

每个计算出来的数字都对应着你需要的一个长度为K的组合。

我认为举个例子会更好。

我们使用您提供的值。 N={a, b, c} 因此我们想在基数3中计数。 由于我们想要2位组合，我们只关心2位数字。 最小的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

- V Maharajh

Answer 2

您可以使用深度优先搜索：

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

Answer 3

Eric Lippert提出了一种通用的方法，可以从任意数量的序列中生成笛卡尔积 他在这里写了相关博客。

他编写了一个扩展方法，如下所示：

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

Answer 4

简单 - 你只需要数数。如果你有3个元素，就像你的例子一样，并且想要所有两个元素的组合，你只需要从0数到8（3^2-1），并将结果视为一个以你的元素为数字的三进制数。

如果你有15个元素，并且想要8个元素的组合，你只需要从0数到15^8-1，并将你的结果视为一个以15为基数的数字。

- zmbq

Answer 5

你所要求的是排列而不是组合。通过对 n 个元素的 k 进行树遍历，可以找到唯一的组合。如果你想要 n 个元素中的 n 个元素是唯一的，答案是 1。

- TheJackal