查找具有 k 大小子集的 n 个元素的所有可能分区，其中两个元素仅共享同一个集合一次
我有 n 个元素需要分成 x 个集合，每个集合必须恰好包含 k=4 个元素。
我需要找到所有可能的分区，并限制每对元素仅共享同一组一次。
因此，如果我从 [1 2 3 4] [5 6 7 8] [...] 开始，所有连续分区都不能容纳例如 [1 2 XX] 或 [XX 1 3]。集合是无序的。
接近这个问题的是第二类斯特林数。然而，它们只能解决任意大小的集合的问题。
示例：我有 32 只老鼠，可以放入 8 个笼子中，每个笼子 4 只。小鼠应在笼子之间轮换，以免它们两次遇到另一只小鼠。您多久可以执行一次此操作以及配置是什么？
I have n elements that need to be partitioned into x sets, each set has to hold exactly k=4 elements.
I need to find all possible partitions with the constraint that each pair of elements only shares the same set once.
So if I start with [1 2 3 4] [5 6 7 8] [...], all consecutive partitions cannot hold e.g. [1 2 X X] or [X X 1 3]. sets are unordered.
Close to this problem are the stirling numbers of the second kind. However, they only solve the problem for arbitrarily sized sets.
Example: I have 32 mice that can be put in 8 cages, 4 per cage. The mice should be rotated between the cages in a fashion that they never meet another mouse twice. How often can you do this and what are the configurations?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是“社交高尔夫球手问题”的一个例子。 Warwick Harvey 曾经有一个页面 (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 来说这是一个未解决的问题。
This is an instance of the "social golfer problem." Warwick Harvey used to have a page (http://www.cs.st-andrews.ac.uk/~wh/golf/) with a bunch of solutions for different problem sizes, but it seems to be down. The answer in your case turns out to be 10 rotations, but I don't know what the actual configurations are. Here is a 9-rotation solution, though: http://www.cs.st-andrews.ac.uk/~ianm/CSPLib//prob/prob010/solution
It is an unsolved problem for general n and k.
您的问题陈述（“所有可能的分区”）令人困惑。
让我们修正一下术语（如果您同意）：分区 (
p) 是 n 个元素 中的特定（且完整）分布strong>x 个盒子，每个盒子有 k=4 个元素。 （我使用术语“盒子”而不是“集合”以避免混淆）（顺便说一句，请注意，如果我们接受这个定义，那么您必须重申有关“连续分区”的短语，它没有意义）。然后，我们将 P ={p1,p2 ...} 称为所有可能分区的集合。现在，我们对 P 的一些子集感兴趣（我们可以将它们中的每一个称为“适当的分区集”）。 PSOF 是一组具有给定属性的分区：不存在将同一对元素映射到同一个框的两个分区。 （我们还可以添加最大属性：在不违反规则的情况下不可能添加另一个分区）。
现在，尚不清楚您是否想要：
（我不清楚是否每个 PSOF 都具有相同的基数 - 可能）
对我来说，没有一个是容易的。 （抱歉，我知道这不是回答而是澄清，但它不适合评论）
Your problem statement ("all possible partitions") is confusing.
Let's fix the terms (if you agree) : a partition (
p) is a particular (and complete) distribution of the n elements in x boxes, each with k=4 elements. (I use the term 'box' instead of 'set' to avoid confusion) (BTW, notice that, if we accept this definition, then you must restate your phrase about "consecutive partitions", it does not make sense).Then, let´s call
P ={p1,p2 ...}the set of all possible partitions. Now, we are interested in some subsets of P (we might call each of them a "proper set of partitions"). A PSOF is a set of partitions that has the given property: there are no two partitions that map the same pair of elements to the same box. (We can also add the property of being maximal: it's not possible to add another partition without violating the rule).Now, it's not clear if you want to:
(it's not clear for me if every PSOF has the same cardinality - probably)
None seems easy to me. (Sorry, I know this is not an aswer but a clarification, but it didnt fit in the comments)