如何在某些对象必须避免被配对在一起时，将一个数组的元素随机映射到另一个数组的元素？

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