集覆蓋：找到一組重疊的目標數組的元素陣列

Question

比方說，我有一個數組，A（可排序的，如果這能幫助）

我有一組陣列，B，C，D ，等...（全部可排序），所有這些可以部分或完全重疊數組A。

我想找到最小的一組數組B,C,D等......它們完全重疊在數組A上。返回第一個匹配。

例如，

const A = [1, 2, 3, 4, 'a', 'b', 'c']; 

const B = [1, 3, 4, 5, 10]; 
const C = [1, 3, 5, 'a', 'b'] 
const D = [2, 4, 'a', 'b', 'c']; 
const E = [1, 2, 'b', 'c'] 

findSmallestSet(A, [B, C, D, E]); 
// => [B, D] 

旁白：我原來的問題是找到節點樹是完全重疊的目標節點樹，但我認爲上面所提出的問題可能是一個簡單的解決方案。

Answer 1

你可以做這樣的事情，首先創建排序功能，將排序基於匹配的元素數第二個參數，所以你可以從那裏開始，那麼你每次循環的內部數組，如果它發現它在從第一個參數中刪除元素當前數組，如果在第一個數組中有左元素，則重新排序鍵並使用遞歸重複該過程。

const A = [1, 2, 3, 4, 'a', 'b', 'c']; 
 

 
const B = [1, 3, 4, 5, 10]; 
 
const C = [1, 3, 5, 'a', 'b'] 
 
const D = [2, 4, 'a', 'b', 'c']; 
 
const E = [1, 2, 'b', 'c'] 
 

 
function findSmallestSet(one, [B, C, D, E]) { 
 
    let obj = {B, C, D, E} 
 
    let keys = Object.keys(obj); 
 
    let getL = (e) => obj[e].filter(e => one.includes(e)).length 
 
    let sortK = (keys) => keys.sort((a, b) => getL(b) - getL(a)) 
 
    sortK(keys) 
 
    var r = [] 
 

 
    let find = (one, k) => { 
 
    obj[k[0]].forEach(function(a) { 
 
     var index = one.indexOf(a); 
 
     if (index != -1) one.splice(index, 1) 
 
    }) 
 
    
 
    r.push(k[0]) 
 

 
    if (one.length) { 
 
     k.shift() 
 
     sortK(k) 
 
     find(one, k) 
 
    } 
 
    } 
 

 
    find(one, keys) 
 
    return r; 
 
} 
 

 
console.log(findSmallestSet(A, [B, C, D, E]));

Answer 2

這被稱爲 '集合覆蓋' 的問題。這是NP完整的，並深入研究。 「正確答案」取決於輸入的大小以及您是否可以接受近似值。