使用递归挑选团队

Question

我正在尝试编写一个程序，显示具有字符A、B、C……等等的团队的所有可能组合。

输入：（5,3）

5是小组规模，3是团队规模。

从{A，B，C，D，E}中选择3个

预期产出 ： ABC，ABD，ABE，ACD，ACE，ADE，BCD，BCE，BDE，CDE

下面是我到目前为止编写的代码。

public class teamApp 
{
    public static void main(String[] args) {
        int groupSize =5;
        int teamSize = 3;
        char start = 'A';
        String sequence = "";
        showTeam(sequence,start,groupSize,teamSize);
    }

    public static void showTeam(String sequence,char start, int n, int k)
    {
        if(n==0||k==0||k>n) {
            System.out.println(sequence);
            return;
        } else {
            showTeam(sequence+start,start++,n-1,k-1);       
            showTeam(sequence,start++,n-1,k);
        }
    }
}

我尝试使用< code>(n，k) = (n-1，k-1) (n-1，k)定理。(其中n =组大小k =团队大小)。我当前的输出是

AAA
AAB
AAC
AA
ABB
ABC
AB
ACC
AC
A
BBB
BBC
BB
BCC
BC
B
CCC
CC
C

我做错了什么？

Answer 1

这是我收藏的同一个程序...

public class TeamSelector {

    public static void main(String[] args) {
        String sequence = "";
        int groupSize = 5;
        int teamSize = 3;
        showTeams(groupSize, teamSize, sequence, 'A', teamSize - 1);
    }

    public static void showTeams(int groupSize, int teamSize, String sequence, 
                                                char groupMember, int validNode) {
        if (teamSize > groupSize || groupSize < 0 || teamSize < 0) return;

        sequence += Character.toString(groupMember);
        groupMember++;
        // Left call
        showTeams(groupSize - 1, teamSize - 1, sequence, groupMember, validNode);
        sequence = sequence.substring(0, sequence.length() - 1);

        if (sequence.length() == validNode) {
            System.out.println(sequence + (char) (groupMember - 1));
        }
        // Right call
        showTeams(groupSize - 1, teamSize, sequence, groupMember, validNode);
        groupMember--;
    }
}

Answer 2

代替

start++

使用

start + 1

如果您使用start，start变量将仅在递归之后增加，而不是在调用递归之前增加。

使用起始 1 将新值作为参数传递。

在 java 中，有 3 个不同的运算符可用于递增一个变量：

< li >开始1 < li >开始 < li >开始

start 1是一个值为start 1的表达式，它不递增start。

开始是一个表达式，其值是开始（不是开始1），它将开始增加1

开始是一个表达式，其值为开始1，并将开始增加1。

这里是初始值为5的示例。

                      start + 1         start++           ++start
                      ---------         -------          --------
 initial start value      5                 5                5
 end start value          5                 6                6
 expression value         6                 5                6

请注意，开始 1 并没有真正改变开始。您需要像 start = start 1 这样的代码来更改它。

在代码中，您对更改当前方法中start的值不感兴趣。您只需要将start 1传递给递归。

Answer 3

首先，你应该改变

showTeam(sequence+start,start++,n-1,k-1);
showTeam(sequence,start++,n-1,k);

到

showTeam(sequence+start,(char)(start+1),n-1,k-1);
showTeam(sequence,(char)(start+1),n-1,k);

否则，只有第二个递归调用会获得 Start 的递增值（因为 start 返回 start 的原始值）。

其次，当递归展开时，也会打印部分序列。要避免这种情况，请添加以下条件：

    if (n==0||k==0||k>n) {
        if (k==0) // this condition will make sure that only complete
                  // sequences of k elements will be printed
            System.out.println(sequence);
    } else {
        showTeam(sequence+start,(char)(start+1),n-1,k-1);
        showTeam(sequence,(char)(start+1),n-1,k);
    }

输出：

ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE