配对数字，必须逐一成对，不能与自己或小组成员配对。

Question

配对数字，必须逐一成对，不能与自己或小组成员配对。

4

我有一个包含1-8这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)

- Chance

2

欢迎。请展示您的代码，并尽可能精确地说明您想从给定输入（据我所理解，是一个数组和一些“组”）中获得什么。 - Jeto

1 和 ? ... ? 应该是除了 1 或 2（同一组）之外的所有数字。那么，有没有关于最佳配对（从 3,4,5,6,7,8 中选择一个）的规则呢？就我所看到的情况而言，这将与您的第二个条件发生冲突。 - Roko C. Buljan

每个“组”的项目数量是否可预测地相似？例如，您能否依赖于每个组具有相同数量的项目？ - CertainPerformance

@Chance 一个组可以包含超过2个数字吗？ - Koushik Chatterjee

@Redu，您的解决方案违反了条件1，因为配对不应该预先确定。 - Alexander Moser

显示剩余5条评论

4个回答

1

这是我想出来回答自己问题的方法。首先，我将组分成了两个单独的元组。这意味着a和b组在metagroup 1中，c和d组在metagroup 2中。

其次，我添加了一个加权系统。因此，当正在尝试进行配对时，我会收集已经被取走的配对中的所有次要数字，并为它们的组添加权重。例如，如果4已经与6配对，那么组c的权重就会增加1。但这仅是加权的第一步。

现在，在当前示例中，4已经与6配对，因此组c的权重为1。现在我们想要配对3。3与4在同一组，即组b。因此，现在组3将查看4，并发现它已经有了一个配对，即6。6是metagroup 2的一部分，因此现在组c和d都被赋予+10的权重。这使得组c的权重为11，组d的权重为10。 编辑：我添加了这两个条件以清除我发现的一些不常见的错误。首先，我为尚未配对的任何数字添加了负权重（-1）。这样可以使没有配对的数字在有配对的数字之前被选择。我不得不这样做，因为我仍然偶尔会遇到一个无法配对的数字。其次，我改变了同一组中数字的处理方式。以前，我只是将它们从可用列表中删除。但是，如果该组的权重最低，这会导致问题。算法会建议从该组中选择一个数字，因为它的权重最低，但是该组中没有数字，因此导致死锁。现在，我为数字所在的组添加20个权重，以便它永远不会成为最低权重。

现在我们已经设置好权重，3仍在尝试配对。我们查看所有的权重，发现组a和b的分数都是0，而c的分数是11，d的分数是10。3是b组的一部分，并且特别阻止了与自己配对，因此这只留下了组a可供选择，因此3将与1或2配对。

这是我找到的唯一一种方法，可以让我按需一次形成一对。以下是我的代码，可能有点混乱，因为我直接从程序中提取，但如果有人需要解释它的工作原理，我很乐意解释。

function chooseGiftee(avail){
    const int = avail.length;
    const index = Math.floor((Math.random() * int) + 1);
    return avail[index-1];
}

function getCandidates(weights){
        return candidates;
}



function selectGiftee(req, res, db){
    const {user_id, spouse_id, group_id} = req.body;
    if (!user_id || !spouse_id || !group_id){
        return res.status(400).json('Missing Credentials')
    }

    db.select('user_id', 'spouse_id', 'giftee_id', 'group_id').from('users')
    .then (data => {

        if (data.length) {
// only sending available giftees


            let newGiftee;
            const taken = [];
            const fullList = [];
            let available = [];
            let filteredAvailable = [];
            let nullCount = 0;
            let nullArr = [];
            let a = 0;
            let b = 0;
            let c = 0;
            let d = 0;

//for the love of god man please refactor all this stuff!!!!!!!


// figure out which giftees are taken and set weight for already picked groups 
            data.forEach( user => {

                if (user.giftee_id === null){
                    switch (user.user_id){
                        case 1:
                        case 2:
                            a--;
                            break;
                        case 3:
                        case 4:
                            b--;
                            break;
                        case 5:
                        case 6:
                            c--; 
                            break;
                        case 7:
                        case 8:
                            d--;
                            break;
                    }
                }

                if (user.giftee_id !== null){
                    taken.push(user.giftee_id);
                }
                switch (user.giftee_id){
                        case 1:
                        case 2:
                            a++;
                            break;
                        case 3:
                        case 4:
                            b++;
                            break;
                        case 5:
                        case 6:
                            c++; 
                            break;
                        case 7:
                        case 8:
                            d++;
                            break;
                    }

                if (user.group_id === group_id) {
                    switch(user.giftee_id){
                        case 1:
                        case 2:
                        case 3:
                        case 4:
                            a += 10;
                            b += 10;
                            break;
                        case 5:
                        case 6:
                        case 7:
                        case 8:
                            c += 10;
                            d += 10;
                            break;
                    }
                    switch(user.group_id){
                        case 1:
                            a += 10;
                            break;
                        case 2:
                            b += 10;
                            break;
                        case 3:
                            c += 10;
                            break;
                        case 4:
                            d += 10;
                            break;
                    }
                }
            })


// add all giftees to a list
            data.forEach( user => {
                fullList.push(user.user_id)
            })

// only add available giftees to available list

            available = fullList.filter(val => !taken.includes(val));


// Choose from what is available based on groupWeight
            let lowWeight = Math.min(a, b, c, d);
            let candidates = [];
            if(lowWeight === a){
                    candidates.push(1, 2);
            }
            if(lowWeight === b){
                    candidates.push(3, 4);
            }
            if(lowWeight === c){
                    candidates.push(5, 6);
            }
            if(lowWeight === d){
                    candidates.push(7, 8);
            }

            filteredAvailable = available.filter(val => candidates.includes(val));



// check if there is three or less choices left, and if so we need to prevent a deadlock

            if (nullCount <= 4){
                filteredAvailable = filteredAvailable.filter(val => !nullArr.includes(val))
            }
            newGiftee = chooseGiftee(filteredAvailable);

- Chance

@JonasWilms 这是我想出来的。 - Chance

你的代码中有一个“fun”函数，似乎不知道从哪里冒出来的... 我仍然认为我提供的版本更优雅，但是对于你的努力还是要点个赞。 - Jonas Wilms

@JonasWilms，那个错误是我粘贴时出现的，感谢你指出。你的解决方案肯定更加优雅。然而，你提出了一个我没有考虑过的限制。所有的配对都可以互相匹配吗？这是我真的不想要的。原因是我正在为我的家人制作一个网站，它将自动进行秘密圣诞抽奖。如果你得到某个人，他们也得到你，那就没什么乐趣了。除此之外，秘密圣诞的一部分就是保密，如果有人发现它是这样工作的，他们就会知道谁是他们的秘密圣诞。而我也会确定谁会送我礼物。 - Chance

@JonasWilms 我进行了一些测试，这种方法适用于所有偶数组。 - Chance

是的，这就是为什么我的答案可以避免这种情况。唯一的问题是你收到礼物的团体很可能也是你要送礼物的人的团体（但并非总是如此）。 - Jonas Wilms

显示剩余3条评论

1

如果每个组都恰好包含2个值（如果不是，我会解决），那么我们可以在奇数索引处继续打印数字，以保持它们之间的墙壁。例如：

组

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

从 [1, 2] 开始的初始数组

处理下一个 -> [3, 4] 在索引1和3处打孔，这样它就变成了[1, 3, 2, 4]

现在处理下一个（[5,6]）并进行相同的操作，所以它变成了：[1, 5, 3, 6, 2, 4]

然后继续处理下一个。

现在，如果有可能长度任意的组！因此，现在出现了问题（正中要害！这就是我来到这里的原因）

首先，我们需要了解何时（在哪种条件下）可以完成这个任务！如果存在一个长度为L的组，并且所有其他组的长度总和为M，那么N-M应该小于等于1。

为什么呢？

假设一个组有3个成员，为了将它们分开，你需要至少2堵墙。因此，所有其他组的组合长度必须为2。

所以，如果满足条件，现在我们需要创建一些配对（因为现在可能了）。

第一步，按照他们的长度降序排列组数组
我们需要从第一个开始，但是如果第二个组没有完全破坏第一个组，我们需要连续的奇数索引。

让我们假设Groups是： [[1, 2, 3, 4, 5, 6], [7,8,9], [10, 11, 12], [...], [.....]] 作为第一组，长度为6和5的元素需要完全忽略，接下来的组[7, 8, 9]长度为3，因此肯定需要2个以上的元素，因此当我们在将当前组件放置在索引1、3、5后开始处理下一个组时，我们需要从7、9、...开始放置。

一旦忽略了第一个数组，我们可以从索引1开始保持奇数索引。

我可以根据需要生成一个可工作的代码，但是一旦清楚了我们要做什么，我们所有人都可以轻松地完成编码部分。主要关注算法部分。但是如果有帮助，我也可以编写代码！

添加实现示例

var groups1 = [
    [7, 8, 9],
    [10, 11],
    [1, 2, 3, 4, 5, 6],
    [12, 13]
  ],
  groups2 = [
    [1, 2],
    [3, 4],
    [5, 6],
    [7, 8]
  ];

function punchGroups(groups) {
  groups.sort((a, b) => b.length - a.length);
  let firstLen = (groups[0] || []).length,
    oic = 0, //odd index increment counter
    covered = false; //covered the largest array flag
  return groups.reduce((acc, e) => {
    if (!acc.length) {
      return acc.concat(e)
    }
    e.forEach((n, i) => {
      let idx = (covered ? (i * 2) : (oic++) * 2) + 1;
      acc.splice(idx, 0, n);
      covered = oic >= (firstLen - 1)
    })
    return acc;
  }, []);
}

console.log('Groups: ', groups2);
console.log('Pairs: ', punchGroups(groups2));
console.log('-------------------------------');
console.log('Groups: ', groups1);
console.log('Pairs: ', punchGroups(groups1));

现在，要获得不同的一对组合（显然在可能的一对中），您只需要管理所有可能组合中的组和组成员（只需使用递归来获取所有组合），并处理每个以获得所有不同的可能配对。您可以生成所有输出，并从中选择一个每天使用索引或某个因素使您的呼叫不同，可能是时间戳，并将其计算为所有可能输出数组的索引范围内的数字。

- Koushik Chatterjee

Koushik，如果我理解正确的话，我认为这将违反我的第一条规则，即不要预先确定，因为我认为你所建议的意味着例如，如果我总是给予相同的组和相同的数字，结果将始终相同。 - Chance

@Chance 在处理之前，您可以对每个组进行一次洗牌，以产生不同的输出。 - Koushik Chatterjee

@koushikmagic 这个方法存在很多问题。如果你选择所有的配对，然后在最后洗牌，那么你就没有满足条件#3，即它们必须一次配对。这将导致在最后一起配对。除此之外，当你洗牌时，有什么办法阻止1和2等人配对呢？ - Chance

输出结果可以是逻辑的（并且可以通过逻辑推导得出），也可以是随机的（例如随机数或从数组中生成随机索引），但不能同时具备两者。如果您的结果不可预测，则需要进行洗牌操作（这是一种基于随机数的操作），未来无法保证输出结果不同。因此，您可以创建组内容的所有组合（而不是洗牌），然后对所有内容使用相同的算法进行处理并生成所有输出结果。然后随机选择一个结果（或发送一个索引作为输入参数并返回该索引的值）。 - Koushik Chatterjee

关于始终不同的配对和“非预定”的问题，您需要理解，如果一组输入无法处理（我也已经展示了条件），那么根本就不会有任何输出。如果一组输入可以生成3个输出组合，则必须在这些3个组合中进行选择（这是可猜测的），然后您可以随机或顺序地最大化选择其中一个。如果您运行它4次（使用具有3个输出组合的输入），则必须重复。 - Koushik Chatterjee

@Chance 我已经发布了一段代码片段来进一步解释。你可以看一下！ - Koushik Chatterjee

0

你的数字是图节点，每个节点之间都有边，但不能与相邻节点相连。你需要用n/2条边覆盖所有n个节点，同时保证没有节点被两条边共享。这种覆盖称为完美匹配（不是我之前写的最大匹配，而是完美匹配）

使用networkx库的Python示例可以找到最大匹配（这里也是完美匹配，但我们不能总是期望这一点）：

import networkx as nx
lst = [1, 2, 3, 4, 5, 6, 7, 8]
G = nx.Graph()
for i in range(0, len(lst)):
    for j in range(i + 1, len(lst)):
        if ((i // 2) != (j // 2)): //make edge for items from different pairs
            G.add_edge(lst[i], lst[j])
#print(G.edges)
m = nx.maximal_matching(G)
print(m)
>>> {(4, 2), (1, 3), (6, 8), (5, 7)}

- MBo

如何洗牌？ - Jonas Wilms

这就是我读到的问题：“从可用数组中随机选择一个数字，然后将该数字与另一个数字配对”。 - Jonas Wilms

是的，@Jonas Wilms 是正确的。我需要逐一配对物品，并且需要能够留下一些数字未配对，以便以后可以配对。例如，如果我当前正在配对数字1，那么我只需要返回数字1的可能配对列表，这不会造成冲突。这意味着我不能返回1或2，但也意味着它不能返回任何会导致无法完成单独配对的数字。 - Chance

@chance 它必须完全随机吗？或者如果它遗漏了一些组合，那也可以吗？ - Jonas Wilms

它可以省略一些组合。我整个上午都在思考这个问题，我认为我可能已经找到了一个解决方案。我想我可以强制每两个人一组从两个不同的小组中选择。例如，如果1（A组）搭档3（B组），那么2（A组）将不被允许和4（B组）配对，而是必须从C组或D组中选择。我认为这样可以解决问题，但我还没有检查所有情况。 - Chance

显示剩余10条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonas Wilms · Accepted Answer

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

1 2|3 4|5 6

现在让我们把它分成两部分，将其中一部分移动到另一部分下面：

1 2|3
4|5 6

现在每个元素都有一个不来自于组本身的对应项（每列），您可以通过将所有列附加到一个列表中将其转换为连续列表：

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

现在，为了获得不同的组合，我们只需要在之前对组和组本身的数组进行洗牌。

// stolen from https://dev59.com/DW015IYBdhLWcg3w_Q4_
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]);