3

我发现许多解决方案以所有可能的顺序组合了集合元素，但它们在每个结果中都只使用每个元素一次，而我需要将它们视为可重用。

例如，如果输入元素是 {"a", "b", "c"} 并且数字是 2，则输出是 {"a", "a"}, {"a", "b"}, { “a”、“c”}、{“b”、“a”}、{“b”、“b”}、{“b”、“c”}、{“c”、“a”}、{ “c”、“b”}、{“a”、“c”}。

4

5 回答 5

1

假设您有 N 个输入元素，并且您想要一个 K-long 组合。

您需要做的就是以 N 为底数，当然范围是所有具有 K 位数字的数字。

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

您将从数字 [n0 n0 ... n0] 开始，一直数到 [nN nN ... nN]

如果您在了解如何计算另一个基地方面需要帮助，您可以在此处获得

您计算的每个数字都映射到您需要的 K-long 组合之一。

我认为一个例子会有所帮助

我会使用你的价值观。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
于 2013-06-23T04:36:11.017 回答
1

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

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
于 2013-06-23T05:47:46.307 回答
1

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);
于 2013-06-23T09:09:17.140 回答
0

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

于 2013-09-20T08:44:52.150 回答
0

简单 - 你数。如果您有 3 个元素，如您的示例所示，并且想要所有两个元素的组合，您只需从 0 数到 8 (3^2 - 1)，并将结果视为以 3 为底的数字，元素为数字.

如果您有 15 个元素并想要 8 个元素的组合，则从 0 计数到 15^8-1 并将结果视为以 15 为底的数字。

于 2013-06-23T05:45:04.577 回答