创建组而不重复以前的分组

Question

我创建了一个随机组创建者，但随机并不能真正保证您与以前从未合作过的人一起工作。如果有人能够生成一个 "Random Group Generator With History" 来跟踪以前的组并避免将人们一遍又一遍地放在同一组中，我肯定会使用它！有人知道怎么做吗？

为清楚起见：给定一个字符串数组

["Jason", "Kim", "Callie", "Luke"]

和一组先前的配对（也是数组）

[[["Jason", "Kim"], ["Callie", "Luke"]], [["Jason", "Luke"], ["Callie", "Kim"]]]

return 重复组成员数量最少的组

[["Jason", "Callie"], ["Luke", "Kim"]]

我在想，我要尽量减少的数量是回头客的数量。所以对于每对两个人，对于他们已经在一个团队中的每次，如果结果将他们放在同一个团队中，那么结果就会有那个分数。例如，"scoring" 得出 return 值可能如下所示：

["Jason", "Kim"] have a score of 1, they have been paired together before
["Callie", "Luke"] have a score of 1, they have been paired together before
["Jason", "Luke"] have a score of 1, they have been paired together before
["Callie", "Kim"] have a score of 1, they have been paired together before
["Jason", "Callie"] have a score of 0, they have not been paired together before
["Luke", "Kim"] have a score of 0, they have not been paired together before

选择覆盖整个列表同时生成最小分数的集合。在这种情况下，配对 ["Jason"、"Callie"] 和 ["Luke"、"Kim"] 覆盖了整个集合，并且得分为 0（没有重复分组）并且因此它是一个最佳解决方案（0 是最好的结果）。

这可能是执行此操作的错误方法（因为我认为这将花费 n 平方时间），但希望它能让您了解我要优化的内容。这不需要是完美的优化，只是 "decent answer" 不会每次都将相同的组放在一起。

理想情况下，它将能够处理任何规模的组，并且还能够处理那天有人可能外出的事实（并非所有人都会在所有阵列中）。我想要 javascript 答案，但如果有人能想出逻辑，我应该能够翻译。

Answer 1

您可以收集一个对象中的所有配对并计数。然后只拿那些数量少的。

function getKey(array) {
    return array.slice().sort().join('|');
}

var strings = ["Jason", "Kim", "Callie", "Luke"],
    data = [[["Jason", "Kim"], ["Callie", "Luke"]], [["Jason", "Luke"], ["Callie", "Kim"]]],
    object = {},
    i, j,
    keys;

for (i = 0; i < strings.length - 1; i++) {
    for (j = i + 1; j < strings.length; j++) {
        object[getKey([strings[i], strings[j]])] = 0;
    }
}

data.forEach(function (a) {
    a.forEach(function (b, i) {
        object[getKey(b)]++;
    });
});

keys = Object.keys(object).sort(function (a, b) {
    return object[b] - object[a];
});

keys.forEach(function (k) {
    console.log(k, object[k]);
});

console.log(object);

.as-console-wrapper { max-height: 100% !important; top: 0; }

创建组而不重复以前的分组

Create Groups Without Repeating Previous Groupings

javascript

arrays

algorithm

heuristics