Sunday, February 20, 2011

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>>();

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>>();

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>>();
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) {
}

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

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>>();

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

List<T> k = new ArrayList<T>(j);
}
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.