How to find powerset of an ArrayList of pairs: ArrayList> pairList

Question

public static void generatePowerSet(ArrayList<Pair<Integer,Integer>> pairList, int n_items) {
    Deque<Integer> set = new ArrayDeque<>();
    
    if (n_items == 0) {
        System.out.println(set);
        return;
    }
    Object[] pair_array = pairList.toArray();
    // consider the n'th element
    set.addLast((Integer) pair_array[n_items - 1]);
    generatePowerSet(pairList, n_items - 1);

    // or don't consider the n'th element
    set.removeLast();
    generatePowerSet(pairList, n_items - 1);
   
    System.out.println(set);
}

I'm having trouble finding documentation that will allow me to do this, so far I have this function to generate a powerset with inputs (pairList, int n_items)

n_items is the number of pairs in the ArrayList I tried to change the array list to an array (toArray()) but am having type conversion issues while passing in the arrayList. Is there a better way I can make a power set from this arraylist?

Why do you need `n_items`? The [`ArrayList`](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html) knows its own size, which you can get by calling the conveniently named [`size()`](https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#size--) method. — Andreas, Feb 06 '21 at 20:24

karakfa · Accepted Answer · 2021-02-06T19:59:53.640

Here is a non recursive version for String elements. Convert to work with Pairs.

static class PowerSet implements Iterable<Set<String>> {

    private List<String> values;

    public PowerSet(List<String> values) {
        this.values = values;
    }

    @Override
    public Iterator<Set<String>> iterator() {
        return new Iterator<Set<String>>() {

            int index;
            final int size = (int) Math.pow(2, values.size());

            @Override
            public boolean hasNext() {
                return index < size;
            }

            @Override
            public Set<String> next() {

                BitSet bitSet = BitSet.valueOf(new long[]{index});
                Set<String> elements = new HashSet<>();
                int b = bitSet.nextSetBit(0);
                while (b >= 0) {
                    elements.add(values.get(b));
                    b = bitSet.nextSetBit(b + 1);
                }

                index++;
                return elements;
            }
        };
    }
}

Usage is simple

    List<String> values = Arrays.asList("a", "b", "c");
    PowerSet ps = new PowerSet(values);
    for(Set<String> e : ps) System.out.println(e);

will return

[]
[a]
[b]
[a, b]
[c]
[a, c]
[b, c]
[a, b, c]

How to find powerset of an ArrayList of pairs: ArrayList> pairList

1 Answers1