代码之家 › 专栏 › 技术社区 › ypnos

查找具有k大小子集的n个元素的所有可能分区,其中两个元素只共享一次同一集合

combinatorics permutation partitioning

1

ypnos · 技术社区 · 15 年前

我有n个元素需要划分成x个集合,每个集合必须正好容纳k=4个元素。

我需要找到所有可能的分区,其中的约束是每对元素只共享一次相同的集合。

因此,如果我从[1 2 3 4][5 6 7 8][…]开始,所有连续的分区都不能容纳,例如[1 2 x x x]或[x x 1 3]。集合无序。

接近这个问题的是 stirling numbers of the second kind . 但是,它们只解决了任意大小集的问题。

例子: 我有32只老鼠,可以放在8个笼子里,每个笼子4只。老鼠应该在笼子之间旋转,这样它们就永远不会碰到另一只老鼠两次。您多久可以这样做一次?配置是什么?

2 回复 | 直到 15 年前

1

2

Joe Neeman 15 年前

这是“社会高尔夫球手问题”的一个例子。沃里克·哈维以前有一个页面( http://www.cs.st-andrews.ac.uk/~wh/golf/ )针对不同的问题大小提供了一系列解决方案,但似乎有所下降。在你的例子中,答案是10个旋转,但我不知道实际的配置是什么。不过,这里有一个9旋转的解决方案: http://www.cs.st-andrews.ac.uk/~ianm/CSPLib//prob/prob010/solution

对于N和K将军来说,这是一个未解决的问题。

2

1

leonbloy 15 年前

您的问题语句(“所有可能的分区”)令人困惑。

让我们修正条款(如果您同意): 一个分区 ( p )是一个特殊的(和完整的)分布 N元素 在里面 X盒 ,每一个 K=4个元素 . (我使用术语“box”而不是“set”以避免混淆)(顺便说一句,注意,如果我们接受这个定义,那么您必须重申您关于“连续分区”的短语,这没有意义)。

那么,让我们打电话 P ={p1,p2 ...} 所有可能分区的集合。现在,我们对P的一些子集很感兴趣(我们可以将它们中的每一个都称为“适当的分区集”)。PSOF是一组具有给定属性的分区:没有两个分区将同一对元素映射到同一个框中。(我们还可以添加“最大化”属性:不违反规则就无法添加其他分区)。

现在还不清楚你是否想:

计算(最多)有多少个分区可以有一个这样的psof (我不清楚每个PSOF是否都有相同的基数-可能吧)
找到其中一个PSOF分区的算法。
数一数PSOF有多少。
找到所有可能的粒子群算法与每个分区。

在我看来,没有一件事是容易的。(不好意思,我知道这不是一个提问者,而是一个澄清,但不符合评论)