Finden Sie optimale Array-Schnittpunkte

Question

Ich habe ein Array von Arrays und ein passendes Array. Jedes Array hat eindeutige ID-Werte.

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

A1 = [1, 4, 6]

A2 = [2,3,5]

A3 = [1,5]

A4 = [4]

A5 = [1, 6]

Need "optimal passende" zu finden. Eine optimale Anpassung ist eine Anordnung von Teilmengen von A1-A5 mit minimaler Länge, die eine maximal mögliche Schnittmenge mit MatchingArray haben sollte.

Für dieses Beispiel gibt es 2 mögliche Zuordnungen mit einem maximalen Schnittpunkt: M1 = [[2,3,5], [1, 4, 6]] und M2 = [[1,5], [4] , [1, 6]]. Aber M1.length < M2.length, so sollte der Algorithmus M1 ausgeben.

Answer 1

Sie könnten Sets (oder Hashes, unabhängig von der Sprache sie nennt), um die Zeiteffizienz zu optimieren.

Konvertieren Sie das Zielarray in einen Satz, und subtrahieren Sie dann die ausgewählte Quelle davon (d. H. Entfernen von gemeinsamen Werten). Führen Sie das rekursiv durch, bis die Zielmenge leer ist. Behalten Sie das beste Ergebnis im Auge (möglichst wenige Quell-Arrays verwenden). Backtrack, wenn die Anzahl der verwendeten Quell-Arrays die Länge der besten Lösung überschreitet, die zu diesem Zeitpunkt bereits gefunden wurde. Hier

ist der Code in 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) 

Sehen Sie es auf repl.it laufen

In 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; }

Answer 2

implementierten Algorithmus in 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)));

1. Count Kreuzung von Arrays getrennt.
2. Rückgabe Arrays, die mehr Teile von Kreuzungen enthalten.

-Code aktualisiert