2

我需要通过组合其中的数字来减小集合的大小。我需要所有可能的组合。这里有两个例子可以说明我的情况。

1) Set1 有 4 个条目，而 Set2 有 2 个。所以我们需要在每种情况下组合两个数字。

Set1 = {70, 100, 50, 200}; Set2 = {"part1", "part2"}
All combinations I want to retrive should look like following:
"part1"        |"part2"
  70 + 100       |  50 + 200
  70 + 50        | 100 + 200
  70 + 200       |  50 + 100
 100 + 50       |  70 + 200
 100 + 200      |  50 +  70
  50 + 200       | 100 +  70
 50             |  70 + 100 + 200
 70             |  50 + 100 + 200
 100            |  50 +  70 + 200
 200            |  50 +  70 + 100  
 70 + 100 + 200 |  50
 50 + 100 + 200 |  70
 50 +  70 + 200 |  100
 50 +  70 + 100 |  200

2) Set1 有 4 个条目，而 Set2 有 3 个条目。所以我们只需将两个数字组合一次。

Set1 = {70, 100, 50, 200}; Set2 = {"part1", "part2", "part3"}
All combinations I want to retrive should look like following:
"part1"   |"part2"     |"part3"
   70        | 100        |  50 + 200
   70        |  50        | 100 + 200
   70        | 200        |  50 + 100
   50        |  70        | 100 + 200 
   50        | 100        |  70 + 200
   50        | 200        |  70 + 100
 100       |  70        |  50 + 200
 100       | 200        |  50 +  70
 100       |  50        | 200 +  70
 200       |  70        |  50 + 100
 200       | 100        |  50 +  70
 200       |  50        |  70 + 100
   70        |  50 + 200  |  100
   70        | 100 + 200  |   50
   70        |  50 + 100  |  200
   50        | 100 + 200  |   70
   50        | 200 + 70   |  100
   50        |  70 + 100  |  200
 100       |  50 + 200  |   70
 100       |  50 +  70  |  200
 100       | 200 +  70  |   50
 200       |  50 + 100  |   70
 200       |  50 +  70  |  100
 200       |  70 + 100  |   50 
   50 + 200  | 100        |  70
 100 + 200 |  50        |  70
   50 + 100  | 200        |  70
 100 + 200 |  70        |  50
   70 + 200  | 100        |  50
   70 + 100  | 200        |  50
   50 + 200  |  70         | 100
   50 +  70  | 200         | 100
 200 +  70 |  50         | 100
   50 + 100  |  70         | 200
   50 +  70  | 100         | 200
   70 + 100  |  50         | 200

我很感激任何帮助。我想不出任何词语来更好地解释我的担忧。但我很乐意回答任何问题。在你的帮助下，我也许能够证实我的问题。虽然应用程序是用 C# 编写的，但我不一定需要源代码。我的问题是概念而不是实现。

提前致谢！

4

2 回答 2

0

您的问题的主要困难是：

如何获取给定集合的所有子集？

这是我的想法：我想你的第一组不会超过 32 个元素。否则，结果将是相当巨大的。

然后，对于给定的集合MySet = { a, b, c, d, e }，该集合的每个子集都可以用 和 之间的值来0描述2^5 - 1。

如何 ？

使用位！OK 例如，数字5（00101二进制​​）表示，a并且c包含在子集中。

所以要拥有给定N元素集的子集的整个集合。只需从迭代0到2^N-1排除。

那么，如何创建其他部分（最后一个除外）？

只需获取第一组的补码并迭代其子集即可。

那么，最后一部分呢？

获取您之前部分的补充！

使用这种技术可能不必寻找前一个子集的补码，但它需要一些非标准的按位运算。

于 2013-01-21T14:17:34.303 回答
0

好的，所以这里的总体思路是

  • 从 -开始，{0, 0, 0, 0}对于Set1.
  • 0表示 中的第一项Set2。因此，第一个数组是“中的所有内容都Set1属于中的第一项Set2”。
  • 返回与此对应的分区。
  • 增量{0, 0, 0, 0}为{0, 0, 0, 1}。
  • 1表示 中的第二项Set2。因此，这个数组是“中的所有内容都Set1属于 中的第一项Set2，除了最后一项，它属于中的第二项Set2”。
  • 返回与此对应的分区。
  • 增加{0, 0, 0, 1}（{0, 0, 1, 0}或者{0, 0, 0, 2}如果您有超过 2 个项目Set2）。
  • 重复直到你击中{1, 1, 1, 1}（或{2, 2, 2, 2}等）并且不能再进一步。

然后，您可以添加逻辑说“如果分区有任何空白部分，请不要打扰它”。

我实现了如下：

static IEnumerable<ILookup<T, U>> Pool<T, U>(T[] t, U[] u)
{
    // Start off with all zeroes.
    int[] indices = new int[u.Length];

    while (true)
    {
        // Build a Lookup from the array.
        var lookup = (Lookup<T,U>)indices
            .Select((ti, ui) => new { U = u[ui], T = t[ti] })
            .ToLookup(p => p.T, p => p.U);
        // Only return it if every part is non-empty.
        if (lookup.Count == t.Length)
            yield return lookup;

        // Increment to the next value.
        int toIncrement = u.Length - 1;
        while (++indices[toIncrement] == t.Length)
        {
            indices[toIncrement] = 0;

            // Stop when we can't increment further.
            if (toIncrement-- == 0)
                yield break;
        }
    }
}

你可以称之为

foreach (var q in Pool(
    new[] { "part1", "part2" },
    new[] { 70, 100, 50, 200 }))
{
    foreach (int i in q["part1"])
        Console.Write(i + " ");
    Console.Write("| ");
    foreach (var ii in q["part2"])
        Console.Write(ii + " ");
    Console.WriteLine();
}

注意我已经制作了我的参数数组，因为我很懒，但是您可以将它们列出，或者将它们设为可枚举并调用ToArray它们。

于 2013-01-21T14:29:27.533 回答