Cheok Yan Cheng Cheok Yan Cheng - 2 months ago 7
Java Question

Smart way to generate permutation and combination of String

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?

Answer

You should check this answer: every possible permutation of a string or combination including repeated character use java

To get this code:

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<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.

Comments