通过进制法捕获所有组合

题目:
现有2支队伍,每支队伍有2个人,两支队伍的人相互握手,求所有的握手组合方式。
我们可以快速得到答案:
假设两只队伍分别为A,B;成员代号为A1、A2、B1、B2;
则组合方式有以下四种:
A1,B1;A1,B2;A2,B1,;A2,B2;

难度稍微升级一下
题目:
现有3支队伍,每支队伍有3个人,3支队伍的人相互握手,求所有的握手组合方式。
当我们将队伍换成三支或更多的时候,答案可能并不是很快就能得到的

抽取题目意图:
对于编程来说,碰到相似的逻辑把他抽为方法,实现单层维护,多处调用是一个很好的习惯,那么现在我们把刚才的逻辑抽出来先写个接口


/**
     * 打印输出所有的组合方式(第一列为第一组,第二列为第二组...)
     * 举例:1,1,1 说明:共有三组,当前组合为第一组的第一个元素,第二组的第一个元素,第三组的第一个元素
     * @param troops 每个组的长度/人数 举例:{3,3,3} 说明:共有三组,每组有三个人
     */
public void getGroup(int[] troops);

在具体实现时如果没有整理出来一个好的排序思路,出现重复组合和漏组合的概率极高

针对此需求推荐使用进制法:
排序如下
1,1,1
2,1,1
3,1,1
1,2,0

即前一位达到传入数组的最大长度时,往后一位进一,这样就能保证不会出现组合缺漏重复的情况

发表评论

电子邮件地址不会被公开。 必填项已用*标注