algorithm - 遍历不同的唯一排列组合

Question

我很难开始为这个问题布局代码。

我有固定数量的随机数，在本例中为 8 个数字。 R[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

这将被放置在 3 组数字中，唯一的限制是每组至少包含一个值，并且每个值只能使用一次。 编辑:应使用所有 8 个数字

例如:

R1[] = { 1, 4 }

R2[] = { 2, 8, 5, 6 }

R3[] = { 7, 3 }

我需要遍历集合 R1、R2、R3 的所有可能组合。顺序并不重要，所以如果上面的例子发生了，我不需要

R1[] = { 4, 1 }

R2[] = { 2, 8, 5, 6 }

R3[] = { 7, 3 }

也不是

R1[] = { 2, 8, 5, 6 }

R2[] = { 7, 3 }

R3[] = { 1, 4 }

什么是好的方法？

Answer 1

我面前有 Knuth 第 4 卷，分册 3，生成所有组合和分区，第 7.2.1.5 节生成所有集合分区(分册第 61 页) .

首先，他详细介绍了 算法 H，按字典顺序限制增长字符串 归功于 George Hutchinson。它看起来很简单，但我现在不打算深入研究它。

在下一页详细说明集合分区的格雷码时，他思考:

Suppose, however, that we aren't interested in all of the partitions; we might want only the ones that have m blocks. Can we run this through the smaller collection of restricted growth strings, still changing one digit at a time?

然后他详细介绍了 Frank Ruskey 提出的解决方案。

简单的解决方案(并且肯定是正确的)是在 m==3 且所有分区都不是空集(根据您规定的约束)的分区上编写算法 H 过滤。我怀疑算法 H 运行得非常快，因此过滤成本不会很大。

如果您在 8051 上实现它，您可以从 Ruskey 算法开始，然后只过滤包含空集的分区。

如果您在小于 8051 和毫秒级的东西上实现它，您可以为三个分区中的每一个分区播种一个唯一元素(一个简单的三级嵌套循环)，然后通过在其余五个分区上进行扩充m==3 的元素使用 Ruskey 算法。您不必过滤任何内容，但您必须跟踪哪五个元素仍要分区。

从通用算法中过滤下来的好处是，您不必验证自己的聪明才智，而且您稍后会改变对约束的想法，而不必修改自己的聪明才智。

我什至可能稍后会想出一个解决方案，但目前仅此而已。

附言对于 Java 孔雀鱼:我发现在“George Hutchison restricted growth strings”上搜索某个包 ca.ubc.cs.kisynski.bell，其中包含实现 Hutchison 算法的方法 growthStrings() 的文档。

似乎可以在 http://www.cs.ubc.ca/~kisynski/code/bell/ 找到