Алгоритм поиска 2d-массива

Question

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

Учитывая приведенный выше массив 2d, мне нужно выбрать пять массивов, которые дают мне самый уникальный номер.

Например

# 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 

Doing это грубая сила способ принимает слишком много времени, чтобы закончить. Есть ли другие предложения?

Answer 1

А вот алгоритм 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] 

Answer 2

Вот то, что делает это:

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 тривиально с точки зрения вычисления. Подсчет количества бит в заданном значении также довольно прост.

Answer 3

Вы можете уменьшить время вычисления, уменьшив массив data.

Первоначально, 462 комбинации:

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

Удаление пустых массивов уменьшает это до 56:

data.reject!(&:empty) 

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

и удаление массивов, которые полностью содержащиеся в других результатах массивов в лишь 6 комбинаций:

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

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