我在编写一个算法来返回 32 支球队的所有可能的有效比赛时遇到问题。规则是:
团队的一个例子是
[
{
id: "teamId1",
opponents: ["teamId2", "teamId3", "teamId5", "teamId8", "teamId14", ...etc] // length 14
},
{
id: "teamId2",
opponents: ["teamId1", "teamId3", "teamId6", "teamId11", "teamId12", ...etc] // length 14
}
...etc
] // length 32
我认为可能有一个递归解决方案对此很优雅,但我真的很难理解它或找到已经存在的适当命名的算法。
我将使用 javascript 来实现这一点,但显然该算法是独立于语言的。但任何专门针对 javascript/使用 javascript 运算符等的示例都会有所帮助。
这可以通过创建一个嵌套循环来完成,该循环获取球队及其对手的每组配对,并将其添加到日程表中(如果该配对尚未包含在日程表中)。这是一个例子:
const teams = [
teamId1 = {
id: "teamId1",
opponents: ["teamId2", "teamId3", "teamId5", "teamId8", "teamId14"] // length 14
},
teamId2 = {
id: "teamId2",
opponents: ["teamId1", "teamId3", "teamId6", "teamId11", "teamId12"] // length 14
}
] // length 32
// Empty aray to store the schedule
const schedule = [];
// Loop through initial array
teams.forEach(team => {
// Loop through subarray of opponents of team
team.opponents.forEach(opponent => {
// Make sure that [team, opp] is not already included in schedule
if (
!(schedule.includes([team.id, opponent]))
&& !(schedule.includes([opponent, team.id]))
) {
// add pairing to schedule
schedule.push([team.id, opponent]);
}
})
})
console.log(schedule);
编辑:
为了回应您下面的评论,这是上述代码的一个版本,它为数组中的每个元素创建一个新的排列:
const teams = [
teamId1 = {
id: "teamId1",
opponents: ["teamId2", "teamId3", "teamId5", "teamId8", "teamId14"] // length 14
},
teamId2 = {
id: "teamId2",
opponents: ["teamId1", "teamId3", "teamId6", "teamId11", "teamId12"] // length 14
}
] // length 32
// Empty aray to store the schedule
const schedule = [];
// Loop through initial array
teams.forEach(team => {
const permutation = [];
// Loop through subarray of opponents of team
team.opponents.forEach(opponent => {
// Make sure that [team, opp] is not already included in schedule
if (
!(permutation.includes([team.id, opponent]))
&& !(permutation.includes([opponent, team.id]))
&& schedule.every(i => !(i.includes([team.id, opponent])))
&& schedule.every(i => !(i.includes([opponent, team.id])))
) {
// add pairing to schedule
permutation.push([team.id, opponent]);
}
})
schedule.push(permutation);
})
console.log(schedule);