How to generate the power-set of a given List?

Question

I'm trying to generate a collection of all 2^N - 1 possible combinations of a given List of length N. The collection will map the number of elements in a combination to an ordered list of combinations containing combinations of the specific length. For instance, for the List:

[A, B, C, D]

I want to generate the map:

{
    1 -> [{A}, {B}, {C}, {D}]
    2 -> [{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}]
    3 -> [{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}]
    4 -> [{A, B, C, D}]
}

The generated database should maintain the original order (where [] represents an ordered series (List), and {} represents an un-ordered group (Set)), and run as fast as possible.

I was struggling with some recursive code all day (I know the implementation should be recursive) but couldn't get to the bottom of it.

Is there a reference I can use/a ready implementation of such algorithm?

Answer 1

What you're looking for is essentially the power set (minus perhaps the empty set). Guava actually has a method for this: Sets.powerSet(). You can view the source of the Sets class to see how the method is implemented if you want to write it yourself; you might need to modify it to return a List instead of a Set since you want to preserve order, although this change should not be too drastic. Once you have the power set, it should be trivial to iterate over it and construct the map you want.