如何在某些對象必須避免被配對在一起時，將一個數組的元素隨機映射到另一個數組的元素？

Question

我正在創建一個遊戲，玩家需要將屏幕上的對象分類到正確的目標位置。我正在尋找一種方法來洗滌物體，以便沒有物體在正確的位置開始。因此，我們不會陷入一個雙重否定的瘋狂世界，我要稱之爲「正確答案」的地點「避免」地點，以及「不正確答案」地點的「有效」地點。

的陣列可能是這樣的：

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

因此，例如，在sort_items第一和第二物體可以被放置在target3，target4，或，但不target1或target2。

我已經嘗試了許多不同的方法，但他們都有問題，在排序結束時，剩餘的sort_items中剩餘的唯一位置經常無效。例如：

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 

即使在這個例子中，隨機挑選另一個和交換與它似乎是一個好主意，因爲其他人的一半也將導致在交換的無效比賽。

是否有一個很好的方法來做到這一點？

Answer 1

如果你想保證每個物品具有相同的概率，最終達到它允許佔用的位置之一，而沒有任何由之前處理的物品引起的偏差，我傾向於認爲只有'簡單'的方法是從一個完全隨機的列表開始。

然後，您可以遍歷列表並嘗試將每個無效項與您在其之後遇到的第一個有效項交換。

更確切地說，下面的算法做這種方式：

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

這不會每次都能成功。當它失敗時，你將不得不從頭開始重新啓動。

然而，這比試圖以給定的順序一個接一個地填充插槽更爲公平，並且比簡單地洗刷列表直到獲得有效的列表更有效。 （在我們拒絕它之前嘗試「修復」它。）

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

編輯

我做了一些進一步測試這表明，它仍然更偏向比我期待它。

值得一提的是，這裏有一個更簡單的100％試用版。這一個保證是沒有偏見的。

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

這裏是通過遞歸產生所有可能的解決方案，然後選取一個隨機的一個溶液中。與隨機反覆試驗解決方案相比，與輸入大小相比，解決方案的數量有限有限，這可能會帶來更快的結果。

其次，這保證每個解決方案獲得被選中的概率相等。

請注意，腳本需要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);