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

Question

我正在创建一款游戏，玩家需要将屏幕上的对象分类到正确的目标位置。我正在寻找一种方法来随机排列对象，以便没有对象从正确的位置开始。所以我们不会陷入双重否定的疯狂世界，我将调用 "correct answer" 个位置 "avoid" 个位置，并将 "incorrect answer" 个位置称为 "valid" 个位置.

数组可能如下所示：

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

如果你想保证每个项目都有相同的概率最终出现在它被允许占据的位置之一，而不是由它之前处理的项目引起的任何偏差，我倾向于认为唯一的 'easy' 方法是从一个完全随机的列表开始。

然后，您可以浏览列表并尝试将每个无效项目与您在它之后遇到的第一个有效项目交换。

更准确地说，下面的算法是这样做的：

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

这不会每次都成功。当它失败时，您将不得不从头开始。

然而，这比尝试按给定顺序一个一个地填充插槽更公平，并且比简单地洗牌列表直到我们得到一个有效的插槽更有效。（因为我们在拒绝它之前尝试 'fix' 它。）

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

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

How to randomly map the elements of one array to those of another array when certain objects must avoid being paired together?

javascript

arrays

shuffle