Multithreaded String Permutations
This code snippet is designed to take in a string an print out every possible permutation of that string. The only problem I’ve encountered so far is that it uses a lot of memory with longer strings.
package com.syfran.Permut;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class Permutations {
public static void main(String[] pie) {
String input = "";
// if there are no arguments, prompt the user
if (pie.length > 0) {
// Get all the arguments, gets rid of the need for pesky quotes
for (String temp : pie)
input += " " + temp;
} else {
System.out.println("Please enter String: ");
input = (new Scanner(System.in).nextLine());
}
Permutations p = new Permutations();
p.begin(input);
}
public void begin(final String myString) {
// Number of threads, probably best to set it just over the number of
// cores you have
final int THREADS = 4;
// Create a thread safe queue, add initialize it with a blank string.
Stack<String> myStack = new Stack<String>();
myStack.push("");
// Used to execute the threads
ExecutorService ex = Executors.newFixedThreadPool(THREADS);
Runnable myRunnable = new PermutWorker(myStack, myString);
// make sure there is enough in the queue so that it doesn't end early
final int SEED = 2;
for (int x = 0; x < SEED; x++)
seedQueue(myRunnable, ex);
// continue to execute the worker
try {
while (true) {
ex.execute(myRunnable);
}
} catch (EmptyStackException e) {
}
// shutdown the executor
ex.shutdown();
}
private void seedQueue(Runnable run, ExecutorService ex) {
ex.execute(run);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// give up / sad panda
return;
}
}
// Main content of the thread
private class PermutWorker implements Runnable {
private Stack<String> stack;
private final String original;
PermutWorker(Stack<String> myStack, final String original) {
this.stack = myStack;
this.original = original;
}
@Override
public void run() {
String current = null;
try {
// get the current state of permutations from the queue
current = stack.pop();
}
// if we get null then wait for awhile then try again
catch (EmptyStackException ex) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
return;
}
try {
current = stack.pop();
} catch (EmptyStackException e) {
return;
}
}
// create List of current characters
List<Character> currentList = new ArrayList<Character>();
for (Character c : current.toCharArray())
currentList.add(c);
// create list of characters in original
List<Character> remaining = new ArrayList<Character>();
for (Character c : original.toCharArray())
remaining.add(c);
// remove current from the original to get the remaining
for (Character c : currentList)
remaining.remove(c);
// for every remaining character, add it to current
// if it is the same length as the original then print it
// else add it to the queue
for (Character c : remaining) {
String result = current + c;
if (result.length() == original.length()) {
// change this as needed
System.out.println(result);
} else {
stack.push(result);
}
}
}
}
}
UPDATE: Replaced the queue with a stack to try to help with the memory problem. It will still get outofMemory errors on longer strings but it can handle a bit more. The stack should focus on the longest strings first and get them (hopefully if the GC does its job) out of the memory quickly.
