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

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 或 target5 上，但不能放在 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);