Results 1 to 6 of 6
  1. #1
    b1707107 is offline Member
    Join Date
    Jan 2013
    Posts
    3
    Rep Power
    0

    Question Loops and recursion: get every permutation of ArrayList elements, order matters

    I have an ArrayList of n number of stuff, and ultimately I need to fill a separate 2D ArrayList with every possible ArrayList combination of the stuff. Order is important. For example, if I have an ArrayList with:

    dog, blue, cat

    In the end, I would like to have:

    dog,
    blue,
    cat,
    dog, blue
    blue, dog
    blue, cat
    cat, blue
    cat, dog
    dog, cat
    dog, blue, cat
    dog, cat, blue
    blue, cat, dog
    blue, dog, cat
    cat, dog, blue
    cat, blue, dog

    The number of stuff in the original ArrayList will change, which is why I'm not sure how to write the code to do what I want. For the above example I could do nested for loops, but this won't generalize to an ArrayList with n elements. I feel like this should be a fairly common problem but I don't know what to search for. How can I generate a 2D ArrayList containing every possible permutation with no repetitions from size 1 to n from the elements in an ArrayList of size n?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default Re: Loops and recursion: get every permutation of ArrayList elements, order matters

    What you want is every permutation of every combination of a set of items, e.g. if the set is { A, B, C }, the combinations are { A, B, C, AB, AC, BC, ABC } and the permutations of each element of this set are: { A, B, C, AB, BA, AC, CA, BC, CB, ABC, ACB, BAC, BCA, CAB, CBA }; you don't need recursion for either the combination or permutation generators.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    b1707107 is offline Member
    Join Date
    Jan 2013
    Posts
    3
    Rep Power
    0

    Default Re: Loops and recursion: get every permutation of ArrayList elements, order matters

    I looked for more information and what I want is technically called a variation without repetition. Unfortunately Googling "arraylist variation" or whatever doesn't work obviously. I found code that produces permutations:

    Java Code:
    import java.util.*;
    
    public class Permutation
    {
    	public static ArrayList<ArrayList<Screener>> permutations(ArrayList<Screener> list)
    	{
    		return permutations(null, list, null);
    	}
    
    	public static ArrayList<ArrayList<Screener>> permutations(ArrayList<Screener> prefix, ArrayList<Screener> suffix, ArrayList<ArrayList<Screener>> output)
    	{
    		if(prefix == null)
    			prefix = new ArrayList<Screener>();
    		if(output == null)
    			output = new ArrayList<ArrayList<Screener>>();
    		
    		if(suffix.size() == 1)
    		{
    			ArrayList<Screener> newElement = new ArrayList<Screener>(prefix);
    			newElement.addAll(suffix);
    			output.add(newElement);
    			return output;
    		}
    		
    		for(int i = 0; i < suffix.size(); i++)
    		{
    			ArrayList<Screener> newPrefix = new ArrayList<Screener>(prefix);
    			newPrefix.add(suffix.get(i));
    			ArrayList<Screener> newSuffix = new ArrayList<Screener>(suffix);
    			newSuffix.remove(i);
    			permutations(newPrefix,newSuffix,output);
    		}
    		
    		return output;
    	}
    }
    (Screener is my class, ctrl+f replace with whatever.) Now I need to find combinations of sizes 1 through n from an ArrayList of size n. The above code runs itself to calculate the permutations -- I don't understand how I can get combinations of any size without using recursion or writing out nested for loops. How do I form combinations from ArrayList elements of any size less than the size of the ArrayList?

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default Re: Loops and recursion: get every permutation of ArrayList elements, order matters

    Combinations of elements of a set is a simple including an element in the result or not; think of 'including it' as 1 and 'not including it' as 0; for a set of n elements, you just have to enumerate all possible sequences of 0s and 1s of length n; example: S= { A, B, C }; enumeration = 000, 001, 010, 011, 100, 101, 110, 111 }; so the result is { -, C, B, BC, A, AC, AB, ABC }; as you can see from the enumeration, it's just counting in binary.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    b1707107 is offline Member
    Join Date
    Jan 2013
    Posts
    3
    Rep Power
    0

    Default Re: Loops and recursion: get every permutation of ArrayList elements, order matters

    I got it! Here's some parts from the code for combinations, it's probably terrible and unoptimized but I don't care:

    Java Code:
    public static ArrayList<ArrayList<Object>> comb(ArrayList<Object> in)
    	{
    		ArrayList<ArrayList<Object>> out = new ArrayList<ArrayList<Object>>();
    		
    		for (int i = 0; i < Math.pow(2, in.size()); i ++)
    		{
    			ArrayList<Object> thing = new ArrayList<Object>();
    			
    			String t = Integer.toBinaryString(i);
    			
    			String zeroes = new String();
    			for (int o = 0; o < in.size(); o ++)
    			{
    				zeroes = zeroes + "0";
    			}
    			
    			DecimalFormat df = new DecimalFormat(zeroes);
    			
    			String s = df.format(Integer.parseInt(t));
    			
    			for (int j = 0; j < s.length(); j ++)
    			{
    				if (s.charAt(j) == new String("1").charAt(0))
    				{
    					thing.add(in.get(j));
    					System.out.println(in.get(j).getName() + " added");
    				}
    				else
    				{
    					
    				}
    			}
    			
    			out.add(thing);
    		}
    		
    		for (int i = 0; i < out.size(); i ++)
    		{
    			ArrayList<ArrayList<Object>> permsOfOne = permutations(out.get(i));
    			
    			for (int j = 0; j <permsOfOne.size(); j ++)
    			{
    				for (int d = 0; d <permsOfOne.get(j).size(); d ++)
    				{
    					System.out.print(permsOfOne.get(j).get(d).getName() + ", ");
    				}
    				
    				Strategy coolStrat = new Strategy(permsOfOne.get(j));
    				System.out.print("Sensitivity is:" + coolStrat.getSens() + " Specificity is:" + coolStrat.getSpec() + " Cost is: " + coolStrat.getCost());
    				
    				System.out.println("END");
    			}
    		}
    		
    		return out;
    	}
        
        public static ArrayList<ArrayList<Object>> permutations(ArrayList<Object> list)
    	{
    		return permutations(null, list, null);
    	}
        
        public static ArrayList<ArrayList<Object>> permutations(ArrayList<Object> prefix, ArrayList<Object> suffix, ArrayList<ArrayList<Object>> output)
    	{
    		if(prefix == null)
    			prefix = new ArrayList<Object>();
    		if(output == null)
    			output = new ArrayList<ArrayList<Object>>();
    		
    		if(suffix.size() == 1)
    		{
    			ArrayList<Object> newElement = new ArrayList<Object>(prefix);
    			newElement.addAll(suffix);
    			output.add(newElement);
    			return output;
    		}
    		
    		for(int i = 0; i < suffix.size(); i++)
    		{
    			ArrayList<Object> newPrefix = new ArrayList<Object>(prefix);
    			newPrefix.add(suffix.get(i));
    			ArrayList<Object> newSuffix = new ArrayList<Object>(suffix);
    			newSuffix.remove(i);
    			permutations(newPrefix,newSuffix,output);
    		}
    		
    		return output;
    	}
    I think it calls the permutation function I posted above. Anyway, thanks for the help! And I can't believe there isn't already some library that does this for you.
    Last edited by b1707107; 01-22-2013 at 06:20 PM.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,433
    Blog Entries
    7
    Rep Power
    20

    Default Re: Loops and recursion: get every permutation of ArrayList elements, order matters

    I'm glad you have it working; one little nitpick; your line #23 is terrible:

    Java Code:
                    if (s.charAt(j) == new String("1").charAt(0))
    change that to:

    Java Code:
    if (s.charAt(j) == '1')
    kind regards,

    Jos

    ps. I found an old algorithm implementation of mine; it generates all those combinations. Here it is:

    Java Code:
    import java.util.Arrays;
    
    public class Combination {
    
    	public static boolean combine(int[] c, int n) {
    	
    		for (int i= c.length; --i >= 0;) {
    			if (++c[i] <= n-(c.length-i)) {
    				for (; ++i < c.length; )
    					c[i]= c[i-1]+1;
    				return true;
    			}
    		}
    		return false;
    	}
    
    	public static void main(String[] args) {
    		
    		int N= 5;
    	
    		for (int n= 1; n <= N; n++) {
    			int[] a= new int[n];
    			for (int i= 0; i < a.length; i++) a[i]= i;
    		
    			do {
    				System.out.println(Arrays.toString(a));
    			}
    			while (combine(a, N));
    		}
    	}
    }
    Given each combination you have to generate all its permutations and voila.
    Last edited by JosAH; 01-22-2013 at 08:13 PM.
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Replies: 2
    Last Post: 08-30-2012, 12:01 PM
  2. show elements in correct order
    By Shien in forum New To Java
    Replies: 4
    Last Post: 12-30-2011, 05:20 PM
  3. Recursion with loops
    By Claymz in forum New To Java
    Replies: 11
    Last Post: 06-01-2011, 08:30 PM
  4. N while loops into recursion
    By Claymz in forum New To Java
    Replies: 1
    Last Post: 04-17-2011, 03:05 PM
  5. Replies: 9
    Last Post: 02-14-2011, 04:22 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •