java - 排列发生器

Question

我正在尝试将用户的输入添加到我的排列列表中，但是当我接受用户输入时，程序一直在运行。在第三次输入后按回车键时，我没有得到任何排列。这是我的代码:

  import java.util.ArrayList;
  import java.util.Scanner;

 /**
 This program demonstrates the permutation generator.
 */
 public class PermutationGeneratorDemo
 {
 public static void main(String[] args)
 {
   Scanner scan = new Scanner(System.in);

   System.out.println("Please enter a 4 letter word: ");
   String word1 = scan.next();
   System.out.println("Enter a 5 letter word: ");
   String word2 = scan.next();
   System.out.println("Enter a 6 letter word: ");
   String word3 = scan.next();


  PermutationGenerator generator = new PermutationGenerator(word1 + word2 + word3);
  ArrayList<String> permutations = generator.getPermutations();
  for (String s : permutations)
  {         
     System.out.println(s);
    }
   }
  }

排列代码:

import java.util.ArrayList;

/**
This class generates permutations of a word.
*/
 public class PermutationGenerator
 {
  private String word;

 /**
  Constructs a permutation generator.
  @param aWord the word to permute
 */
 public PermutationGenerator(String aWord)
{
    word = aWord;
}

PermutationGenerator(String[] wordList) {
    throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}

 /**
    Gets all permutations of a given word.
   */
 public ArrayList<String> getPermutations()
 {
  ArrayList<String> permutations = new ArrayList<String>();

  // The empty string has a single permutation: itself
  if (word.length() == 0) 
  { 
     permutations.add(word); 
     return permutations; 
  }

  // Loop through all character positions
  for (int i = 0; i < word.length(); i++)
  {
     // Form a simpler word by removing the ith character
     String shorterWord = word.substring(0, i)
           + word.substring(i + 1);

     // Generate all permutations of the simpler word
     PermutationGenerator shorterPermutationGenerator 
           = new PermutationGenerator(shorterWord);
     ArrayList<String> shorterWordPermutations 
           = shorterPermutationGenerator.getPermutations();

     // Add the removed character to the front of
     // each permutation of the simpler word, 
     for (String s : shorterWordPermutations)
     {
        permutations.add(word.charAt(i) + s);
     }
  }
  // Return all permutations
  return permutations;
 }
}

Answer 1

之前我认为问题出在无限递归上，但经过进一步检查后，您的程序确实终止了。但是，您必须意识到生成排列列表是阶乘复杂性。 4+5+6 = 15. 15!是一个非常大的数，1.3076744e+12从谷歌计算器，这就是为什么你的程序似乎永远不会结束。

生成那么多字符串需要一段时间。

尝试使用输入 a、b 和 c 运行程序，您会发现它可以工作，因为它只需要生成3! = 6 个字符串。