First off, you need to make sure you understand what causes an OutOfMemoryError (OOME). You make couple of references to spreading the calculations out over time. I may misunderstand what you mean by that but as stated, that won't make any difference in this situation.
OOMEs are the result of 1. the JVM not having a free contiguous block of space large enough to store a new object after releasing all garbage and compacting the heap. Time isn't really a factor in this situation. If the memory is reachable, it can't be collected regardless of how long it's been around.
So there are a couple of reasons you might have an issue here. One is that you are trying to create a very large object (which strings allow you to do) and there's no free block of heap large enough to accommodate it. The other reason would be that you've filled up the heap with objects that aren't collectable because you are still referencing them.
In this case, I think the issue is that you are putting all of the strings into an arraylist so they can't be collected before the end of the execution of the method. It's worth noting that substr actually creates a new string that refernces the original string's character array and therefore won't allow it to be collected. This can be an issue if you want to pull a small bit of text out of a large String and discard the rest. I don't think it's an issue here but good to know all the same.
The most efficient way to reduce memory is to create your own Collection class and generate each permutation as the iterator is called. This would eliminate the need to store all the permutations in memory at the same time. If I get a minute, I will post some example code.
Edit: I worked up an example without changing the fundamental structure of your algorithm. It should run in a normal JVM for larger inputs than you'll ever want to wait to finish. Essentially by putting all the results into an Arraylist, your memory consumption grows a factorial rate with respect to your input string length. By eliminating the storage of the results, the below approach has memory usage that grows linearly with respect to the input string length.
This is not perfect and there are some problems that I am leaving to the reader to solve. Hint: what happens if you create a Permutor with an empty String?
As someone mentioned StringBuffer is not the best choice here but you'd probably do even better using substring and concat something like so:
current.substring(0, position).concat(last).concat(current.substring(position));
Example:
public class Example
{
public static void main(String... args) {
Permutor p = new Permutor("abcdefghijklmnopqrstuvwxyz");
System.out.println(p.size());
int i = 0;
for (String s : p) {
System.out.println(i++ + ": " + s);
}
}
public static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
public static class Permutor extends AbstractCollection<String>
{
private String characters;
public Permutor(String s)
{
characters = s;
}
@Override
public Iterator<String> iterator()
{
if (characters.length() == 1) {
return Collections.singleton(characters).iterator();
} else {
return new PermutingIterator(characters);
}
}
@Override
public int size()
{
return factorial(characters.length());
}
}
private static class PermutingIterator implements Iterator<String>
{
private final char last;
private final Iterator<String> inner;
private String current;
private int position;
PermutingIterator(String s)
{
int lastIndex = s.length() - 1;
this.inner = new Permutor(s.substring(0, lastIndex)).iterator();
this.last = s.charAt(lastIndex);
}
@Override
public boolean hasNext()
{
return inner.hasNext() || (current != null && position <= current.length());
}
@Override
public String next()
{
while(true) {
if (current != null && position <= current.length()) {
return new StringBuffer(current).insert(position++, last).toString();
} else if (inner.hasNext()) {
position = 0;
current = inner.next();
} else {
throw new IllegalStateException("no more permutations available");
}
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
}
}
