Wie werden die Elemente eines Arrays zufällig denen eines anderen Arrays zugeordnet, wenn bestimmte Objekte nicht miteinander verknüpft werden sollen?

Question

Ich erstelle ein Spiel, in dem Spieler Objekte auf dem Bildschirm an den richtigen Zielorten sortieren müssen. Ich suche nach einer Möglichkeit, die Objekte so zu mischen, dass kein Objekt an einem korrekten Ort beginnt. Wir werden also nicht in eine verrückte Welt von doppelten Negativen verfallen, ich werde die Orte mit der "richtigen Antwort" "vermeiden" und die Orte mit der "falschen Antwort" "gültige" Orte für diese Art nennen.

Die Arrays könnte wie folgt aussehen:

var sort_items = [ 
    {"avoid": ["target1", "target2"]}, 
    {"avoid": ["target1", "target2"]}, 
    {"avoid": ["target3"]}, 
    {"avoid": ["target4", "target5"]}, 
    {"avoid": ["target4", "target5"]}, 
]; 

var sort_locations = [ 
    {"id": "target1"}, 
    {"id": "target2"}, 
    {"id": "target3"}, 
    {"id": "target4"}, 
    {"id": "target5"}, 
]; 

So zum Beispiel werden die ersten und zweiten Objekte in sort_items auf target3, target4 platziert könnte, oder , aber nicht target1 oder target2.

Ich habe eine Reihe von verschiedenen Methoden ausprobiert, aber alle haben das Problem, dass am Ende der Sortierung die verbleibenden Positionen für die verbleibenden sort_items häufig ungültig sind. Zum Beispiel:

sort_items[0] placed on target3, 
sort_items[1] placed on target5, 
sort_items[2] placed on target2, 
sort_items[3] placed on target1, 
Error: sort_items[4] cannot be placed on target4 

Auch in diesem Beispiel einer anderen zufällig Kommissionierung und Austausch mit ihm wie eine schlechten Idee scheint, weil die Hälfte des andere wäre auch ein ungültiges Spiel auf einem Swap führen.

Gibt es eine gute Methode, um dies zu tun?

Answer 1

Wenn Sie garantieren wollen, dass jeder Gegenstand gleiche Wahrscheinlichkeiten hat, um an einer der Position zu landen, die er besetzen darf, ohne irgendwelche Voreingenommenheit durch die Gegenstände, die davor verarbeitet wurden, bin ich geneigt zu denken, dass die Der einfachste Weg ist, mit einer völlig zufälligen Liste zu beginnen.

Dann können Sie durch die Liste gehen und versuchen, jedes ungültige Element mit dem ersten gültigen Element zu tauschen, auf das Sie stoßen. genau

Mehr unterhalb der Algorithmus ist es auf diese Weise tun:

// initial random list 
["target1", "target5", "target2", "target4", "target3"] 
// 1st position is invalid -> swap "target1" and "target5" 
["target5", "target1", "target2", "target4", "target3"] 
// 2nd position is invalid -> swap "target1" and "target2" 
["target5", "target2", "target1", "target4", "target3"] 
// 2nd position is still invalid -> swap "target2" and "target4" 
["target5", "target4", "target1", "target2", "target3"] 
// -> valid list 

Diese jedes Mal nicht gelingen wird. Und wenn das fehlschlägt, müssen Sie von vorne anfangen.

Dies ist jedoch fairer als zu versuchen, die Slots nacheinander in einer bestimmten Reihenfolge zu füllen, und effizienter als einfach die Liste zu mischen, bis wir eine gültige erhalten. (In, dass wir zu 'reparieren' es versuchen, bevor es ablehnen.)

var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]} 
 
]; 
 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"} 
 
]; 
 

 
var list = sort_locations.map(function(i) { return i.id; }); 
 

 
while(!list.every(function(item, i) { 
 
    for(var j = i + 1; sort_items[i].avoid.indexOf(item) != -1; j++) { 
 
    if(j == list.length) { 
 
     return false; 
 
    } 
 
    item = list[j]; 
 
    list[j] = list[i]; 
 
    list[i] = item; 
 
    } 
 
    return true; 
 
})) { 
 
    list.sort(function() { return Math.random() < 0.5 ? -1 : 1; }); 
 
} 
 
console.log(list);

EDIT

habe ich ein paar weitere Tests, die darauf hindeuten, dass es noch mehr voreingenommen ist als ich erwartet es zu sein.

Für was es wert ist, hier ist eine einfachere, 100% Trial-and-Error-Version. Dieser ist garantiert unvoreingenommen.

var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]} 
 
]; 
 

 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"} 
 
]; 
 

 
var list = sort_locations.map(function(i) { return i.id; }); 
 

 
while(!list.every(function(item, i) { 
 
    return sort_items[i].avoid.indexOf(item) == -1; 
 
})) { 
 
    list.sort(function() { return Math.random() < 0.5 ? -1 : 1; }); 
 
} 
 
console.log(list);

Answer 2

Hier ist eine Lösung, die alle möglichen Lösungen durch Rekursion erzeugt, und nimmt dann ein gelegentliches.Im Vergleich zu zufälligen Trial-and-Error-Lösungen kann dies zu schnelleren Ergebnissen führen, wenn die Anzahl der Lösungen im Vergleich zur Größe der Eingabe begrenzt ist.

Zweitens garantiert dies, dass jede Lösung die gleiche Wahrscheinlichkeit hat, ausgewählt zu werden.

Beachten Sie, dass das Skript ES6-Unterstützung erfordert.

function findSolutions(items, locations) { 
 
    // Transform the data structure to a simple array of Sets with allowed location numbers per item number, to avoid costly `indexOf` calls. 
 
    var locNums = locations.map((o, i) => i); 
 
    var locs = locations.reduce((o, loc, i) => Object.assign(o, { [loc.id]: i }) , {}); 
 
    var allowed = items.map(item => { 
 
     var allowed = new Set(locNums); 
 
     item.avoid.forEach(loc => allowed.delete(locs[loc])); 
 
     return allowed; 
 
    }); 
 
    // Now find all possible solutions through recursion 
 
    var occupied = new Set(); 
 
    var solutions = []; 
 
    var solution = []; 
 
    (function recurse(itemNo) { 
 
     var loc; 
 
     if (itemNo >= allowed.length) { 
 
      solutions.push(solution.slice()); 
 
      return; 
 
     } 
 
     for (loc of allowed[itemNo]) { 
 
      if (!occupied.has(loc)) { 
 
       solution.push(locations[loc].id); 
 
       occupied.add(loc); 
 
       recurse(itemNo+1); 
 
       occupied.delete(loc); 
 
       solution.pop(); 
 
      } 
 
     } 
 
    })(0); 
 
    return solutions; 
 
} 
 

 
// Sample data 
 
var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
]; 
 

 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"}, 
 
]; 
 

 
// Get all solutions 
 
var solutions = findSolutions(sort_items, sort_locations); 
 

 
// Pick random solution from it 
 
var randomSolution = solutions[Math.floor(Math.random() * solutions.length)]; 
 

 
// Output result 
 
console.log(randomSolution);