通过不同组的独特排列环 [英] Loop through different sets of unique permutations

问题描述

我有一个很难入门的布局code这个问题。

I'm having a hard time getting started to layout code for this problem.

我有一个固定量的随机数，在这种情况下，8号。 ř[] = {1，2，3，4，5，6，7，8};

I have a fixed amount of random numbers, in this case 8 numbers. R[] = { 1, 2, 3, 4, 5, 6, 7, 8 };

这将要被放置在3组数字，条件是每一组包含最小的一个值的唯一约束，并且每个值只能使用一次。 修改：所有的8个数字，应使用

That are going to be placed in 3 sets of numbers, with the only constraint that each set contain minimum one value, and each value can only be used once. all 8 numbers should be used

例如：

R1 [] = {1，4}

R1[] = { 1, 4 }

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

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

R3 [] = {7,3}

R3[] = { 7, 3 }

我需要循环通过一组R1，R2，R3中所有可能的组合。顺序并不重要，因此如果在上面的例子中发生的事情，我不需要

I need to loop through all possible combinations of a set R1, R2, R3. Order is not important, so if the above example happened, I don't need

R1 [] = {4,1}

R1[] = { 4, 1 }

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

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

R3 [] = {7,3}

R3[] = { 7, 3 }

和

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

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

R2 [] = {7,3}

R2[] = { 7, 3 }

R3 [] = {1，4}

R3[] = { 1, 4 }

有什么好方法？

推荐答案

我在我的面前克努特第4卷，分册3，生成的所有组合和分区的，第7.2.1.5的生成所有分区集的（专册第61页）。

I have in front of me Knuth Volume 4, Fascicle 3, Generating all Combinations and Partitions, section 7.2.1.5 Generating all set partitions (page 61 in fascicle).

首先，他详细介绍算法H，限制增长的字典顺序串的由于乔治·哈钦森。这看起来很简单，但我不打算潜入它只是现在。

First he details Algorithm H, Restricted growth strings in lexicographic order due to George Hutchinson. It looks simple, but I'm not going to dive into it just now.

在下制定的灰色codeS为组分区的思考，他的下一个页面：

On the next page under an elaboration Gray codes for set partitions he ponders:

假设，我们不感兴趣的分区中的所有的;我们可能希望只有那些有 M 的块。我们可以运行这个通过限制成长串的小集合，还是改变一个数字的时间？

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?

接着，他详细介绍，由于弗兰克Ruskey的解决方案。

Then he details a solution due to Frank Ruskey.

简单的解决方案（和一些是正确的）是$ C C上的分区算法^ h过滤，其中米== 3 $并没有一个分区是空的（根据你的陈述约束）设置。我怀疑算法^ h运行速度极快，因此过滤成本并不大。

The simple solution (and certain to be correct) is to code Algorithm H filtering on partitions where m==3 and none of the partitions are the empty set (according to your stated constraints). I suspect Algorithm H runs blazingly fast, so the filtering cost will not be large.

如果你在8051实现这一点，你可能会开始与Ruskey算法，然后只筛选包含空集的分区。

If you're implementing this on an 8051, you might start with the Ruskey algorithm and then only filter on partitions containing the empty set.

如果你的东西比8051毫秒事小，实施这个，你可以种子每三个分区中的一个独特的元素（三个级别的简单循环嵌套），然后通过分区增加对其余五元素使用Ruskey算法米== 3 。你不会有过滤什么，但你必须要跟踪哪些五行继续进行分区。

If you're implementing this on something smaller than an 8051 and milliseconds matter, you can seed each of the three partitions with a unique element (a simple nested loop of three levels), and then augment by partitioning on the remaining five elements for m==3 using the Ruskey algorithm. You won't have to filter anything, but you do have to keep track of which five elements remain to partition.

有关从通用算法过滤下来的好处是，你不必验证自己的任何聪明的，你以后对你的约束改变你的想法，而无需修改你的聪明才智。

The nice thing about filtering down from the general algorithm is that you don't have to verify any cleverness of your own, and you change your mind later about your constraints without having to revise your cleverness.

我可能会更晚工作的一个解决方案，但是这就是现在。

I might even work a solution later, but that's all for now.

P.S。为Java孔雀鱼：我发现搜索的乔治·和记禁区成长串与法growthStrings文件（一定包ca.ubc.cs.kisynski.bell），它实现了和记算法。

P.S. for the Java guppies: I discovered searching on "George Hutchison restricted growth strings" a certain package ca.ubc.cs.kisynski.bell with documentation for method growthStrings() which implements the Hutchison algorithm.

看起来可用的 HTTP：//www.cs。 ubc.ca/~kisynski/$c$c/bell/

这篇关于通过不同组的独特排列环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！