Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Permutations using Arraylist

  1. #1
    Junior Member
    Join Date
    Jun 2011
    Posts
    29
    Thanks
    11
    Thanked 0 Times in 0 Posts

    Default 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


  2. #2
    Junior Member
    Join Date
    Feb 2013
    Location
    Germany
    Posts
    27
    Thanks
    0
    Thanked 5 Times in 5 Posts

    Default Re: Permutations using Arraylist

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

Similar Threads

  1. Permutations using Arraylist
    By steel55677 in forum Collections and Generics
    Replies: 1
    Last Post: March 14th, 2013, 06:58 PM
  2. Help generating random permutations from array list
    By mactank13 in forum What's Wrong With My Code?
    Replies: 12
    Last Post: December 2nd, 2012, 08:04 PM
  3. permutations of a string using iteration
    By ueg1990 in forum Java Theory & Questions
    Replies: 11
    Last Post: August 11th, 2012, 03:23 PM
  4. Finding all Permutations that add up to a number.
    By godsfearme in forum What's Wrong With My Code?
    Replies: 0
    Last Post: December 28th, 2010, 02:54 PM
  5. [SOLVED] Extracting an How to ArrayList from an ArrayList and convert to int??
    By igniteflow in forum Collections and Generics
    Replies: 2
    Last Post: August 16th, 2009, 01:11 PM