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.
