ruby - 搜索二维数组的算法

Question

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 

用蛮力方式完成它会花费太多时间。还有其他建议吗？

Answer 1

这里有一些东西可以做到这一点:

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

计算不需要很长时间，如果您准备使用 Benchmark 进行测试，可能有更好的方法来优化内部循环。

如果您需要数量级更好的性能，也许是 C++ 库 linked in via FFI就是答案。

如果您正在处理相对较小的数字，例如在 0..31 甚至 0..63 范围内，那么您可以使用位掩码来实现。这会将每个数组减少为单个值，并且将值与 OR 组合在计算方面是微不足道的。计算给定值中的位数同样非常简单。