Jak losowo odwzorować elementy jednej tablicy na te z innej tablicy, gdy pewne obiekty muszą unikać łączenia w pary?

Question

Tworzę grę, w której gracze będą musieli posortować obiekty na ekranie w odpowiednie lokalizacje docelowe. Szukam sposobu na przetasowanie obiektów, aby żaden obiekt nie zaczął się we właściwym miejscu. Więc nie wprowadzamy się w szalony świat podwójnych negatywów, zamierzam nazwać lokalizacje "poprawnej odpowiedzi", "unikać" lokalizacji, i "nieprawidłowej odpowiedzi" lokalizacje "prawidłowe" lokalizacje dla tego rodzaju.

Macierze może wyglądać następująco:

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"}, 
]; 

Tak więc, na przykład, pierwszy i drugi obiekty sort_items mogą być umieszczone na target3, target4 lub , lecz nie target1 lub target2.

Próbowałem już różnych metod, ale wszystkie mają problem z tym, że do końca sortowania jedyne pozostałe lokalizacje są często nieważne dla pozostałych elementów sort_item. Na przykład:

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 

Nawet w tym przykładzie, zbieranie inny losowo i zamiana z wydaje się złym pomysłem, ponieważ połowa z pozostałych również spowodować nieprawidłową spotkanie na wymianę.

Czy istnieje dobra metoda, aby to zrobić?

Answer 1

Jeśli chcesz zagwarantować, że każdy przedmiot ma równe prawdopodobieństwa, aby skończyć na jednej z pozycji, które może zająć, bez żadnego uprzedzenia wywołanego przez przedmioty, które zostały przetworzone przed nim, jestem skłonny pomyśleć, że tylko "łatwym" sposobem jest rozpoczęcie od całkowicie losowej listy.

Następnie można przejść przez listę i spróbować zamienić każdy nieprawidłowy element na pierwszy ważny, który napotka po nim.

Dokładniej, poniżej algorytm robi to w ten sposób:

// 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 

To się nie uda za każdym razem. A kiedy się nie powiedzie, będziesz musiał zrestartować od nowa.

Jest to jednak bardziej sprawiedliwe niż próba wypełnienia gniazd po kolei w określonej kolejności i bardziej wydajne niż zwykłe przetasowanie listy, dopóki nie otrzymamy ważnego. (W tym staramy się „naprawić” to przed odrzuceniem.)

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

Zrobiłem kilka dalszych badań, które sugerują, że to jeszcze bardziej tendencyjne niż ja oczekując tego.

Oto, co warto tutaj zrobić, w uproszczonej wersji 100% wersji próbnej i błędu. Ten ma gwarancję bezstronności.

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

tutaj rozwiązanie, które generuje wszystkie możliwe rozwiązania przez rekursję, a następnie wybiera losowy.W porównaniu z przypadkowymi rozwiązaniami prób i błędów, może to dać szybsze wyniki, gdy liczba rozwiązań jest ograniczona w porównaniu do rozmiaru danych wejściowych.

Po drugie, gwarantuje to, że każde rozwiązanie ma równe szanse na bycie wybranym.

Należy pamiętać, że skrypt wymaga obsługi ES6.

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);