查找最佳陣列交點

我有一個數組和一個匹配數組的數組。每個數組都有唯一的id值。查找最佳陣列交點

MatchingArray = [1,2,3,4,5,6]

A1 = [1，4,6]

A2 = [2,3,5]

A3 = [1,5]

A4 = [4]

A5 = [1,6]

需要找到「最佳匹配數」。最佳匹配是來自A1-A5的具有最小長度的子集陣列，其應與匹配陣列具有最大可能的交集。對於這個例子，有兩個可能的匹配與最大交集：M1 = [[2,3,5]，[1,4,6]]和M2 = [[1,5]，[4] ，[1,6]]。但M1.length < M2.length，所以算法應輸出M1。

來源

2017-04-15 VahagnNikoghosian

如果需要更多的描述，請留下評論根據回答 –

也許問題描述不好，但算法的全部含義是找到M1。我定義了M1和M2來解釋最優解，並不是因爲它們在算法中是已知的。 – VahagnNikoghosian

你需要找到更多的'A1-A5'與'MatchingArray'相交的數組？ –

你可以使用集（或哈希值，無論語言稱他們），以優化的時間效率。

將目標數組轉換爲一個集合，然後從中減去所選的源（即刪除公共值）。繼續遞歸直到目標集合爲空。跟蹤最佳結果（儘可能使用最少的源數組）。如果正在使用的源數組的數量超過了當時已經找到的最佳解決方案的長度，則返回。

這裏是在Python代碼：

def find_optimal_coverage(target, sources): 
    max_size = len(target) 
    best = None 

    def recurse(target, sources, selected): 
     nonlocal max_size, best 
     if len(target) == 0: 
      best = selected 
      max_size = len(best) - 1 
      return True 
     if len(selected) == max_size: 
      return None 
     for i, source in enumerate(sources): 
      result = recurse(target - set(source), sources[i+1:], 
          selected + [list(source)]) 
      if result: 
       return True 

    target = set(target) # convert to set for faster lookup 
    # limit the source lists to elements that occur in the target 
    sources = list(map(target.intersection, sources)) 
    # limit target to elements that occur in at least one source 
    target = set.union(*sources) 
    # sort sources by decreasing length to maximise probability of 
    # finding optimal solution sooner 
    sources.sort(key = len, reverse = True) 
    if recurse(target, sources, []): 
     return best 

result = find_optimal_coverage(
    [1, 2, 3, 4, 5, 6, 8], 
    [ 
     [1, 4, 6, 7], 
     [2, 3, 5], 
     [1, 5], 
     [4], 
     [1, 6] 
    ] 
) 
print(result)

看到它在repl.it

運行在JavaScript：

function subtractArray(s, arr) { 
 
    return arr.reduce((s, v) => (s.delete(v), s), new Set(s)); 
 
} 
 

 
function findOptimalCoverage(target, sources) { 
 
    var maxSize = target.size; 
 
    var best = null; 
 
    
 
    function recurse(target, sources, selected) { 
 
     if (target.size == 0) { 
 
      best = selected; 
 
      maxSize = best.length - 1; 
 
      return true; 
 
     } 
 
     if (selected.length == maxSize) return; 
 
     return sources.some((source, i) => 
 
      recurse(subtractArray(target, source), sources.slice(i+1), 
 
        selected.concat([source])) 
 
     ); 
 
    } 
 
    target = new Set(target) // convert to set for faster lookup 
 
    // limit the source arrays to elements that occur in the target 
 
    sources = sources.map(source => source.filter(target.has.bind(target))); 
 
    // limit target to elements that occur in at least one source 
 
    target = new Set([].concat(...sources)); 
 
    // sort sources by decreasing length to maximise probability of 
 
    // finding optimal solution sooner 
 
    sources.sort((a,b) => b.length - a.length); 
 
    if (recurse(target, sources, [])) return best; 
 
} 
 

 
var result = findOptimalCoverage(
 
    [1, 2, 3, 4, 5, 6, 8], 
 
    [ 
 
     [1, 4, 6, 7], 
 
     [2, 3, 5], 
 
     [1, 5], 
 
     [4], 
 
     [1, 6] 
 
    ] 
 
); 
 
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

來源

2017-04-15 20:32:26 trincot

好的答案，經過一些調整後，這個算法給了我真正想要的。謝謝。 – VahagnNikoghosian

@VahagnNikoghosian這個algrorithm在數組中不能正常工作，它包含非交集元素並且具有相同數量的intesection元素，是嗎？例如，如果你嘗試測試數組''[1,4,6,7]'' –

實施的算法在javascript：陣列的單獨

var matchingArray = [1, 2, 3, 4, 5, 6]; 
 

 
var A1 = [1, 4, 6], 
 
    A2 = [2, 3, 5], 
 
    A3 = [1, 5], 
 
    A4 = [4], 
 
    A5 = [1, 6]; 
 

 

 
var M = [A1, A2, A3, A4, A5]; 
 

 
function compareArrays(M, machingArray) { 
 
    var intersections = [] 
 
    M.forEach(function(A) { 
 
    var partOfItersections; 
 
    if (A.length > 0) { 
 
     var intersectionsCount = getIntersectionCount(A, machingArray); 
 
     partOfItersections = intersectionsCount/A.length; 
 
    } else { 
 
     partOfItersections = 0 
 
    } 
 

 
    intersections.push({ 
 
     length: A.length, 
 
     partOfItersections: partOfItersections 
 
    }); 
 
    }); 
 

 

 
    //alert(JSON.stringify(intersections)); 
 

 
    var maxLength = 0, 
 
    maxPartOfItersections = 0, 
 
    optimalArrays = []; 
 

 
    intersections.forEach(function(arrayData, index) { 
 
    var currentArr = M[index]; 
 
    var currentArrLength = currentArr.length; 
 
    if (maxPartOfItersections < arrayData.partOfItersections) { 
 

 
     setCurrentOptimalArr(arrayData.partOfItersections, currentArr); 
 
    } else if (maxPartOfItersections === arrayData.partOfItersections) { 
 
     if (maxLength < currentArrLength) { 
 
     setCurrentOptimalArr(arrayData.partOfItersections, currentArr); 
 
     } else if (maxLength === currentArrLength) { 
 
     optimalArrays.push(currentArr); 
 
     } 
 
    } 
 
    }); 
 

 
    //alert(JSON.stringify(optimalArrays)); 
 

 
    return optimalArrays; 
 

 
    function setCurrentOptimalArr(intersectionsCount, currentArr) { 
 
    optimalArrays = [currentArr]; 
 
    maxLength = currentArr.length; 
 
    maxPartOfItersections = intersectionsCount; 
 
    } 
 

 
    function getIntersectionCount(A, machingArray) { 
 
    var intersectionCount = 0; 
 

 
    A.forEach(function(elem) { 
 
     if (machingArray.indexOf(elem) != -1) { 
 
     intersectionCount++; 
 
     } 
 
    }); 
 

 

 
    return intersectionCount; 
 
    } 
 
} 
 

 
alert(JSON.stringify(compareArrays(M, matchingArray)));

計數交集。
包含更多部分交點的返回數組。

代碼更新

來源

2017-04-15 17:21:56

嘗試使用拼寫檢查器。 – greybeard

對不起我'分開'。我忘記它是如何正確寫入的。您可以編輯它並修復。 –

查找最佳陣列交點

回答

相關問題