I have written a code in C# to generate the power set of a given input list of integers.
public List<List<int>> GeneratePowerSet(List<int> Set)
{
int setCount = Set.Count;
int powerSetCount = 1 << setCount;
// Temporary list to hold the all subsets
List<List<int>> subsets = new List<List<int>>();
// Outer loop running 2^n times
for (int i = 0; i < powerSetCount; i++)
{
// Inner loop running n times to check if j-th bit is set or not
for (int j = 0; j < setCount; j++)
{
// Temporary list to hold the current subset
List<int> subset = new List<int>();
// Check if j-th bit of i is 1 or no
if ((i & (1 << j)) != 0)
{
subset.Add(Set[j]);
}
subsets.Add(subset);
}
}
return subsets;
}
As seen above I am making 2 temporary input lists which is causing extra overhead while generating the subsets.
Also for larger inputs I have observed it takes too long to compute the power sets.
How can I rewrite this method using the iterator pattern so that each time it yields out the current value without having me to make a temporary list.
Update:
public static IEnumerable<IEnumerable<int>> GeneratePowerSet(List<int> Set)
{
int setCount = Set.Count;
int powerSetCount = 1 << setCount;
// Outer loop running 2^n times
for (int i = 0; i < powerSetCount; i++)
{
// Inner loop running n times to check if j-th bit is set or not
for (int j = 0; j < setCount; j++)
{
// Check if j-th bit of i is 1 or no
if ((i & (1 << j)) != 0)
{
yield return new[] { Set[j] };
}
}
}
}
18
Imagine you have a powerset for a set of N-1 elements, then the powerset for N elements returns twice as many, those with the Nth element and those without. We can implement this recursively, as follows.
using System.Collections.Generic;
using System.Linq;
public static class SetExtensions
{
private static IEnumerable<IEnumerable<T>> PowersetFrom<T>(List<T> elems, int current)
{
if (current == elems.Count)
{
yield return Enumerable.Empty<T>();
yield break;
}
var single = new T[]{ elems[current] };
foreach (var next in PowersetFrom(elems, current + 1))
{
yield return single.Concat(next);
yield return next;
}
}
public static IEnumerable<IEnumerable<T>> Powerset<T>(this List<T> elems)
{
return PowersetFrom(elems, 0);
}
}
Stepping through, for Powerset({1, 2, 3})
PowersetFrom({1, 2, 3}, 0)
calls PowersetFrom({1, 2, 3}, 1)
calls PowersetFrom({1, 2, 3}, 2)
calls PowersetFrom({1, 2, 3}, 3)
which returns {{}}
which yields {3}, {}
which yields {2, 3}, {3}, {2}, {}
which yields {1, 2, 3}, {2, 3}, {1, 3}, {3}, {1, 2}, {2}, {1}, {}
An alternative, using BigInteger, looks similar to what you have
public static IEnumerable<IEnumerable<int>> GeneratePowerSet(List<int> Set)
{
// Outer loop running 2^n times
for (BigInteger i = BigInteger.Zero; i < (BigInteger.One << Set.Count); i++)
{
yield return Set.Where((_, j) => (i & (BigInteger.One << j)) != 0);
}
}
9