找到n個元素的所有可能的分區與k大小的子集，其中兩個元素只共享相同的集合一次

我有n個元素需要分成x個集合，每個集合必須完全保存k = 4個元素。找到n個元素的所有可能的分區與k大小的子集，其中兩個元素只共享相同的集合一次

我需要找到所有可能的分區，約束條件是每對元素只共享一次相同的集合。因此，如果我從[1 2 3 4] [5 6 7 8] [...]開始，則所有連續的分區都不能容納例如[1 2 X X]或[X X 1 3]。套是無序的。

接近這個問題的是stirling numbers of the second kind。但是，他們只能解決任意大小的問題。

例如：我有32只老鼠，可以放在8個籠子裏，每籠4只。老鼠應該在籠子之間旋轉，以便他們再也不會遇到另一隻老鼠兩次。你多久可以做到這一點，配置是什麼？

2010-06-18 ypnos

這是「社交高爾夫球員問題」的一個實例。華威哈維曾經有一個頁面（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-13 19:04:37

非常感謝。我找到了這個資源：http：//www.cs.brown.edu/~sello/golf.html，它引用了Harvey的頁面鏡像：http://www.csplib.org/prob/prob010/index.html還有其他許多人。 – ypnos 2010-09-14 11:55:46

你的問題陳述（「所有可能的分區」）令人困惑。

讓我們來解決的術語（如果同意）：分區（p）是n個元素在X框的特定（和完整）的分佈，每個具有K = 4組的元素。（我使用'box'而不是'set'來避免混淆）（順便說一句，請注意，如果我們接受這個定義，那麼你必須重申關於「連續分區」的短語，這是沒有意義的）。

然後，讓我們打電話P ={p1,p2 ...}所有可能的分區的集合。現在，我們對P的一些子集感興趣（我們可能會稱它們爲「合適的分區集合」）。 PSOF是一組具有給定屬性的分區：沒有兩個分區將同一對元素映射到同一個盒子。（我們也可以添加最大的屬性：在不違反規則的情況下添加另一個分區是不可能的）。現在

，如果你想它不是明確：

算多少分區（最多）可以有那些PSOF 之一（目前尚不清楚對我來說，如果每PSOF具有相同的基數 - 可能）
找到其中一個PSOF分區的算法。
計算PSOF的數量。
找到所有可能的PSOF與每個分區的算法的算法。

對我來說這似乎不容易。（對不起，我知道這不是一個意思，而是一個澄清，但它不適合評論）

來源

2010-07-04 23:51:26 leonbloy

非常感謝您的澄清。它非常清楚地總結了問題陳述。我想找到的是最大的最大PSOF（如你所說可能它們都具有相同的尺寸）。 – ypnos 2010-07-05 12:05:22

另一個解釋：箱子的順序是否重要？我認爲它沒有。即如果兩個分區僅在box1與box2交換時有所不同，則認爲它們是相同的。對？ – leonbloy 2010-07-05 14:38:17

找到n個元素的所有可能的分區與k大小的子集，其中兩個元素只共享相同的集合一次

回答

相關問題