獲取有限集合的有限族的隨機橫向

我正在尋找一種算法，它將有限數量的集合S_1，...，S_n作爲輸入並輸出列表x_1，...，x_n，其中x_i屬於S_i，對於i = 1，...，n和所有x_i是成對的不同的。請注意，集合S_i一般不會成對分離。我們可以將這樣的名單稱爲家庭的橫向{S_1，...，S_n}，正如通常所做的那樣。獲取有限集合的有限族的隨機橫向

應該以這樣的方式隨機選擇列表，即每個可能的列表作爲輸出同樣可能。我不在乎發生了什麼，沒有這樣的列表存在。我希望算法相當快，特別是在使選擇被認爲太慢之前列舉所有列表。

來源

2015-11-17 witzar

n有多大？有多少種不同的元素？大致等分可行嗎？ –

在我看來，這個問題太廣泛了。此外，它可能是脫離主題，而屬於[計算機科學]（https://cs.stackexchange.com/）。 – Hexaholic

在實際應用中我記住：n <10，每個S_n可以有多達幾百個元素。 – witzar

將集合和元素的發生率表示爲二部圖，並找到maximum cardinality bipartite matching。

來源

2015-11-18 09:19:26 Ante

是的，搜索一組集合的橫向等價於搜索二分圖的最大匹配。而找到一些最大基數匹配的問題是衆所周知的。但我不想要一些。 – witzar

在算法選擇DFS中的下一個頂點的步驟中，可以對輸入（元素和/或集合）進行置換，甚至可以進行混洗。 – Ante

正如Ante所觀察到的，我們正在尋找二分配匹配，但這裏最難的部分是找到一個隨機匹配。如果你的圖表足夠大，那麼你可能不得不解決Jerrum和Sinclair快速混合的馬爾可夫鏈。否則，有一個O（2^n poly（n））時間動態程序用於計算最大匹配（與用於枚舉它們的O（n！） - 時間算法相反），您可以通過重複計數在使用邊緣或不匹配之後匹配的數量。

來源

2015-11-18 11:46:22

這看起來很有趣。所以我需要爲我的家族集合（或二分圖）構造一些馬爾可夫鏈。然後每個（足夠長的）隨機遊走將指向我一些解決方案，並且概率將表現出來。但如何構建連鎖？你也可以給我一些關於你所提到的理論的有用鏈接嗎？ – witzar

動態規劃方法看起來也很有希望，因爲在我的特定應用中n很小。 – witzar

@witzar其實，只需要獨立一致地隨機選擇代表就足夠了，如果發生碰撞就從頭開始重試。 –

獲取有限集合的有限族的隨機橫向

回答

相關問題