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
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
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments