[算法][排列组合]每一轮两两组合不允许重复

本文主要是介绍[算法][排列组合]每一轮两两组合不允许重复，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.问题描述：

给定N个数（N是偶数），给它们进行两两组合并列举所有可能的轮数，每一轮的组合不可以一样，并且两个元素只允许组合一次。
比如N是4，有A,B,C,D共4个元素，那么可以共有3轮组合，分别是：

从第四轮开始要开始重复了，因此这里不重复组合的最大轮数是3

输入是一个含有偶数元素的列表，输出是排好之后的每一轮。

2.问题分析

首先要明确组合的规律，也可以说是条件：

• 条件1：每轮都包含N个元素，而且只包含N个元素
• 条件2：每轮有N/2对组合
• 条件3：不重复的轮数是N-1，因为每个人都会与其他的N-1个人pair，一共是N-1轮

可以使用回溯法来解决问题，思路是：

• 1.列举所有可能的组合，比如N=4时，所有的组合是A-B， A-C， A-D，B-C， B-D， C-D
• 2.从中选出一对组合加入到当轮的组合安排中，选完一个组合后，就有相关组合的不能再选，比如选了A-B，不能选的就是：A-C， A-D，B-C， B-D
• 3.选完之后要检查是否满足条件1，如果没有满足，就把它拿出来,这一轮就不要选它了，给这些不能选的做一个标记。
• 4,对照条件1，各个元素是只出现一次。如果没有满足需要回退，如果满足则到下一步
• 5.对照条件2，是否选了N/2个组合，如果没有满足条件2，说明该轮没有完成，需要跳到步骤2，如果该轮完成了需要把该轮不能选的元素标记成下一轮是可以选的，这轮选完的下一轮就不能选了。
• 6.对照条件3是否选完了N-1轮，如果没有就继续到步骤2，如果结束了就完成了，可以退出程序

以上是分析思路，如果写程序的话，步骤2-6要倒着写，因为大的条件判断要放在前面。

3.问题结果

具体的代码可以参考https://github.com/ILoveStudyAndWork/pair-generator
上述的过程在PairGenerator的generatePairSchedule()里面，要跑的话可以在Solution中运行，运行的步骤可以参考打印在控制台的结果，会显示每次选择后各个列表的元素。

4.问题扩展

可以扩展成一个现实问题，团队有N个人，每次工作需要两两组合完成任务，如果是人数是单数那么有一个人会单独做。这个程序就可以生成组合的计划，让每个人都和其他人互相组合。
运行时只需要把成员的名单放到teamMembers中

 Set<String> teamMembers = new HashSet<>();
        teamMembers.add("A");
        teamMembers.add("B");
        teamMembers.add("C");
        teamMembers.add("D");
        teamMembers.add("E");
        PairGenerator pairGenerator = new PairGenerator(teamMembers);
        pairGenerator.generatePairSchedule();
        pairGenerator.printSolution();

而且这个程序支持输入成员，如果是单数成员，程序会自动补全一位（Nobody）变成偶数
选择的过程可以参考打印出来的log，例如选择了第一个元素A + B之后,各列表的元素是：

selectedPairs pairs:
A + B
disable pairs:
0:
A + C
A + D
A + E
A + Nobody
B + C
B + D
B + E
B + Nobody
Choosable pairs:
C + D
C + E
C + Nobody
D + E
D + Nobody
E + Nobody
result:

例如选择了第二个元素C + D之后,各列表的元素是：

selectedPairs pairs:
A + B
C + D
disable pairs:
0:
A + C
A + D
A + E
A + Nobody
B + C
B + D
B + E
B + Nobody
1:
C + E
C + Nobody
D + E
D + Nobody
Choosable pairs:
E + Nobody
result:

这篇关于[算法][排列组合]每一轮两两组合不允许重复的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！