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

• raptortech97: You're not going to be able to make this that much more efficient, and if you're having trouble with it being too long it's probably because you're creating a long list. Could you use an Iterator in this situation?
• Joeblade: In your interface, try to return List<...> rather than ArrayList<...> so you don't get pinned down on specific types. (say you want to switch to ConcurrentOnWriteArrayList, the concurrent version of array list) then you don't want to have to change your implementation. not saying this is a strong example but it's good practice to return the interface, not the implementation

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.

• Joeblade: Actually just realised this is codereview. This might not be the best place to post other implementations, rather should've helped you improve yours :) still, recursion with large sets can use up a lot of memory. I'll see tomorrow if you don't have a good answer if I can make a recommendation on your recursive method. my rule of thumb is "leave as little on the stack as possible, construct as few objects as you can" to make the stackframes smaller. StackOverflow is always a risk when the number of elements goes up.
• 200_success: Posting an alternative implementation is fine, since you have made some remarks about the original code, stated a reason for taking a different approach, and even tried to compare the performance. That makes a fine Code Review answer.
• user1418018: Thank you for your input, I appreciate it. nrElements isn't the same as elements.length in this case.
• Joeblade: Yeah sorry about that, I noticed when I was writing my version of this, that there's a difference. oh well hope this helped

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