Optimizing String combinations in Java

Question

I need to obtain all combinations of a String of length k from given elements. For example, for

char[] elements = {'a', 'b', 'c'}
k = 4

the output should be: aaaa, aaab, ..., cccc. Now I have the following code which gives proper results BUT isn't fast enough. What can I improve in my code?

public static ArrayList<String> printAllKLength(char[] elements, int nrElements, int patternLength) {
    ArrayList<String> patternVariations = new ArrayList<String>();
    patternVariations = printAllKLengthRec(elements, "", nrElements, patternLength, patternVariations);

    return patternVariations;
}

public static ArrayList<String> printAllKLengthRec(char[] elements, String prefix, int nrElements, int patternLength, ArrayList<String> patternVariations) {

    if (patternLength == 0) {
        patternVariations.add(prefix);
        //System.out.println(prefix);
        return patternVariations;
    }

    for (int i = 0; i < nrElements; ++i) {
        String newPrefix = prefix + elements[i]; 
        printAllKLengthRec(elements, newPrefix, nrElements, patternLength - 1, patternVariations); 
    }
    return patternVariations;
}

Thank you!

This is an algorithms question AND does NOT belong to this forum. You need to ask it in http://cs.stackexchange.com/ — Mohammad Najar, Oct 23 '14 at 19:48
It's not really an algorithm question. I posted it on codereview, thanks @Tom. — user1418018, Oct 23 '14 at 20:00
When you've done that, then delete this question here. It doesn't belong to stackoverflow. — Tom, Oct 23 '14 at 20:01
@Mohammad: Algorithms questions involving actual code are just fine here. ["As a rule of thumb, if your question depends on code, ask on Stack Overflow; if your question calls for mathematical notation, ask on Computer Science. Algorithms expressed in pseudocode straddle the border."](https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-do-i-post-in). But if you've cross-posted to Code Review, then go ahead and delete it here to not leave a duplicate around. — Jeffrey Bosboom, Oct 23 '14 at 20:05

score 0 · Answer 1 · answered Oct 23 '14 at 19:55

0

You can use dynamic programming approach(memorization). Something very similar:

http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

answered Oct 23 '14 at 19:55

Amit Sharma

1,987
2
18
29

score 0 · Accepted Answer · edited May 23 '17 at 12:05

0

Try doing it without recursation ... see the explanation here.

recursion versus iteration

I hope this helps you

edited May 23 '17 at 12:05

Community

1
1

answered Oct 23 '14 at 20:11

carlos effio

71
5

Optimizing String combinations in Java

2 Answers2