Thread: Permutations using Arraylist

I'm having problem with not outputting the correct result. I only get the original permutation back. It doesn't want to iterate through the rest of the letters.

Question is, I'm following the string implementation of finding permutations but I've edited it using arraylist. Now since Strings are immutable, is that the cause of my problem when using Arraylist?

	public BinaryTree optimize2() {	
 
		ArrayList<String> growing = new ArrayList();
		optimize(growing, this.keys);
 
		return null;
 
	}	
 
 
	public static void optimize2(ArrayList<String> growing, ArrayList<String> remaining){
 
		//System.out.println(growing);
		//System.out.println(remaining);
 
		if(remaining.size() == 0)	System.out.println("base" +growing);
 
		else{	
		//remaining.remove(0);
		//optimize(growing,remaining);
 
		for(int i  = 0 ; i < remaining.size(); i++){
			growing.add(remaining.get(i));
			System.out.print("growing" + growing);
 
			remaining.remove(remaining.indexOf(remaining.get(i)));
			System.out.println("remaining" + remaining);
			optimize2( growing, remaining );
 
		}
		}
 
	}

OUTPUT with A,B,C:

growing[A]remaining[B, C]
growing[A, B]remaining[C]
growing[A, B, C]remaining[]
base[A, B, C]

Thanks

The first problem is that you operate on only two Arraylists. Both exist on the heap and not - like you may think - on the stack of the recursive calls. So after the the first three calls the remaining is empty and in the first loop remaining.size() returns zero and the loop ends. So you must create two new arraylist with a copy constructor.
But even if you do so, the second problem is that you remove an object of your remaining while iterating over it. Your loop doesnt work correctly so. Try it with a java-for-each and you will raise an exception because it's not allowed.
Maybe you try it in a way like this:

	public static void main(String[] args) {
		Set<String> set = new HashSet<>(keys);
		printPerm(new ArrayList<String>(), set);
	}
 
	static <T> void printPerm(List<T> stack, Set<T> rest) {
		if (rest.isEmpty())
			System.out.println(stack);
		else
			for (T element : rest) {
				stack.add(element);
				Set<T> restCopy = new HashSet<>(rest);
				restCopy.remove(element);
				printPerm(stack, restCopy);
				stack.remove(element);
			}
	}