public class ParallelPermutations {
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};

ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);

for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());

System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}

private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();

public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}

private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}

public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));

Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();

String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}

private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}

/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}

/** the word this task is working on*/
public String getWord() {
return word;
}

/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}

/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}

/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}

final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}

/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;

/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}