Выбор команды с использованием рекурсии

Question

Я пытаюсь написать программу, которая показывает все возможные комбинации команд с символами A, B, C ... и так далее.

Входной сигнал: (5,3)

5 является размер группы и 3 является размер команды.

выбора 3 из {А, В, С, D, Е}

Ожидаемые результаты: ABC, ABD, ABE, ACD, ACE, АДЭ, BCD, до н.э., 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); 
     } 
    } 
} 

Я попытался использовать теорему (n,k) = (n-1,k-1)+(n-1,k). (где n = groupSize k = teamSize). Мой текущий выход

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

Что я делаю неправильно?

Answer 1

Прежде всего, вы должны изменить

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 

Answer 2

Вместо

start++ 

использование

start + 1 

Если вы используете start++, переменная startбудет увеличена только после рекурсии и не до вызова рекурсии.

Используя start + 1, вы передаете новое значение в качестве параметра.

---

В Java есть 3 различных операторов, которые могут быть использованы для увеличения одной переменной:

• старт + 1
• старт ++
• ++ начать

start + 1 - это выражение, значение которого начинается + 1, и оно не увеличивает начало.

начало ++ является выражение, значение которого запускается (не запускается + 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 

Обратите внимание, что start + 1 не меняет start. Вам понадобится код start = start + 1, чтобы изменить его.

В вашем коде вы не заинтересованы в изменении значения начала внутри текущего метода. Вам нужно только передать start + 1 в рекурсию.

Answer 3

Вот та же программа из моей коллекции ...

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--; 
    } 
}