1

我有 n 个元素需要分成 x 个集合，每个集合必须恰好包含 k=4 个元素。

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

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

接近这个问题的是第二类斯特林数。但是，它们只解决了任意大小的集合的问题。

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

4

2 回答 2

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，这是一个未解决的问题。

于 2010-09-13T19:04:37.747 回答
1

您的问题陈述（“所有可能的分区”）令人困惑。

让我们修正一下条款（如果您同意的话）：分区( ) 是x 个盒子中的n 个元素的p特定（且完整）分布，每个盒子有k=4 个元素。（我使用术语 'box' 而不是 'set' 以避免混淆）（顺便说一句，请注意，如果我们接受这个定义，那么你必须重申你关于“连续分区”的短语，它没有意义）。

然后，让我们调用P ={p1,p2 ...}所有可能分区的集合。现在，我们对 P 的一些子集感兴趣（我们可以称它们中的每一个为“适当的分区集”）。PSOF 是一组具有给定属性的分区：没有两个分区将同一对元素映射到同一个框。（我们还可以添加最大的属性：不可能在不违反规则的情况下添加另一个分区）。

现在，尚不清楚您是否要：

  • 计算（最多）多少个分区可以拥有其中一个 PSOF（我不清楚每个 PSOF 是否具有相同的基数 - 可能）
  • 一种用于查找其中一个 PSOF 的分区的算法。
  • 计算有多少 PSOF。
  • 一种使用每个分区查找所有可能的 PSOF 的算法。

对我来说，没有一个是容易的。（对不起，我知道这不是一个回答，而是一个澄清，但它不适合评论）

于 2010-07-04T23:51:26.043 回答