рекурсивно получить комбинации слов

Question

Я боролся с этим в течение нескольких дней, и я не могу показаться закончить его. Вопрос заключается в следующем:

Напишите рекурсивный метод String [] perm (int n), который принимает один аргумент: Integer n. Метод возвращает массив всех слов с ровно n слогами. Слова, доступные для использования являются: «Foo» и «Бар»

У меня есть следующий код без рекурсии:

static String[] words = {"Foo","Bar"}; 
static int  n  = 2; 
static int  count = 0; 

public static String[] perm(int n) { 
    String[] wordsArray = new String[4]; 

    for(int i = 0; i < words.length; i++) { 
     for(int j = 0; j < words.length; j++) { 
      wordsArray[count] = words[i] + words[j]; 
      count++; 
     } 
    } 

    return wordsArray; 
} 

Я не могу показаться, чтобы получить следующие результаты, используя рекурсию и возвращение строка Array вдоль пути. Так что я был интересно, можете ли вы мне помочь.

Следующие должны быть результаты с 2-х слогов:

FooFoo 
FooBar 
BarFoo 
BarBar 

Answer 1

Вот первоначальный подход, пожалуйста, измените его в соответствие с вашими потребностями ...

public static void permutationForAString(String str) { 
    permutation("", str); 
} 

private static void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0) System.out.println(prefix); 
    else { 
     for (int i = 0; i < n; i++) 
      permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
    } 
} 

Примечание это не считает повторение ...

permutationForAString("ABC"); 

даст выход в

ABC 
ACB 
BAC 
BCA 
CAB 
CBA 

Answer 2

Это то, что работает по мере необходимости.

public List<String> permute(String[] stringInput, int curr) 
    { 
    List<String> permutations = new ArrayList<String>(); 
    if (curr >= stringInput.length-1) 
    { 
     return Arrays.asList(stringInput); 
    } 
    else 
    { 
     for (int i = 0; i < stringInput.length; i++) 
     { 
     String currentCharacter = stringInput[i]; 
     List<String> permutationsOutput = permute(stringInput,curr+1); 
     for (String singlePermutation : permutationsOutput) 
     { 
      String currentPermutations = currentCharacter + singlePermutation; 
      permutations.add(currentPermutations); 
     } 
     } 
     return permutations; 
    } 
    } 

Вызов его как этот

permute(arr, 0); 

где 0 является индекс начала, с которого начинается перестановкой будет также выступать в качестве предельного состояния в случае рекурсии.

Выход ::

FooFoo 
FooBar 
BarFoo 
BarBar