Optimizing String combinations in Java

Question

I need to obtain all combinations of a String of length k from the 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;
}

Answer 1

In the wild I don't find much recursion, it seems mostly used during exercises. I'm assuming this is one as well. Just hope you already handed it in.

one pointer for you, you are passing nrElements. Is this the same as elements.length? you might be able to remove it altogether from the interface of your methods. Second pointer: your printAllKLengthRec returns an array , but it also updates the (same) array passed into it as an input argument. you can remove the return value completely. It is not needed. trust that the method will update the array you pass as input.

the way I would solve this myself would be something like:

public List<String> getStrings(char[] chars, int k) {
    int[] indexes = new int[k]; // prefills with 0
    List<String> result = new ArrayList<String>();
    boolean done = false;

    while (!done) { // stopcondition is inside the loop
        // construct 1 string with current indexes
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < k; ++i) {
            buffer.append(chars[indexes[i]]);
        }
        result.add(buffer.toString());

        indexes[0]++;

        for (int i = 0; i < k; ++i) {
            if (indexes[i] == chars.length) { // overflow should go into i+1, set this index back to 0
                if (i + 1 == k) {
                    // loop done. would overflow.
                    done = true;
                    break;
                } else {
                    indexes[i] = 0;
                    indexes[i + 1]++;
                }
            }
        }
    }

    return result;
}

It is more lines, but it's nonrecursive which might make things a bit more manageable. For one you can split subparts into a separate method (for instance the indexes could become a class of it's own) and reuse it for other methods that need the same. I find recursion really only fixes it's one issue, but can't easily be reused for other things. Unless you write a good datastructure around it, like tree lookups and such.

just measured, my implementation was faster 3 times out of 4, but :) that's the problem with measuring using System.nanotime. All sorts of stuff can happen during execution to make the result not untrustworthy.

Answer 2

Perhaps there should be a preprocessing step to remove duplicates from elements[ ] so that {'a', 'a'}, k=2 yields [aa] and not [aa, aa, aa, aa].