2

你好说我有一些数据A -> ....（n个数据点）。现在我从这些数据中获取给定数量的值 (m) - 现在我希望遍历这些值的所有唯一组合。

5 个值的示例，其中 2 个是唯一的：唯一的组合类似于“a + b”或“a + c” - 但是“c + d”与“b + c”相同。“B + E”与“A + D”相同

A x x x x 
B x       x x
C   x     x 
D     x     x
E       x

这些描述了一些几何“线”，整个标本可以围绕中点“镜像”。因此，对于任意数量的行，考虑到这种“镜像能力”，是否有一种聪明的算法可以迭代所有内容？

在给定集合大小 n 和项目数 m 的情况下，计算元素数的公式是什么？

---- “3 out 6”的示例：
它也非常类似于函数 combine(6,3) - 但是现在我用 - 而不是 x 标记了重复的行。

                    1 1 1 1 1 1 1 1 1 1 2
  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
A x x x x x x x x - -                     A
B x x x x             x x - - - -         B
C x       x x x       x x -       - - -   C
D   x     x     x -   x     - -   - -   - D
E     x     x   x   -   x   -   - -   - - E
F       x     x   - -     -   - - - - - - F

所以可能的清单是：

ABC、ABD、ABE、ABF、ACD、ACE、ACF、ADE、BCD、BCE

20 个潜在候选人中有 10 个忽略了对称性。

4

2 回答 2

1

不容易。事实上，这是相当困难的。但这里是纲要：

for_each_unmirrored() 
   mark first element as part of the set.
   mark last element as definitely NOT part of the set.
   //we know no matter whats inside, this isnt't semetrical, so all combinations
   for_each_mirrored() on all elements between these.

   mark first element as part of the set.
   mark last element as part of the set.
   //ends are semetrical, so insides cannot be
   for_each_unmirrored() on all elements between these

   mark first element as definitely not part of the set.
   mark last element as definitely not in the set.
   //ends are semetrical, so insides cannot be
   for_each_unmirrored() on all elements between these

for_each_mirrored() 
    for each element
        mark it as part of the set.
        if more elements are needed
            for_each_mirrored on elements to the right but in range

是的，即使是简化的伪代码也很复杂。真正的代码在这里：http: //ideone.com/WDEn40（包括显示它适用于 6 个元素选择 3）。链接的代码并不像它可能的那么简单，因为我对其进行了优化以避免分配并最小化函数调用。（作为副作用，for_each_call_helper不是线程安全的。如果这需要是线程安全的，只需static从该函数的变量中删除关键字。）

于 2013-06-05T17:35:48.693 回答
0

我承认我也不完全理解这个问题。但是，解决此类问题的一般方法是提出一个好的符号和规范形式，以及将某些内容转换为规范形式的算法。然后，您只需在规范形式上做繁重的工作，不要重复。

于 2013-06-05T02:02:17.857 回答