我不知道如何寫這個問題的標題。現有的標題可能不準確。算法 - 如何有效地確保來自每個陣列的元素不同？
這裏的問題是：
我有m組（陣列），說，4組。每個組包含一些數字。我們希望每個組都給出一個數字，並且總共得出的4個數字（每組來自一個組）是不同的。
現在給了這4組，我該如何確定它們符合我們的願望？
例如，
A：0，2，3
B：0,2
C：2,3
d：1
以上4組可以符合我們的願望。 d給出1，C給出3，B給出了2，A 0給
但如果
A：2-
B：2
C：2,3
D：1
是壞的。我們不能讓每個組都給出一個明確的數字。
我的想法是最笨的辦法，我只是不走回頭路從所有組中的所有元素，以獲得元素的每個組合和看到一個組合這些元素不同與否。
任何人有更好的主意嗎？
您可以將此模型設置爲網絡流問題，然後在該問題域（其中多數爲多項式時間）中使用快速算法，如Edmunds-Karp或push-relabel。
創建源節點和宿節點。然後爲每個「組」和每個不同的元素創建節點。將每個組節點連接到源，並將每個元素節點連接到接收器。最後，如果組作爲元素，則將組節點與元素節點連接起來。所有流量應爲1.
這是最好的例子。我會用你給第一個例子：
A: 0, 2, 3
B: 0, 2
C: 2, 3
D: 1
會變成下面的流程網絡：
A 0
/ \
/ \
S--B 1--T
\ /|
\ /|
C 2/
/
3
我不能得出中間流。但是，假設A流向0,2,3，並且B流向0,2，並且C流向2,3和D.流向1.所有流都是單位容量。
所以首先找到這個圖中的最大流量。組和元素之間的流程將爲您提供所需的二分配匹配。
如果沒有可能的匹配，那麼最大流量將小於組數。
你想要什麼叫http://en.wikipedia.org/wiki/Bipartite_graph，你有一個適用於http://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching。您可以在此名稱下找到算法：雙基圖上的最大基數二分配匹配或最大流量。這裏很好解釋http://en.wikipedia.org/wiki/Maximum_matching和http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow,http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2 希望有所幫助。
一個想法是查找所有組都獨有的元素，並將它們用於它們所屬的組;這將把列表縮小到只有具有共同元素的組。
另一個想法是從具有最少元素（理想情況下爲1）的組開始，將它們設置爲其中一個值並迭代增加大小（可以在刪除已使用的元素之後考慮大小）。