求一个比赛唯一对阵分配算法

Question

已知比赛选手，要两两对阵

$players = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];

已经分配过的比赛，可能是手动分配的

$matchA = [
    ['a', 'b'], ['c', 'd'], ['e', 'f'], ['g', 'h']
];

$matchB = [
    ['b', 'c'], ['a', 'd'], ['e', 'g'], ['f', 'h']
];

现在要添加一场比赛，生成matchC
结果可以是这样，就是球员对阵情况要尽量唯一

求类似下面的输出

$matchC = [
    ['a', 'c'], ['b', 'd'], ['e', 'h'], ['f', 'h']
];

Answer 1

可以先让人员随机排列，然后再从前往后两两一组，随机排列可以使用洗牌算法，js实现如下

function fn(arr){
    var res = [], item = []
    for(var i = 0, l = arr.length; i < l; i++){
        const j = i + Math.floor(Math.random() * (arr.length - i));
        //交换
        [arr[i], arr[j]] = [arr[j], arr[i]]

        item.push(arr[i])
        if(item.length == 2){
            res.push(item)
            item = []
        }
    }
    if(item.length){res.push(item)}
    return res
}

fn(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'])