Creating a power set of a Sequence
Power set is easy to generate if one is familiar with bits. For the set of N elements, there will be 2^N subsets which will go to power set (including empty set and initial set). So each element will be either IN or OUT (1 or 0 in other words).
Taking this into consideration, it is easy to represent subsets of the set as bit masks. Then enumerating through all possible bit masks, it is possible construct the whole power sets. In order to do this we need to examine each bit in bit mask and take element of input set if there is 1 in that place. Below is example for string (collection of chars) as input. It can be easily rewritten to work for collection of any type values.
private static List<string> PowerSet(string input)
{
int n = input.Length;
// Power set contains 2^N subsets.
int powerSetCount = 1 << n;
var ans = new List<string>();
for (int setMask = 0; setMask < powerSetCount; setMask++)
{
var s = new StringBuilder();
for (int i = 0; i < n; i++)
{
// Checking whether i'th element of input collection should go to the current subset.
if ((setMask & (1 << i)) > 0)
{
s.Append(input[i]);
}
}
ans.Add(s.ToString());
}
return ans;
}
Example
Suppose you have string "xyz" as input, it contains 3 elements, than there will be 2^3 == 8 elements in power set. If you will be iterating from 0 to 7 you will get the following table. Columns: (10-base integer; bits representation (2-base); subset of initial set).
0 000 ...
1 001 ..z
2 010 .y.
3 011 .yz
4 100 x..
5 101 x.z
6 110 xy.
7 111 xyz
You can notice that third column contains all subsets of initial string "xyz"
Another approach (twice faster) and generic implementation
Inspired by Eric's idea, I have implemented another variant of this algorithm (without bits now). Also I made it generic. I believe this code is near to fastest of what can be written for Power Set calculation. Its complexity is the same as for bits approach O(n * 2^n), but for this approach constant is halved.
public static T[][] FastPowerSet<T>(T[] seq)
{
var powerSet = new T[1 << seq.Length][];
powerSet[0] = new T[0]; // starting only with empty set
for (int i = 0; i < seq.Length; i++)
{
var cur = seq[i];
int count = 1 << i; // doubling list each time
for (int j = 0; j < count; j++)
{
var source = powerSet[j];
var destination = powerSet[count + j] = new T[source.Length + 1];
for (int q = 0; q < source.Length; q++)
destination[q] = source[q];
destination[source.Length] = cur;
}
}
return powerSet;
}
SergeyS's approach is perfectly reasonable. Here's an alternative way to think about it.
For the purposes of this answer I'm going to assume that "sets" are finite sequences.
We define the function P recursively as follows.
- A set is either empty, or a single item H followed by a set T.
P(empty) --> { empty }-
P(H : T) -->the union ofP(T)and every element ofP(T)prepended withH.
Let's try that out. What's the power set of {Apple, Banana, Cherry}?
It's not an empty set, so the power set of {Apple, Banana, Cherry} is the power set of {Banana, Cherry}, plus the sets formed by prepending Apple to each.
So we need to know the power set of {Banana, Cherry}. It's the power set of {Cherry} plus the sets form by prepending Banana to each.
So we need to know the power set of {Cherry}. It's the power set of the empty set, plus the sets formed by prepending Cherry to each.
So we need to know the power set of the empty set. It's the set containing the empty set. { {} }
Now prepend each element with Cherry and take the union. That's { {Cherry}, {} }. That gives us the power set of { Cherry }. Remember we needed that to find the power set of {Banana, Cherry}, so we union it with Banana prepended to each and get { {Banana, Cherry}, {Banana}, {Cherry}, {}} and that's the power set of {Banana, Cherry}.
Now we needed that to get the power set of {Apple, Banana, Cherry}, so union it with Apple appended to each and we have { {Apple, Banana, Cherry}, {Apple, Banana}, {Apple, Cherry}, {Apple}, {Banana, Cherry}, {Banana}, {Cherry}, {}} and we're done.
The code should be straightforward to write. First we'll need a helper method:
static IEnumerable<T> Prepend<T>(this IEnumerable<T> tail, T head)
{
yield return head;
foreach(T item in tail) yield return item;
}
And now the code is a straightforward translation of the description of the algorithm:
static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> items)
{
if (!items.Any())
yield return items; // { { } }
else
{
var head = items.First();
var powerset = items.Skip(1).PowerSet().ToList();
foreach(var set in powerset) yield return set.Prepend(head);
foreach(var set in powerset) yield return set;
}
}
Make sense?
----------- UPDATE ----------------
Sergey points out correctly that my code has a Schlemiel the Painter algorithm and therefore consumes huge amounts of time and memory; good catch Sergey. Here's an efficient version that uses an immutable stack:
class ImmutableList<T>
{
public static readonly ImmutableList<T> Empty = new ImmutableList<T>(null, default(T));
private ImmutableList(ImmutableList<T> tail, T head)
{
this.Head = head;
this.Tail = tail;
}
public T Head { get; private set; }
public ImmutableList<T> Tail { get; private set; }
public ImmutableList<T> Push(T head)
{
return new ImmutableList<T>(this, head);
}
public IEnumerable<ImmutableList<T>> PowerSet()
{
if (this == Empty)
yield return this;
else
{
var powerset = Tail.PowerSet();
foreach (var set in powerset) yield return set.Push(Head);
foreach (var set in powerset) yield return set;
}
}
}
Same algorithm SergeyS mention using Linq (where inputSet is the input and outputPowerSet is the output):
int setLength = inputSet.Count;
int powerSetLength = 1 << setLength;
for (int bitMask = 0; bitMask < powerSetLength; bitMask++)
{
var subSet = from x in inputSet
where ((1 << inputSet.IndexOf(x)) & bitMask) != 0
select x;
outputPowerSet.Add(subSet.ToList());
}