是否存在任何已知算法如何有效地產生具有附加限制的任意隨機多重排列。有限制的隨機多重排列的產生
實施例: 我有項的多集,例如:{1,1,1,2,2,3,3,3}
,和限制集合的集合,例如{{3}
,{1,2}
,{1,2,3}
,{1,2,3}
,{1,2,3}
,{1,2,3}
,{2,3}
,{2,3}
}。我在尋找項目的排列,但第一個元素必須是3,第二個必須是1或2,等
一個這樣的排列,適合限制是:
是否存在任何已知算法如何有效地產生具有附加限制的任意隨機多重排列。有限制的隨機多重排列的產生
實施例: 我有項的多集,例如:{1,1,1,2,2,3,3,3}
,和限制集合的集合,例如{{3}
,{1,2}
,{1,2,3}
,{1,2,3}
,{1,2,3}
,{1,2,3}
,{2,3}
,{2,3}
}。我在尋找項目的排列,但第一個元素必須是3,第二個必須是1或2,等
一個這樣的排列,適合限制是:
是的,有。我在this German forum詢問並得到以下答案:問題可以簡化爲找到a maximum matching on a bipartite graph。 爲了做到這一點,介紹multiset中所有元素的頂點。這些頂點形成了二分圖的一側。然後,爲每個限制集引入頂點。這些頂點構成了二分圖的另一側。現在,將每個限制集中的邊緣引入到第一側上的頂點,使得當且僅當它表示包含在連接集中的元素時,第一側上的頂點纔是「命中」。
您例如二分圖是這樣的:
現在匹配的是兩個相鄰的邊緣選擇的方式選擇邊緣。例如。爲第二個限制「{1,2}」選擇第一個「1」,那麼它就不能再用於任何其他限制,因爲從這個頂點使用另一個邊將不會再導致匹配。
如果您對此有其他疑問,請隨時提問。