搜索二維數組的算法

data = [[0,1], [1,6,10], [], [1,2,4,5], [7,8], [], [], [8], [2], [0,3], [9]]

給定上面的二維數組，我需要選擇五個數組，給我最獨特的數字。搜索二維數組的算法

例如

# returns 11 (optimal output, the number of subclasses) 
(data[1] | data[3] | data[4] | data[9] | data[10]).length 
# returns 10 (less optimal output) 
(data[0] | data[1] | data[3] | data[4] | data[10]).length

做它蠻力方式正在採取太多的時間來完成。還有其他建議嗎？

來源

2017-01-23 root

能不能請你解釋清楚 – 2017-01-23 15:39:15

「最獨特」是指「最少重複」嗎？這是一個排列問題，所以它不會非常高效。在一般情況下，沒有算法可以神奇地解決這個問題。 – tadman

這是一個greedy算法。

對於每次迭代，它只需要具有最新元素的子陣列。它適用於您的示例，但可能會因爲更復雜的示例而被少數元素忽略。

對於大型陣列和大型n，它應該比使用combination的任何解決方案快得多。

你沒有提供任何代碼，所以我會留下它作爲練習來尋找反例;）。

data = [[0, 1], [1, 6, 10], [], [1, 2, 4, 5], [7, 8], [], [], [8], [2], [0, 3], [9]] 

def trim(array, already_taken) 
    array.map { |sub_array| sub_array - already_taken }.reject(&:empty?) 
end 

def find_best_cover(array, n) 
    array = array.map{ |subarray| subarray.uniq } 
    Array.new(n) do 
    next_best = array.max_by { |subarray| subarray.size } 
    array = trim(array, next_best) 
    next_best 
    end 
end 

p find_best_cover(data, 5).flatten 
#=> [1, 2, 4, 5, 6, 10, 7, 8, 0, 3, 9]

來源

2017-01-23 18:29:02

這裏的東西做它：

data = [[0,1], [1,6,10], [], [1,2,4,5], [7,8], [], [], [8], [2], [0,3], [9]] 

best = data.combination(5).max_by do |combo| 
    combo.flatten.uniq.length 
end 

best 
# => [[1, 6, 10], [1, 2, 4, 5], [7, 8], [0, 3], [9]] 
best.flatten.uniq.length 
# => 11

它並不需要很長時間來計算，大概還有，如果你準備用基準測試優化該內環的更好的方法。

如果您需要更高的性能數量級，也許C++庫linked in via FFI是答案。

如果您處理的數字相對較小，例如在0..31或甚至0..63的範圍內，那麼您可以使用位掩碼來完成此操作。這會將每個數組減少到一個單一的值，並且在計算方面將值與OR組合使用是微不足道的。計算給定值中的位數同樣非常簡單。

來源

2017-01-23 16:06:37 tadman

結果中有12個數字，但只有11個_unique_數字（1次出現兩次）。 – Stefan

順便說一句，我認爲你（只）需要'組合'，而不是'排列'。 – Stefan

@Stefan偉大的一點，它的運行速度很快。我也沒有注意到重複，所以這也解決了。 – tadman

您可以通過減少data陣列來減少計算時間。

最初，有462個的組合：

data.combination(5).size 
#=> 462

刪除空陣列減小了這種至56：被完全包含在其他陣列結果僅僅6個組合

data.reject!(&:empty) 

data.combination(5).size 
#=> 56

和刪除數組：

data -= [[2], [8]] 

data.combination(5).size 
#=> 6

來源

2017-01-23 16:39:07 Stefan

搜索二維數組的算法

回答

相關問題