Calculating the Power set of large string array in C#

Question

I want to calculate power set of string array (consider it as a set). When I am exceeding above 26 elements it is thowing out of memory exception.

List<int> ff = new List<int>();
double length = Math.Pow(2, 29);
for (int i = 0; i < length; i++)
{
   ff.Add(1);
}

Above code will produce the that exception if you run it. The size of the set may go up to 1000. So the size of power set of that set will be 2^1000.

How can I deal with this?

EDIT:

I know that above code is not a function of power set. I was just checking how big array c# will be able to hold.

 private static Dictionary<int, object> PowerSetB(string[] input)
        {
            int n = input.Length;
            // Power set contains 2^N subsets.
            int powerSetCount = 1 << n;
            var ans = new Dictionary<int, object>();

            for (int setMask = 0; setMask < powerSetCount; setMask++)
            {
                var s = new ArrayList();
                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.Add(input[i]);
                }
                ans[setMask] = s;
            }
            return ans;
        }

Above code is my function of power set.

Thank you in advance.

Answer 1

Do you really want to store all the items in memory? I suggest using IEnumerable<int> instead of materialized List<int>:

// just enumeration, coefficients aren't stored
public static IEnumerable<int> Serie(Func<int, int> coefByIndex) {
  if (null == coefByIndex)
    throw new ArgumentNullException("coefByIndex");

  for (int i = 0; ; ++i)
    yield return coefByIndex(i);
}

// Let's sum up all 2**29 values, 
// i.e. compute f(1) summing up 2**29 items (it's a long process...)
// sum = 1.44115187606094E+17 (diverges, as we might have expected)
Double sum = Serie(index => index)
  .Select(x => x * 1.0)
  .Take(1 << 29)
  .Sum();

Edit: Once agian, do not materialize (Dictionary<int, object>) huge results! Provide an IReadOnlyDictionary<int, int[]> interface but not implementation as Dictionary<int, object>,
Something like this:

  // ArrayList is an obsolete collection;
  // int[] far more natural here
  public sealed class PowerSet: IReadOnlyDictionary<int, int[]> {
    private int m_Power;

    private int[] getItem(int index) {
      int[] result = new int[m_Power];

      for (int i = 0; i < m_Power; ++i) {
        result[i] = index % 2;

        index /= 2;
      }

      return result;
    }

    public PowerSet(int power) {
      m_Power = power;
    }

    public int[] this[int key] {
      get {
        if (key >= 0 && key < Count)
          return getItem(key);
        else
          throw new ArgumentOutOfRangeException("key");
      }
    }

    public int Count {
      get {
        return 1 << m_Power;
      }
    }

    public IEnumerable<int> Keys {
      get {
        return Enumerable.Range(0, Count);
      }
    }

    public IEnumerable<int[]> Values {
      get {
        return Enumerable.Range(0, Count).Select(index => getItem(index));
      }
    }

    public bool ContainsKey(int key) {
      return key >= 0 && key < Count;
    }

    public IEnumerator<KeyValuePair<int, int[]>> GetEnumerator() {
      return Enumerable
        .Range(0, Count)
        .Select(index => new KeyValuePair<int, int[]>(index, getItem(index)))
        .GetEnumerator();
    }

    public bool TryGetValue(int key, out int[] value) {
      if (key >= 0 && key < Count) {
        value = getItem(key);

        return true;
      }

      value = null;
      return false;
    }

    IEnumerator IEnumerable.GetEnumerator() {
      return this.GetEnumerator();
    }
  }

  ... 

  // Just an easy call
  private static IDictionary<int, int[]> PowerSetB(string[] input) {
    return new PowerSet(input.Length);
  }