Results 1 to 6 of 6
 01212013, 03:05 AM #1Member
 Join Date
 Jan 2013
 Posts
 3
 Rep Power
 0
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?
 01212013, 07:26 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 01212013, 06:09 PM #3Member
 Join Date
 Jan 2013
 Posts
 3
 Rep Power
 0
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; } }
 01212013, 07:03 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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,
Joscenosillicaphobia: the fear for an empty beer glass
 01222013, 06:14 PM #5Member
 Join Date
 Jan 2013
 Posts
 3
 Rep Power
 0
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; }
Last edited by b1707107; 01222013 at 06:20 PM.
 01222013, 07:13 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,010
 Blog Entries
 7
 Rep Power
 20
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))
Java Code:if (s.charAt(j) == '1')
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.lengthi)) { for (; ++i < c.length; ) c[i]= c[i1]+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)); } } }
Last edited by JosAH; 01222013 at 08:13 PM.
cenosillicaphobia: the fear for an empty beer glass
Similar Threads

JAXB  Reading elements in same order as defined in xml.
By rvikasr in forum XMLReplies: 2Last Post: 08302012, 12:01 PM 
show elements in correct order
By Shien in forum New To JavaReplies: 4Last Post: 12302011, 05:20 PM 
Recursion with loops
By Claymz in forum New To JavaReplies: 11Last Post: 06012011, 08:30 PM 
N while loops into recursion
By Claymz in forum New To JavaReplies: 1Last Post: 04172011, 03:05 PM 
Manipulating array elements to zero using forloops and ifstatements in Java
By paulmmj in forum New To JavaReplies: 9Last Post: 02142011, 04:22 AM
Bookmarks