javascript - 配对号码，必须一次配对一个，不能与自己或小组成员配对

Question

我有一个包含 8 个数字的数组，1-8

arr = [1, 2, 3, 4, 5, 6, 7, 8]

数组中的每个数字都是一个组的一部分

1 & 2 - group a
3 & 4 - group b
5 & 6 - group c
7 & 8 - group d

我需要做的是将数组中的每个数字与同一数组中的另一个数字进行匹配，但它们不能在同一组中

• 1 & 2 可能与 1 或 2 不匹配
• 3 & 4 可能与 3 或 4 不匹配
• 5 & 6 可能与 5 或 6 不匹配
• 7 & 8 可能与 7 或 8 不匹配

条件

1. 可能不是预先确定的，给定相同的输入，不同的解决方案必须是可能的
2. 没有重复配对，例如如果 2 对 8，4 不能也与 8 配对
3. 他们必须一次配对一个，并且能够留下一些未完成的配对并在以后回来完成更多配对
4. 配对无法重置或撤消，一旦配对即永久有效
5. 一对不能在所有 情况下同时运行。例如，如果 2 与 3 配对，则 3 不能总是与 2 配对。如果这种情况偶尔发生是可以接受的，但这不是预期的功能。
6. 我们不能假定配对将按任何特定顺序进行。例如，第一对可能由 1、7 或 3 等组成。任何号码都可能需要随时配对。

我的问题是，如果你按正确的顺序选择它，你可能会卡在最后一个数字上，剩下的唯一配对就是与它自己或它的队友配对。

我想在这里强调一个条件，因为它在答案中一直被忽略。我希望一次配对一个。这意味着您应该能够根据需要将每个配对分开。我希望能够在第 0 天进行配对，然后我可以在第 1 天、第 2 周或 2750 年回来进行第二次配对。这是必要的。每个配对都必须完全相互独立，最后，最后一个数字必须仍然能够进行有效配对。

例子...

6 with 8
7 with 6
5 with 7
3 with 5
8 with 4
2 with 3
4 with 2
1 with _

这个命令让 1 除了自己别无选择。

我该怎么做才能让它无论最后一个数字总是有一个可行的配对？

更新:我在答案部分添加了一个相当不错的解决方案。如果您仍在努力理解我想要完成的任务，请尝试阅读我在答案部分的回答。附加代码已过时，因为我找到了当前可用的答案。

下面是过时的代码

 function selectGiftee(req, res, db){
        const {user_id, group_id} = req.body
        db.select('name', 'user_id', 'giftee_id', 'group_id').from('users')
        .then (data => {
            if (data.length) {
    // only sending available giftees

                const taken = [];
                const fullList = [];
                let available = [];

    // figure out which giftees are taken
                data.forEach( user => {
                    if (user.giftee_id !== null){
                        taken.push(user.giftee_id)
                    }
                    if (user.group_id === group_id) {
                        taken.push(user.user_id)
                    }
                })
    // add all giftees to a list
                data.forEach( user => {
                    fullList.push(user.user_id)
                })

    // only add available giftees to the available list
                available = fullList.filter(val => !taken.includes(val));

    // respond with only giftees that are not taken
                res.json(available)

Answer 1

让我们将我们的组作为一个长列表:

1 2|3 4|5 6

现在让我们把它从中间分开，然后把一部分移到另一部分下面:

1 2|3
4|5 6

现在每个元素都有一对(每列)不是来自组本身，您可以通过将所有列附加到一个来将其变成一个连续列表:

(1 -> 4) -> (2 -> 5) -> (3 -> 6) -> 

现在要获得不同的组合，我们只需打乱组数组和之前的组本身。

// stolen from https://stackoverflow.com/questions/6274339/how-can-i-shuffle-an-array
function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}


const groups = [[1, 2], [3, 4], [5, 6], [7, 8, 9]];

groups.forEach(shuffle);
shuffle(groups);

console.log("shuffled:", groups.join(" | "));

const list = [].concat(...groups);

console.log("list:", list);

// Now pair every element by matching the first and the second half:
const pairs = [];

for(let i = 0; i < Math.floor(list.length / 2); i++) {
  pairs.push([
   list[i],
   list[i + Math.floor(list.length / 2)]
  ]);
 }

 if(list.length % 2)
   pairs.push([list.pop()]);
 console.log("pairs:", pairs.join(" | "));

 const result = [].concat(...pairs);

 for(let i = 0; i < result.length; i++)
   console.log(result[i] + " -> " + result[(i + 1) % result.length]);