Find N-Th Set of a Powerset

Find n-th set of a powerset

I don't have a closed form for the function, but I do have a bit-hacking non-looping next_combination function, which you're welcome to, if it helps. It assumes that you can fit the bit mask into some integer type, which is probably not an unreasonable assumption given that there are 2⁶⁴ possibilities for the 64-element set.

As the comment says, I find this definition of "lexicographical ordering" a bit odd, since I'd say lexicographical ordering would be: [], [a], [ab], [abc], [ac], [b], [bc], [c]. But I've had to do the "first by size, then lexicographical" enumeration before.

// Generate bitmaps representing all subsets of a set of k elements,
// in order first by (ascending) subset size, and then lexicographically.
// The elements correspond to the bits in increasing magnitude (so the
// first element in lexicographic order corresponds to the 2^0 bit.)
//
// This function generates and returns the next bit-pattern, in circular order
// (so that if the iteration is finished, it returns 0).
//
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
  UnsignedInteger last_one = comb & -comb;
  UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
  if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
  else if (last_one > 1) return mask / (last_one / 2);
  else return ~comb & 1;
}

Line 5 is doing the bit-hacking equivalent of the (extended) regular expression replacement, which finds the last 01 in the string, flips it to 10 and shifts all the following 1s all the way to the right.

s/01(1*)(0*)$/10\2\1/

Line 6 does this one (only if the previous one failed) to add one more 1 and shift the 1s all the way to the right:

s/(1*)0(0*)/\21\1/

I don't know if that explanation helps or hinders :)

---

Here's a quick and dirty driver (the command-line argument is the size of the set, default 5, maximum the number of bits in an unsigned long):

#include <iostream>

template<typename UnsignedInteger>
std::ostream& show(std::ostream& out, UnsignedInteger comb) {
  out << '[';
  char a = 'a';
  for (UnsignedInteger i = 1; comb; i *= 2, ++a) {
    if (i & comb) {
      out << a;
      comb -= i;
    }
  }
  return out << ']';
}

int main(int argc, char** argv) {
  unsigned int n = 5;
  if (argc > 1) n = atoi(argv[1]);
  unsigned long mask = (1UL << n) - 1;
  unsigned long comb = 0;
  do {
    show(std::cout, comb) << std::endl;
    comb = next_combination(comb, mask);
  } while (comb);
  return 0;
}

---

It's hard to believe that this function might be useful for a set of more than 64 elements, given the size of the enumeration, but it might be useful to enumerate some limited part, such as all subsets of three elements. In this case, the bit-hackery is only really useful if the modification fits in a single word. Fortunately, that's easy to test; you simply need to do the computation as above on the last word in the bitset, up to the test for last_zero being zero. (In this case, you don't need to bitand mask, and indeed you might want to choose a different way of specifying the set size.) If last_zero turns out to be zero (which will actually be pretty rare), then you need to do the transformation in some other way, but the principle is the same: find the first 0 which precedes a 1 (watch out for the case where the 0 is at the end of a word and the 1 at the beginning of the next one); change the 01 to 10, figure out how many 1s you need to move, and move them to the end.

How to get all subsets of a set? (powerset)

The Python itertools page has exactly a powerset recipe for this:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Output:

>>> list(powerset("abcd"))
[(), ('a',), ('b',), ('c',), ('d',), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), ('a', 'b', 'c', 'd')]

If you don't like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.

What algorithm can calculate the power set of a given set?

There is a name for what you're asking. It's called the power set.

Googling for "power set algorithm" led me to this recursive solution.

Ruby Algorithm

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)  
   subset | subset.map { |x| x | [p] }
end

Power Set Intuition

If S = (a, b, c) then the powerset(S) is the set of all subsets
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?

S = () has what powerset(S)?

How get to it?

Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b)}

What is missing?

powerset(S) = {(c), (a,c), (b,c), (a,b,c)}

hmmm

Notice any similarities? Look again...

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} is

powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with

{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {e_i}) U ({e_i} U powerset(S - {e_i}))

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done (Note that power set of {} is {{}})
2. If not, take an element out
   
   
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     
     
     1. the powerset of the set without the element (from the recursive call)
     2. this same set (i.e., 2.1) but with each element therein unioned with the element initially taken out

Generating all the elements of a power set

The problem is in your hasNext. You have i++ < subsets there. What happens is that since hasNext is called once from next() and once more during the iteration for (Set<Integer> subset : pSet) you increment i by 2 each time. You can see this since

for (Set<Integer> subset : pSet) {

}

is actually equivalent to:

Iterator<PowerSet> it = pSet.iterator();
while (it.hasNext()) {
    Set<Integer> subset = it.next();
}

Also note that

if (bitSet.cardinality() == 0) {
    return subset;
}

is redundant. Try instead:

@Override
public boolean hasNext() {
    return i <= subsets;
}

@Override
public Set<E> next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }
    Set<E> subset = new TreeSet<E>();
    BitSet bitSet = BitSet.valueOf(new long[] { i });
    for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) {
        subset.add(ary[e]);
    }
    i++;

    return subset;
}

How to generate a power set of a given set?

Power set of a set A is the set of all of the subsets of A.

Not the most friendly definition in the world, but an example will help :

Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2}

Thus, the power set is {{}, {1}, {2}, {1, 2}}

---

To generate the power set, observe how you create a subset : you go to each element one by one, and then either retain it or ignore it.

Let this decision be indicated by a bit (1/0).

Thus, to generate {1}, you will pick 1 and drop 2 (10).

On similar lines, you can write a bit vector for all the subsets :

• {} -> 00
  
  {1} -> 10
  
  {2} -> 01
  
  {1,2} -> 11

To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N different decisions, corresponding to 2^N different subsets.

See if you can pick it up from here.

selecting a random element of the power set

I think you're going about this the long way. You were close when you mentioned the size of the power set as 2ⁿ. If you want to select a random element of the power set of a set of size n, generate a random integer in the range [0, 2ⁿ) and use the binary representation of the integer to select the appropriate element from the power set.

For example, suppose S = {a, b, c, d, e}. The power set then contains 2⁵ = 32 elements. Generate a random number from 0 to 31, for example 18. The binary representation of 18 is 10010, so you would select the first and fourth elements of S. Your random element of the power set is then {a, d}.

How do I get a power set in a specific order?

You want the combinations in order by length. In Python you can write:

import itertools

def subsets(iterable):
    "Generate the subsets of elements in the iterable, in order by length."
    items = list(iterable)
    for k in xrange(len(items) + 1):
        for subset in itertools.combinations(items, k):
            yield subset

>>> list(subsets([1,2,3,4]))
[(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

See this answer for an overview of algorithms that generate combinations. (Or you can look at Raymond Hettinger's Python implementation, itertoolsmodule.c lines 2026f.)

How can I find all the subsets of a set, with exactly n elements?

itertools.combinations is your friend if you have Python 2.6 or greater. Otherwise, check the link for an implementation of an equivalent function.

import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))

S: The set for which you want to find subsets

m: The number of elements in the subset

Obtaining a powerset of a set in Java

Yes, it is O(2^n) indeed, since you need to generate, well, 2^n possible combinations. Here's a working implementation, using generics and sets:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  

And a test, given your example input:

 Set<Integer> mySet = new HashSet<Integer>();
 mySet.add(1);
 mySet.add(2);
 mySet.add(3);
 for (Set<Integer> s : SetUtils.powerSet(mySet)) {
     System.out.println(s);
 }

---

Related Topics