アレイ組合の最小数を見つけることは別の配列に一致

Question

所与のアレイに入れアレイの任意の数：

a = [1, 2, 4] 
b = [2, 4] 
c = [3] 
d = [1, 2] 

arrays = [a, b, c, d] 

私は配列に一致するように組合これらの配列の最小数を選択したい[1, 2, 3, 4]つまり、「正しい」答えは[a, c]で、[b, c, d]ではありません。

私の目的のために、配列の数が最も少なくても、目的の配列に一致する基準を満たすことができます。

いくつかのブルートフォースソリューション（たとえば、各要素を他の要素と結合するネストループ）を想像することができますが、この結果を得るための最適な/エレガントな方法があるかどうかは疑問です。

Answer 1

1つの配列の組み合わせから始めて、組み合わせをチェックしなければならないということは確かです（問題はNP完全です）、2つの配列の組み合わせをチェックするのが失敗した場合に。

def minimal_cover(arr, target) 
    (1..arr.size).each do |n| 
    arr.combination(n).each { |a| return a if (target - a.reduce(:|)).empty? } 
    end 
    nil 
end 

a = [1, 2, 4] 
b = [2, 4] 
c = [3] 
d = [1, 2] 
arrays = [a, b, c, d] 
target = [1, 2, 3, 4] 

minimal_cover(arrays, target) 
    #=> [[1, 2, 4], [3]]