All possible combinations and subsets of an array in java

Question

Given an array of variable dimensions.... E.g. array={1,2,4,5}

I need a way to generale all possible combinations and subset of the array.

Given an array of n elements I need to have all subsets (all subsets of 1 element, all subset of 2 elements, all subset of n elements) an of each subset all possible permutations.

For example result should be:

{1}
{2}
{4}
{5}
{1,2}
{1,4}
{1,5}
{2,1}
{2,4}
{2,5}
....
....
{1,2,4,5}
{1,2,5,4}
{1,4,2,5}
{1,5,2,4}
{1,5,4,2}
{2,1,4,5}
{2,1,5,4}
....
....
{5,1,4,2}
{5,1,2,4}
{5,2,4,1}
....
....
etc...

ALL combination!

Is there a quick way? I don't have idea....

Answer 1

You should apply 2 steps:

1. You need to find all subsets of the given input. This set of subsets is called the Power Set.
2. For each element of this power set (that is, for each subset), you need all Permutations.

This implementation uses some utility classes from a combinatorics project. The output also contains the empty set {} and is not ordered by the size, but this may easily be done as a postprocessing step.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class AllCombinations {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1,2,4,5);

        PowerSetIterable<Integer> powerSet = 
            new PowerSetIterable<Integer>(list);
        for (List<Integer> subset : powerSet)
        {
            PermutationIterable<Integer> permutations = 
                new PermutationIterable<Integer>(subset);
            for (List<Integer> permutation : permutations) {
                System.out.println(permutation);
            }
        }

    }
}

//From https://github.com/javagl/Combinatorics
class PowerSetIterable<T> implements Iterable<List<T>> {
    private final List<T> input;
    private final int numElements;
    public PowerSetIterable(List<T> input) {
        this.input = input;
        numElements = 1 << input.size();
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new Iterator<List<T>>() {
            private int current = 0;

            @Override
            public boolean hasNext() {
                return current < numElements;
            }

            @Override
            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("No more elements");
                }
                List<T> element = new ArrayList<T>();
                for (int i = 0; i < input.size(); i++) {
                    long b = 1 << i;
                    if ((current & b) != 0) {
                        element.add(input.get(i));
                    }
                }
                current++;
                return element;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(
                        "May not remove elements from a power set");
            }
        };
    }
}
//From https://github.com/javagl/Combinatorics
class PermutationIterable<T> implements Iterable<List<T>> {
    public static int factorial(int n) {
        int f = 1;
        for (int i = 2; i <= n; i++) {
            f = f * i;
        }
        return f;
    }
    private final List<T> input;
    private final int numPermutations;
    public PermutationIterable(List<T> input) {
        this.input = input;
        numPermutations = factorial(input.size());
    }

    @Override
    public Iterator<List<T>> iterator() {
        if (input.size() == 0) {
            return Collections.<List<T>> singletonList(
                    Collections.<T> emptyList()).iterator();
        }
        return new Iterator<List<T>>() {
            private int current = 0;

            @Override
            public boolean hasNext() {
                return current < numPermutations;
            }

            @Override
            public List<T> next() {
                if (!hasNext()) {
                    throw new NoSuchElementException("No more elements");
                }
                // Adapted from http://en.wikipedia.org/wiki/Permutation
                List<T> result = new ArrayList<T>(input);
                int factorial = numPermutations / input.size();
                for (int i = 0; i < result.size() - 1; i++) {
                    int tempIndex = (current / factorial) % (result.size() - i);
                    T temp = result.get(i + tempIndex);
                    for (int j = i + tempIndex; j > i; j--) {
                        result.set(j, result.get(j - 1));
                    }
                    result.set(i, temp);
                    factorial /= (result.size() - (i + 1));
                }
                current++;
                return result;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(
                        "May not remove elements from a permutation");
            }
        };
    }
}

Answer 2

First, you need to find all the subsets of the array which are 2^n sets (including the empty set). Then once you find the subsets, loop through each of them and compute it permutation using a simple recursion which you can easily find online.

Answer 3

The easiest way I know is to loop over i from 1 to 2^n - 1, where n is the size of the array.

The 1s in the bit pattern of i tell you which elements to select.

e.g: With the array [4, 28, 37, 135] on the 10th loop:

10 == 1010b

1, 0, 1, 0 tells you to select the first and third elements of the array: [4, 37].

Now that you have all combinations of elements in the array, you need to get all permutations, which can be done with some simple recursion.

pseudocode:

function getPermutations(arr)
{
    if length of arr == 1 {
        return [arr]
    } else {
        for i = 0 to highest index of arr {
            sub_arr = copy of arr
            remove element i from sub_arr
            perms = getPermutations(sub_arr)

            for each perm in perms {
                insert arr[i] at beginning of perm
            }
            return perms 
        }
    }
}

Answer 4

I'm providing the first solution it came to my mind for finding all subsets given a List (not the permutations, only the subsets). The method subSets gives all subsets of a specific size, while allSubSets iterates over the sizes. Once you have a list of all subsets, you can implement a permutation function that iterates over this list.

public class Subsets<T> {
    public List<List<T>> allSubSets(List<T> list) {
        List<List<T>> out = new ArrayList<List<T>>();
        for(int i=1; i<=list.size(); i++) {
            List<List<T>> outAux = this.subSets(list, i);
            out.addAll(outAux);
        }
        return out;
    }

    private List<List<T>> subSets(List<T> list, int size) {
        List<List<T>> out = new ArrayList<List<T>>();
        for(int i=0; i<list.size()-size+1;i++) {
            List<T> subset = new ArrayList<T>();
            for (int j=i;j<i+size-1;j++) {
                subset.add(list.get(j));
            }
            if (!(size==1 && i>0)) {
                for (int j=i+size-1;j<list.size();j++) {
                    List<T> newsubset = new ArrayList<T>(subset);
                    newsubset.add(list.get(j));
                    out.add(newsubset);
                }
            }
        }
        return out;
    }
}

To use it:

Subsets<Integer> aux = new Subsets<Integer>();
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
List<List<Integer>> out = aux.allSubSets(list);
System.out.println(out);