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

[b1707107]

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?

[JosAH]

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

[b1707107]

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:

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?

[JosAH]

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

[b1707107]

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

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.

[JosAH]

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

                if (s.charAt(j) == new String("1").charAt(0))

change that to:

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:

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.