智能方式生成排列和String的组合

String database[] = {'a', 'b', 'c'}; 

我想基于给定的database生成以下字符串序列。

 a b c aa ab ac ba bb bc ca cb cc aaa ... 

我只能想到一个非常“虚拟”的解决方案。

 public class JavaApplication21 { /** * @param args the command line arguments */ public static void main(String[] args) { char[] database = {'a', 'b', 'c'}; String query = "a"; StringBuilder query_sb = new StringBuilder(query); for (int a = 0; a < database.length; a++) { query_sb.setCharAt(0, database[a]); query = query_sb.toString(); System.out.println(query); } query = "aa"; query_sb = new StringBuilder(query); for (int a = 0; a < database.length; a++) { query_sb.setCharAt(0, database[a]); for (int b = 0; b < database.length; b++) { query_sb.setCharAt(1, database[b]); query = query_sb.toString(); System.out.println(query); } } query = "aaa"; query_sb = new StringBuilder(query); for (int a = 0; a < database.length; a++) { query_sb.setCharAt(0, database[a]); for (int b = 0; b < database.length; b++) { query_sb.setCharAt(1, database[b]); for (int c = 0; c < database.length; c++) { query_sb.setCharAt(2, database[c]); query = query_sb.toString(); System.out.println(query); } } } } } 

解决方案非常愚蠢。 它在某种意义上是不可扩展的

1. 如果我增加database的大小怎么办？
2. 如果我的最终目标打印字符串长度需要为N，该怎么办？

是否有任何智能代码，可以以非常智能的方式生成可扩展的排列和组合字符串？

Answer 1

您应该检查以下答案： 获取包含Java中重复字符的字符串或组合的所有可能排列

要获得此代码：

 public static String[] getAllLists(String[] elements, int lengthOfList) { //initialize our returned list with the number of elements calculated above String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)]; //lists of length 1 are just the original elements if(lengthOfList == 1) return elements; else { //the recursion--get all lists of length 3, length 2, all the way up to 1 String[] allSublists = getAllLists(elements, lengthOfList - 1); //append the sublists to each element int arrayIndex = 0; for(int i = 0; i < elements.length; i++){ for(int j = 0; j < allSublists.length; j++){ //add the newly appended combination to the list allLists[arrayIndex] = elements[i] + allSublists[j]; arrayIndex++; } } return allLists; } } public static void main(String[] args){ String[] database = {"a","b","c"}; for(int i=1; i<=database.length; i++){ String[] result = getAllLists(database, i); for(int j=0; j 

虽然可以进一步改进内存，但由于此解决方案首先生成所有内存解决方案（arrays），然后才能打印它。 但这个想法是一样的，即使用递归算法。

Answer 2

这有点像二进制计数：

• 001
• 010
• 011
• 100
• 101
• …

我的第一直觉是使用二进制计数器作为字符的“位图”来生成可能的值。 但是，这里有一些关于相关问题的精彩答案建议使用递归。 看到

• 如何使这种组合/置换方法递归？
• 找出所有组合和排列 – Java
• java字符串排列和组合查找
• http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

Answer 3

你的置换生成器的Java实现： –

 public class Permutations { public static void permGen(char[] s,int i,int k,char[] buff) { if(i 

Answer 4

好的，所以排列的最佳解决方案是递归。 假设你在字符串中有n个不同的字母。 这会产生n个子问题，每个问题从每个唯一字母开始。 创建一个方法permutationsWithPrefix(String thePrefix, String theString) ，它将解决这些个别问题。 创建另一个方法listPermutations(String theString)实现就像

 void permutationsWithPrefix(String thePrefix, String theString) { if ( !theString.length ) println(thePrefix + theString); for(int i = 0; i < theString.length; i ++ ) { char c = theString.charAt(i); String workingOn = theString.subString(0, i) + theString.subString(i+1); permutationsWithPrefix(prefix + c, workingOn); } } void listPermutations(String theString) { permutationsWithPrefix("", theString); } 

Answer 5

我把这个问题作为面试问题之一。 以下是我使用递归实现此问题的解决方案。

 public class PasswordCracker { private List doComputations(String inputString) { List totalList = new ArrayList(); for (int i = 1; i <= inputString.length(); i++) { totalList.addAll(getCombinationsPerLength(inputString, i)); } return totalList; } private ArrayList getCombinationsPerLength( String inputString, int i) { ArrayList combinations = new ArrayList(); if (i == 1) { char [] charArray = inputString.toCharArray(); for (int j = 0; j < charArray.length; j++) { combinations.add(((Character)charArray[j]).toString()); } return combinations; } for (int j = 0; j < inputString.length(); j++) { ArrayList combs = getCombinationsPerLength(inputString, i-1); for (String string : combs) { combinations.add(inputString.charAt(j) + string); } } return combinations; } public static void main(String args[]) { String testString = "abc"; PasswordCracker crackerTest = new PasswordCracker(); System.out.println(crackerTest.doComputations(testString)); } } 

Answer 6

对于任何寻找非递归选项的人来说，这里有一个数字排列的样本（可以很容易地适应numberOfAgents是列数，数字集是0到numberOfActions ：

  int numberOfAgents=5; int numberOfActions = 8; byte[][]combinations = new byte[(int)Math.pow(numberOfActions,numberOfAgents)][numberOfAgents]; // do each column separately for (byte j = 0; j < numberOfAgents; j++) { // for this column, repeat each option in the set 'reps' times int reps = (int) Math.pow(numberOfActions, j); // for each column, repeat the whole set of options until we reach the end int counter=0; while(counter 

Answer 7

 // IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!! import java.util.*; public class Permutation { public static void main(String[] args) { Scanner in=new Scanner(System.in); System.out.println("ENTER A STRING"); Set se=find(in.nextLine()); System.out.println((se)); } public static Set find(String s) { Set ss=new HashSet(); if(s==null) { return null; } if(s.length()==0) { ss.add(""); } else { char c=s.charAt(0); String st=s.substring(1); Set qq=find(st); for(String str:qq) { for(int i=0;i<=str.length();i++) { ss.add(comb(str,c,i)); } } } return ss; } public static String comb(String s,char c,int i) { String start=s.substring(0,i); String end=s.substring(i); return start+c+end; } } // IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!