How can I limit my powerset function?

Question

I found a powerset function from a StackOverflow Post:

    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;
    }

But I am not interested in the entire powerset. It uses too much memory, is limited to the maxvalue of integer, and takes too long. Imagine I have an unlimited length string that I'm taking the powerset of, I couldn't store it. I only want 10 values that are located 25% of the way through the powerset.

For instance, if I send an array of 22 values to the powerset function:

var toTakePowerSetOf = {3,-3,39,-39,392,-392,3920,-3920, 9, -9, 92, -92, 920, -920, 9203, -9203, 2, -2, 20, -20, 203, -203}

I normally get a powerset of 4194304 elements. But I only care about the values at index @ 1049089/4194304 which is {3, -9, 203} . How can I edit the fast powerset function to use unlimited precision, go to a specific index, and only store ~10 values.

The index is calculated as 2^n/4 where n is the number of elements in the toTakePowerSetOf. For my example there are 22 elements: 2^22=4194304 . 4194304/4 = 1048576 . The actual value I was seeking is at 1049089 which is 513 away. In my question I said I would like to check the surrounding 10 values, but I guess I should really say I'd like to check about 513 values (.0122 %) of numbers around it.

This algorithm I'm trying to use may lead to faster factoring, but I need to find out if its the case that factors always appear near 25% of the way through the powerset. It may not make much sense, but if it works I'll share it with you and we can solve P=NP lol

Answer 1

The problem with the given FastPowerSet algorithm is that you need to calculate all the preceding power sets for a new one. Another Algo is presentend on the Wikipedia page for power sets.

Here is a short implementation:

    public static T[][] FastPowerSet2<T>(T[] seq)
    {
        var powerSet = new T[1 << seq.Length][];
        powerSet[0] = new T[0]; // starting only with empty set
        for (uint i = 1; i < powerSet.Length; i++)
        {
            powerSet[i] = PowerSetItem(i, seq, powerSet.Length);
        }
        return powerSet;
    }

    private static T[] PowerSetItemBig<T>(BigInteger neededSetIndex, T[] p)
    {
        byte[] neededSetBytes = neededSetIndex.ToByteArray();
        BitArray b = new BitArray(neededSetBytes);
        return p.Take(b.Length).Where((s, j) =>  b[j]).ToArray();
    }

    private static T[] PowerSetItem<T>(uint powersetIndex, T[] sequence, int powersetLength)
    {
        BitArray b = new BitArray(BitConverter.GetBytes(powersetIndex));
        if (b.Length < powersetLength)
        {
            var prefix = new BitArray(powersetLength - b.Length);
            b = Append(prefix, b);
        }

        return sequence.Where((s, j) => b[j]).ToArray();
    }
    public static BitArray Append(BitArray current, BitArray after)
    {
        var bools = new bool[current.Count + after.Count];
        current.CopyTo(bools, 0);
        after.CopyTo(bools, current.Count);
        return new BitArray(bools);
    }

With these functions, you also have the possibility to generate the specific powerset item with:

int[] P = { 3, -3, 39, -39, 392, -392, 3920, -3920, 9, -9, 92, -92, 920, -920, 9203, -9203, 2, -2, 20, -20, 203, -203 };
var p1049089 = PowerSetItem(1049089, P, (2^P.Length));
Console.WriteLine(string.Join(", ", p1049089));

The BigInteger version works with

var p1049089 = PowerSetItemBig(new BigInteger(1049089), P);

NB: I took some shortcuts with linq, and omitted some bound checks on incoming arrays, but this will work for this specific usecase