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

I would like to generate the following strings sequence, based on given database.

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

I can only think of a pretty "dummy" solution.

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

The solution is pretty dumb. It is not scale-able in the sense that

  1. What if I increase the size of database?
  2. What if my final targeted print String length need to be N?

Is there any smart code, which can generate scale-able permutation and combination string in a really smart way?

Improve this question
1
  • In Python, it's very simple, haha. print ''.join(query) for query in itertools.combinations_with_replacement(database, length) for length in range(1,N+1) Commented Nov 15, 2013 at 3:52

7 Answers 7

Reset to default
19

You should check this answer: Getting every possible permutation of a string or combination including repeated characters in Java

To get this code:

public static String[] getAllLists(String[] elements, int lengthOfList) { //lists of length 1 are just the original elements if(lengthOfList == 1) return elements; else { //initialize our returned list with the number of elements calculated above String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)]; //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<result.length; j++){ System.out.println(result[j]); } } }

Although further improvement in memory could be made, since this solution generates all solution to memory first (the array), before we can print it. But the idea is the same, which is to use recursive algorithm.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

A minor comment: allLists initialisation is best moved inside the else (main) case
@almondandapricot Updated!
3

This smells like counting in binary:

  • 001
  • 010
  • 011
  • 100
  • 101
  • ...

My first instinct would be to use a binary counter as a "bitmap" of characters to generate those the possible values. However, there are several wonderful answer to related questions here that suggest using recursion. See

Improve this answer

5 Comments

This would be true but for the fact that aa is a valid permutation.
I think instead of using binary, it can also easily be done using higher bases. since he has three elements it can be done it in base 3
Still not scalable... Next time he has four elements in database. But you are getting closer...
well if he has n elements in his database he can do it in base n
"if he has n elements in his database, he can do it in base n" -> this is exactly what the OP asked. haha
2

Java implementation of your permutation generator:-

public class Permutations { public static void permGen(char[] s,int i,int k,char[] buff) { if(i<k) { for(int j=0;j<s.length;j++) { buff[i] = s[j]; permGen(s,i+1,k,buff); } } else { System.out.println(String.valueOf(buff)); } } public static void main(String[] args) { char[] database = {'a', 'b', 'c'}; char[] buff = new char[database.length]; int k = database.length; for(int i=1;i<=k;i++) { permGen(database,0,i,buff); } } }
Improve this answer

Comments

1

For anyone looking for non-recursive options, here is a sample for numeric permutations (can easily be adapted to char. numberOfAgents is the number of columns and the set of numbers is 0 to 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<combinations.length) { // for each option for (byte i = 0; i < numberOfActions; i++) { // save each option 'reps' times for (int k = 0; k < reps; k++) combinations[counter + i * reps + k][j] = i; } // increase counter by 'reps' times amount of actions counter+=reps*numberOfActions; } } // print for(byte[] setOfActions : combinations) { for (byte b : setOfActions) System.out.print(b); System.out.println(); }
Improve this answer

Comments

0

Ok, so the best solution to permutations is recursion. Say you had n different letters in the string. That would produce n sub problems, one for each set of permutations starting with each unique letter. Create a method permutationsWithPrefix(String thePrefix, String theString) which will solve these individual problems. Create another method listPermutations(String theString) a implementation would be something like 

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); }
Improve this answer

Comments

0

i came across this question as one of the interview question. Following is the solution that i have implemented for this problem using recursion.

public class PasswordCracker { private List<String> doComputations(String inputString) { List<String> totalList = new ArrayList<String>(); for (int i = 1; i <= inputString.length(); i++) { totalList.addAll(getCombinationsPerLength(inputString, i)); } return totalList; } private ArrayList<String> getCombinationsPerLength( String inputString, int i) { ArrayList<String> combinations = new ArrayList<String>(); 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<String> 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)); } }
Improve this answer

Comments

0 
// 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<String> se=find(in.nextLine()); System.out.println((se)); } public static Set<String> find(String s) { Set<String> ss=new HashSet<String>(); if(s==null) { return null; } if(s.length()==0) { ss.add(""); } else { char c=s.charAt(0); String st=s.substring(1); Set<String> 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!!
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.