搜索二维数组的算法

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

搜索二维数组的算法

回答

相关问题