all sub-sets of a set in java

I was offered the challenge to find all the sub-sets of a set, represented as an ordered list, using java.

I know a list isn't really a set, but it is the same idea in the end, since the elements are not repeated, also the non-recursive implementation I came up with would work equally well with sets as lists.

I started with a recursive implementation, and later found a non-recursive implementation with the same output.

First I made some tests to show what was going to happen.

package org.yi.happy.subset;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class FindSubsetsTest {
    @Test
    public void testFindAll() {
        List<Integer> in = Arrays.asList(0,1,2,3);
        
        List<List<Integer>> have = FindSubsets.findAll(in);
        
        List<List<Integer>> want = new ArrayList<List<Integer>>();
        want.add(new ArrayList<Integer>());
        want.add(Arrays.asList(3));
        want.add(Arrays.asList(2));
        want.add(Arrays.asList(2, 3));
        want.add(Arrays.asList(1));
        want.add(Arrays.asList(1, 3));
        want.add(Arrays.asList(1, 2));
        want.add(Arrays.asList(1, 2, 3));
        want.add(Arrays.asList(0));
        want.add(Arrays.asList(0, 3));
        want.add(Arrays.asList(0, 2));
        want.add(Arrays.asList(0, 2, 3));
        want.add(Arrays.asList(0, 1));
        want.add(Arrays.asList(0, 1, 3));
        want.add(Arrays.asList(0, 1, 2));
        want.add(Arrays.asList(0, 1, 2, 3));

        assertEquals(want, have);
    }

    @Test
    public void testFindAllFlat() {
        List<Integer> in = Arrays.asList(0, 1, 2, 3);

        List<List<Integer>> have = FindSubsets.findAllFlat(in);

        List<List<Integer>> want = new ArrayList<List<Integer>>();
        want.add(new ArrayList<Integer>());
        want.add(Arrays.asList(3));
        want.add(Arrays.asList(2));
        want.add(Arrays.asList(2, 3));
        want.add(Arrays.asList(1));
        want.add(Arrays.asList(1, 3));
        want.add(Arrays.asList(1, 2));
        want.add(Arrays.asList(1, 2, 3));
        want.add(Arrays.asList(0));
        want.add(Arrays.asList(0, 3));
        want.add(Arrays.asList(0, 2));
        want.add(Arrays.asList(0, 2, 3));
        want.add(Arrays.asList(0, 1));
        want.add(Arrays.asList(0, 1, 3));
        want.add(Arrays.asList(0, 1, 2));
        want.add(Arrays.asList(0, 1, 2, 3));

        assertEquals(want, have);
    }
}

And the implementation, with implementation notes in it.

package org.yi.happy.subset;

import java.util.ArrayList;
import java.util.List;


public class FindSubsets {

    /**
     * Find all the subsets of in, recursively.
     * 
     * @param <T>
     *            the type of item items in the set.
     * @param in
     *            the set to get subsets off.
     * @return the list of subsets of in. The order is the same as doing binary
     *         counting with the least significant digit on the right.
     */
    public static <T> List<List<T>> findAll(List<T> in) {
        /*
         * we can do this recursively, we either exclude or include the first
         * item, and join all the deeper subsets to it.
         */

        if (in.size() == 0) {
            /*
             * the base case is just the empty set.
             */
            List<List<T>> out = new ArrayList<List<T>>();
            out.add(new ArrayList<T>());
            return out;
        }

        List<List<T>> out = new ArrayList<List<T>>();

        T first = in.get(0);
        List<List<T>> rest = findAll(in.subList(1, in.size()));

        /*
         * first all the sets excluding the first item
         */
        for (List<T> r : rest) {
            out.add(r);
        }

        /*
         * next all the sets including the first item
         */
        for (List<T> r : rest) {
            List<T> s = new ArrayList<T>();
            s.add(first);
            s.addAll(r);
            out.add(s);
        }

        return out;
    }

    /**
     * Find all the subsets of in, non-recursively.
     * 
     * @param <T>
     *            the type of item items in the set.
     * @param in
     *            the set to get subsets off.
     * @return the list of subsets of in.
     */
    public static <T> List<List<T>> findAllFlat(List<T> in) {
        List<List<T>> out = new ArrayList<List<T>>();
        out.add(new ArrayList<T>());

        for (T i : in) {
            List<List<T>> next = new ArrayList<List<T>>();
            for (List<T> j : out) {
                next.add(j);

                List<T> k = new ArrayList<T>(j);
                k.add(i);
                next.add(k);
            }
            out = next;
        }

        return out;
    }

}

It was not much harder than counting binary to make this list, I gave up on adding the restriction where the resulting lists of lists should be sorted.