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?

Solution 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.

Solution 2

What you're asking is generating all possible subsets of a set. You can think of it as iterating over all possible binary arrays of size N (the size of your list):

000000...000
000000...001
000000...010
000000...011
etc.

Why is that? The answer is simple: 1 indicates that an element exists in a subset, while 0 indicates that it is absent.

So, the basic algorithm is obvious:

s = [A, B, C, D]

for i=0 to 2^N-1:
   b = convert_number_to_bin_array(i)
   ss = calculate_subset_based_on_bin_array(s, b)
   print ss

Where calculate_subset_based_on_bin_array iterates on b and s and selects elements from s[current] where b[current] = 1.

The above will print out all existing subsets. You can adapt this algorithm in order to get the map that you've asked for in your question.

Solution 3

static Map<Integer, List<LinkedList<Integer>>> powerset = new HashMap<>();

public static void main(String[] args) throws IOException {
    powerset(Arrays.asList(1, 2, 3));
    for (Integer key : powerset.keySet()) {
        System.out.print(key + " -> ");
        System.out.println(Arrays.toString(powerset.get(key).toArray()));
    }
}

static void powerset(List<Integer> src) {
    powerset(new LinkedList<>(), src);
}

private static void powerset(LinkedList<Integer> prefix, List<Integer> src) {
    if (src.size() > 0) {
        prefix = new LinkedList<>(prefix); //create a copy to not modify the orig
        src = new LinkedList<>(src); //copy
        Integer curr = src.remove(0);
        collectResult(prefix, curr);
        powerset(prefix, src);
        prefix.add(curr);
        powerset(prefix, src);
    }
}

private static void collectResult(LinkedList<Integer> prefix, Integer curr) {
    prefix = new LinkedList<>(prefix); //copy
    prefix.add(curr);
    List<LinkedList<Integer>> addTo;
    if (powerset.get(prefix.size()) == null) {
        List<LinkedList<Integer>> newList = new LinkedList<>();
        addTo = newList;
    } else {
        addTo = powerset.get(prefix.size());
    }
    addTo.add(prefix);
    powerset.put(prefix.size(), addTo);
}

OUTPUT

1 -> [[1], [2], [3]]
2 -> [[2, 3], [1, 2], [1, 3]]
3 -> [[1, 2, 3]]

Solution 4

Here is a code I have tested to generate all possible combinations out of given array:

enter code here
import java.util.Arrays;

public class PasswordGen {
static String[] options = { "a", "b", "c", "d" };
static String[] places = new String[options.length];
static int count;

public static void main(String[] args) {
    // Starting with initial position of a i.e. 0
    sequence(0, places.clone());
}

private static void sequence(int level, String[] holder) {
    if (level >= options.length) {
        // combination complete
        System.out.println("" + (++count) + " Combination "
                + Arrays.toString(holder));
        return;
    }

    String val = options[level];
    String[] inrHolder = null;
    for (int c = 0; c < holder.length; c++) {
        inrHolder = holder.clone();
        if (inrHolder[c] == null) {
            inrHolder[c] = val;
            sequence(level + 1, inrHolder.clone());
        }
    }
    return;
}
}

Solution 5

public static List<String> getCombinationsLists(List<String> elements)
{
    
    //return list with empty String
    if(elements.size() == 0){
        List<String> allLists = new ArrayList<String>();
        allLists.add("");
        return allLists ;
    }

    String first_ele = elements.remove(0);
    List<String> rest = getCombinationsLists(elements);
    int restsize = rest.size();
    //Mapping the first_ele with each of the rest of the elements.
    for (int i = 0; i < restsize; i++) {
        String ele = first_ele + rest.get(i);
        rest.add(ele);
    }
   
    return   rest;
}

This Power set is one of the exercise in the book SICP "Structure and Interpretation of Computer Programming".Every Programmer should read it.

View more solutions