我有幾套，比如說5套
{1,2,3}
{2,4}
{1,2}
{4,5}
{2,3,5}
在這里，我需要從任意三組中選擇至少 3 個元素（每組一個元素）。假設如果一個元素已經被選中，那么它就不能再次被選中。
還要檢查是否存在任何解決方案。
例如
設定{1,2,3} -> 選擇1
設定{2,4}->選擇2
set {1,2}-> 不能選擇，因為兩者1都2被選中。
設定{2,5}-> 只能選擇 5
有沒有辦法做到這一點？簡單的解釋將不勝感激。
uj5u.com熱心網友回復：
如果你只需要 3 個元素，那么演算法非常簡單。只需重復以下程序：
- 選擇具有最低啟發式的集合。啟發式是集合的長度除以該集合的總出現次數。如果集合有零個元素，則洗掉集合，然后轉到步驟 4。如果有兩個或更多，您可以選擇其中任何一個。
- 從該集合中選擇一個元素。這是您將選擇的元素。
- 從每個集合中洗掉此元素。
- 如果您選擇了 3 個元素或沒有更多的集合，請退出。否則轉到步驟 1。
該演算法盡可能提供至少 3 個元素，即使存在重復項也是如此。這是證據。
- 如果一個集合的啟發式是
<= 1，那么從該集合中選擇一個元素基本上是免費的。它根本不會損害使用其他套裝的能力。 - 如果我們處于具有 2 組或更多組的情況下
>1，我們必須選擇至少兩個元素，這很容易。只需從第一個中選擇一個，第二個就會留下一個元素，因為它的長度是>1因為它是啟發式的>1。 - 如果我們遇到 3 組或更多組帶有 heuristic 的情況
>1，我們可以從第一組中選擇。在此之后，我們至少剩下兩個集合，其中至少一個具有多個元素。我們不能留下兩個大小為一的集合，因為這意味著我們開始的 3 個集合包含重復的長度為 2 的集合，它具有啟發式 1。因此我們可以選擇所有 3 個元素。
這是該演算法的python代碼。生成器回傳盡可能多的元素。如果有可能回傳至少 3 個元素，它會。但是在那之后，它并不總是回傳最佳解決方案。
def choose(sets):
# Copy the input, to avoid modification of the input
s = [{*e} for e in sets]
while True:
# If there are no more sets remaining
if not s:return
# Remove based on length and number of duplicates
m = min(s,key=lambda x:(len(x)/s.count(x)))
s.remove(m)
# Ignore empty sets
if m:
# Remove a random element
e = m.pop()
# Yield it
yield e
# Remove the chosen element e from other sets
for i in range(len(s)):s[i].discard(e)
print([*choose([{1,2,3}, {2,4}, {1,2}, {4,5}, {2,3,5}])])
print([*choose([{1}, {2,3}, {2,4}, {1,2,4}])])
print([*choose([{1,2}, {2}, {2,3,4}])])
print([*choose([{1,2}, {2}, {2,1}])])
print([*choose([{1,2}, {1,3}, {1,3}])])
print([*choose([{1}, {1,2,3}, {1,2,3}])])
print([*choose([{1,3}, {2,3,4}, {2,3,4}, {2,3,4}, {2,3,4}])])
print([*choose([{1,5}, {2,3}, {1,3}, {1,2,3}])])
在線嘗試！
uj5u.com熱心網友回復：
像這樣的東西
given your sets
0: {1,2,3}
1: {2,4}
2: {1,2}
3: {4,5}
4: {2,3,5}
A array of sets
set A[1] = { 0, 2} // all sets containing 1
A[2] = { 0, 1, 2, 4} // all sets containing 2
A[3] = { 0, 4 } // all sets containing 3
A[4] = { 1, 3 } // all sets containing 4
A[5] = { 3, 4 } // all sets containing 5
set<int> result;
for(i = 0; i < 3; i ) {
find k such that A[k] not empty
if no k exist then "no solution"
result.add(k)
A[k] = empty
}
return result
uj5u.com熱心網友回復：
我認為我的想法有點矯枉過正，但它適用于任何型別、任何數量、任何大小的集合。
這個想法是將集合轉換為二分圖。一方面你有每個集合，另一方面你有它們包含的數字。如果一個集合包含一個數字，那么這些頂點之間就有一條邊。
最終你試圖在圖中找到最大匹配（最大基數匹配）。很高興它可以在 O(√VE) 時間內使用 Hopcroft-Karp 演算法完成，或者使用 Ford-Fulkerson 演算法甚至更少。
這里有一些關于最大匹配和演算法的更多來源的鏈接->
https://en.wikipedia.org/wiki/Matching_(graph_theory)
https://en.wikipedia.org/wiki/Maximum_cardinality_matching
https://en.wikipedia.org/wiki/Ford–Fulkerson_algorithm
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/420351.html
標籤：
下一篇：嵌入式系統，如何定義或計算時間段