n个人匹配，两两匹配，匹配多轮

## 要求

要求 n 个人匹配，如果是奇数则有一人轮空，两两匹配，匹配多轮，每轮要求不能和上轮匹配对象重复，优先选择匹配次数少的（满足其他成员的情况下）。

不能重复:如第一轮 1 2 匹配，则下一轮 1 不能与 2 匹配

优先次数少:比如 1234，第一轮 1 2 匹配，则 1 与 2 匹配次数为 1 次，1 与 3，1 与 4 为 0 次，则优先匹配 3，4
特殊情况：3 只能被 2 选择，那 1 只能选择 4

第 1 轮 1-2 3-4
第 2 轮 1-3 2-4
第 3 轮 1-4 2-3
第 3 轮 1-2 3-4
第 4 轮，跟上面第 2 轮一样

## 代码

```js
function test(nums) {
    const map = {};
    const length = nums.length;
    // 初始化数据
    // 第二个数字是匹配次数
    // 处理为 {'1': { '2': 0, '3': 0, '4': 0 }}
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length; j++) {
            if (i !== j) {
                const tmp = map[nums[i]] || {};
                tmp[nums[j]] = 0;
                map[nums[i]] = tmp;
            }
        }
    }
    // console.log(map);
    // 轮次
    let CNT = 0;
    // 上一轮匹配结果
    let lastSet = new Set();
    while (CNT++ < 10000) {
        let res = [];
        // 直到找到结果
        while (res.length < Math.floor(nums.length / 2)) {
            res = [];
            // 记录已经匹配的 id
            const dead = new Set();
            // 当前轮次的匹配情况
            const currentSet = new Set();
            for (let i = 0; i < length; i++) {
                // 已经找过
                if (dead.has(nums[i])) continue;
                // 匹配次数相同的，随机打乱顺序
                // Object.entries(map[nums[i]]) 将对象转成数组
                // 如 { '2': 0, '3': 0, '4': 0 } 转成 [[2,0],[3,0],[4,0]]
                const arr = Object.entries(map[nums[i]]).sort((a, b) => {
                    // 相同就随机打乱
                    if (a[1] === b[1]) {
                        return Math.random() - 0.5;
                    }
                    return a[1] - b[1];
                });
                // 轮询匹配
                for (let [node, count] of arr) {
                    // 转成数字
                    node = Number(node);
                    // 说明被选走 跳过
                    if (dead.has(node)) continue;
                    // 跟上次匹配一样 跳过
                    if (lastSet.has([nums[i], node].sort((a, b) => a - b).join())) continue;

// 匹配结果
                    res.push([nums[i], node]);
                    // 加入到已经匹配过的集合
                    dead.add(nums[i])
                    dead.add(node);
                    // 匹配次数 +1
                    map[nums[i]][node]++;
                    map[node][nums[i]]++;

// 当前匹配的
                    currentSet.add([nums[i], node].sort((a, b) => a - b).join());
                    break;
                }
            }
            lastSet = currentSet;
        }
        // if (res.length !== 4) {
        console.log(` 第 ${String(CNT)}轮 `, lastSet, res);
        // }
    }
}

// nums = [1, 2, 3, 4]
// nums = [1, 2, 3, 4, 5, 6]
nums = [1, 2, 3, 4, 5, 6, 7, 8]
// nums = [];
// for(let i=1;i<=1000;i++){
//     nums.push(i);
// }
console.log(test(nums));
```

新的

```js
// 用循环
// function test(nums) {
//     const map = {};
//     const length = nums.length;
//     // 初始化数据
//     // 第二个数字是匹配次数
//     // 处理为 {'1': { '2': 0, '3': 0, '4': 0 }}
//     for (let i = 0; i < length; i++) {
//         for (let j = 0; j < length; j++) {
//             if (i !== j) {
//                 const tmp = map[nums[i]] || {};
//                 tmp[nums[j]] = 0;
//                 map[nums[i]] = tmp;
//             }
//         }
//     }
//     // console.log(map);
//     console.log('=================');
//     // 轮次
//     let CNT = 0;
//     // 上一轮匹配结果
//     let lastSet = new Set();
//     while (CNT++ < 1) {
//         if (CNT % 7 === 0) {
//             lastSet = new Set();
//             for (let i = 0; i < length; i++) {
//                 for (let j = 0; j < length; j++) {
//                     if (i !== j) {
//                         const tmp = map[nums[i]] || {};
//                         tmp[nums[j]] = 0;
//                         map[nums[i]] = tmp;
//                     }
//                 }
//             }
//         }
//         let res = [];
//         // 直到找到结果
//         while (res.length < Math.floor(nums.length / 2)) {
//             res = [];
//             // 记录已经匹配的id
//             const dead = new Set();
//             // 当前轮次的匹配情况
//             const currentSet = new Set();
//             for (let i = 0; i < length; i++) {
//                 // 已经找过
//                 if (dead.has(nums[i])) continue;
//                 // 匹配次数相同的，随机打乱顺序
//                 // Object.entries(map[nums[i]]) 将对象转成数组
//                 // 如 { '2': 0, '3': 0, '4': 0 } 转成 [[2,0],[3,0],[4,0]]
//                 const arr = Object.entries(map[nums[i]]).sort((a, b) => {
//                     // 相同就随机打乱
//                     if (a[1] === b[1]) {
//                         return Math.random() - 0.5;
//                     }
//                     return a[1] - b[1];
//                 });
//                 // console.log(nums[i],' ',arr.map(item=>`${item[0]}:${item[1]}`).toString());
//                 // 轮询匹配
//                 for (let [node, count] of arr) {
//                     // 转成数字
//                     node = Number(node);
//                     // 说明被选走 跳过
//                     if (dead.has(node)) continue;
//                     // 跟上次匹配一样 跳过
//                     if (lastSet.has([nums[i], node].sort((a, b) => a - b).join())) continue;

//                     // 匹配结果
//                     res.push([nums[i], node]);
//                     // 加入到已经匹配过的集合
//                     dead.add(nums[i])
//                     dead.add(node);
//                     // 匹配次数+1
//                     map[nums[i]][node]++;
//                     map[node][nums[i]]++;

//                     // 当前匹配的
//                     currentSet.add([nums[i], node].sort((a, b) => a - b).join());
//                     break;
//                 }
//             }
//             // console.log(CNT,lastSet,res);
//             lastSet = currentSet;
//             console.log(`第${CNT}轮`, map);
//         }
//         // if (res.length !== 4) {
//         // console.log(`第${String(CNT)}轮`, lastSet, res);
//         // }

//     }
// }

// 回溯
function test(nums) {
    const map = {};
    const numCnt = {};
    const length = nums.length;
    // 初始化数据
    // 第二个数字是匹配次数
    // 处理为 {'1': { '2': 0, '3': 0, '4': 0 }}
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length; j++) {
            if (i !== j) {
                const tmp = numCnt[nums[i]] || {};
                tmp[nums[j]] = 0;
                numCnt[nums[i]] = tmp;
                const tmp2 = map[nums[i]] || [];
                tmp2.push(nums[j]);
                map[nums[i]] = tmp2;
            }
        }
    }
    // console.log(map);
    console.log('=================');
    // 轮次
    let CNT = 0;
    // 上一轮匹配结果
    let lastSet = new Set();
    while (CNT++ < 1) {
        // if (CNT % 7 === 0) {
        //     lastSet = new Set();
        //     for (let i = 0; i < length; i++) {
        //         for (let j = 0; j < length; j++) {
        //             if (i !== j) {
        //                 const tmp = map[nums[i]] || {};
        //                 tmp[nums[j]] = 0;
        //                 map[nums[i]] = tmp;
        //             }
        //         }
        //     }
        // }
        let res = [];

// 先将匹配次数都进行排序
        for (let i = 0; i < length; i++) {
            map[nums[i]].sort((a, b) => {
                // 相同就随机打乱
                if (numCnt[nums[i]][a] === numCnt[nums[i]][b]) {
                    return Math.random() - 0.5;
                }
                return numCnt[nums[i]][a] - numCnt[nums[i]][b];
            });
        }

// 匹配结果
                    data.add([nums[i], node].sort((a,b)=>a-b));
                    // 加入到已经匹配过的集合

nextNode = node;
                    // 匹配次数+1
                    // numCnt[nums[i]][node]++;
                    // numCnt[node][nums[i]]++;

// 当前匹配的
                    // currentSet.add([nums[i], node].sort((a, b) => a - b).join());
                    // 符合条件就结束
                    // break;

// 开始下一位
                    
                    dead.add(nextNode);
                    // dead.add(num);
                    // dead.add(nums[i]);
                    [nums[k], nums[i]] = [nums[i], nums[k]];
                    dfs(nums, k + 1, dead, data, hasDead);
                    // 交换回去，再删了原来的值
                    [nums[k], nums[i]] = [nums[i], nums[k]];
                    // data.delete([nums[i], node].sort((a,b)=>a-b));
                    // dead.delete(nextNode);
                    // dead.delete(nums);
                    // dead.delete(nums[i]);
                }
                // dead.delete(num);

}
        }

// 记录已经匹配的id
        const dead = new Set();
        // 当前轮次的匹配情况
        const currentSet = new Set();

dfs(nums, 0, dead, new Set(), new Set())
        lastSet = currentSet;
        // console.log(CNT,lastSet,res);
        // console.log(`第${CNT}轮`, map);

// if (res.length !== 4) {
        console.log(`第${String(CNT)}轮`, result.sort((a,b)=>{
            if(a[0][0]===b[0][0]){
                return a[0][1]-b[0][1];
            }
            return a[0][0]-b[0][0];
        }));
        // console.log(`第${String(CNT)}轮`, res);
        // }

}
}

nums = [1, 2, 3, 4, 5, 6, 7, 8]
// nums = [1, 2, 3, 4, 5, 6]
// nums = [1, 2, 3, 4]
// nums = [];
// for(let i=1;i<=1000;i++){
//     nums.push(i);
// }
console.log(test(nums));
```