如何限制我的 powerset 功能？

Question

我从 Whosebug 找到了一个 powerset 函数 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;
    }

但我对整个动力装置不感兴趣。它使用太多内存，仅限于整数的最大值，并且花费的时间太长。想象一下，我有一个无限长的字符串，我正在使用它的幂集，但我无法存储它。我只想要 10 个值，它们位于 powerset 的 25% 处。

例如，如果我向 powerset 函数发送一个包含 22 个值的数组：

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

我通常得到 4194304 个元素的幂集。但我只关心 index @ 1049089/4194304 处的值，即 {3, -9, 203} 。如何编辑 fast powerset 函数以使用无限精度、转到特定索引并仅存储 ~10 个值。

索引计算为 2^n/4，其中 n 是 toTakePowerSetOf 中的元素数。对于我的示例，有 22 个元素： 2^22=4194304 。 4194304/4 = 1048576。我正在寻找的实际值是 1049089，相距 513。在我的问题中，我说我想检查周围的 10 个值，但我想我真的应该说我想检查周围数字的大约 513 个值 (.0122 %)。

我尝试使用的这个算法可能会导致更快的因式分解，但我需要查明是否因式总是出现在幂集的 25% 附近。它可能没有多大意义，但如果有效，我会与您分享，我们可以解决 P=NP lol

Answer 1

给定的 FastPowerSet 算法的问题是您需要为新算法计算所有前面的幂集。 Wikipedia page 上还有另一个算法用于幂集。

这是一个简短的实现：

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

使用这些函数，您还可以生成特定的 powerset 项目：

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

BigInteger 版本适用于

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

注意：我使用 linq 采取了一些快捷方式，并省略了对传入数组的一些绑定检查，但这适用于这个特定的用例

Answer 2

我的解决方案为您提供了 25% 指数附近的集合。该索引之后和该索引之前的两个集合。

我的解决方案不限于整数大小，也不使用位数组。

它将处理极长的序列。所需要的只是上下文大小（在您的情况下为 513）不要太大。

代码解释如下：

因此，您希望在功率设置为 25% 指数（我称之为 "central"）附近看到一些向前和向后 "context"。

索引为 25% 的集合由单个项目组成。那是因为 2^n/4 = 1 << (n-1-2) 0000000000100.....

当我们从这个 set/number 继续前进时，我们基本上是在重复相同的前 513 个功率组，但包括中心项目：

0000000000100..... = +0 context = powerSet[0] U { seq[central] }
1000000000100..... = +1 context = powerSet[1] U { seq[central] }
0100000000100..... = +2 context = powerSet[2] U { seq[central] }
1100000000100..... = +3 context = powerSet[3] U { seq[central] }
0010000000100..... = +4 context = powerSet[4] U { seq[central] }

当我们倒退时，数字的行为有些相似，但位看起来相反：

1111111111000..... = -1 context = { seq[0], seq[1], ..., seq[central - 1] } \ powerSet[0]
0111111111000..... = -2 context = { seq[0], seq[1], ..., seq[central - 1] } \ powerSet[1]
1011111111000..... = -3 context = { seq[0], seq[1], ..., seq[central - 1] } \ powerSet[2]
0011111111000..... = -4 context = { seq[0], seq[1], ..., seq[central - 1] } \ powerSet[3]
1101111111000..... = -5 context = { seq[0], seq[1], ..., seq[central - 1] } \ powerSet[4]

通过结合后向上下文和前向上下文，我们得到完整的 [-514 .. +513] 上下文

这是解决您问题的代码：

    public static T[][] PartialPowerSet<T>(T[] seq, int forwardContextSize) {
        int n = seq.Length;
        int centralItemIndex = n - 2; //=log2(2^n/4)
        int numberOfItemsForContext = (int)Math.Ceiling(Math.Log(forwardContextSize, 2));

        var smallContextSeq = seq.Take(numberOfItemsForContext).ToArray();

        var smallContextPowerSet = FastPowerSet(smallContextSeq);
        smallContextPowerSet = smallContextPowerSet.Take(forwardContextSize + 1).ToArray();

        var forwardContextTemplateItems = new[] { seq[centralItemIndex] }; //To get forward context we're adding (union) the small context items
        var forwardContextItems = smallContextPowerSet.Select(s => s.Concat(forwardContextTemplateItems).ToArray());

        var backwardContextTemplateItems = seq.Take(centralItemIndex - 1).ToList(); //To get backward context we're removing (minus) the small context items from the set of all items up to, but not including the central item
        var backwardContextItems = smallContextPowerSet.Reverse().Select(s => backwardContextTemplateItems.Except(s).ToArray()); //Getting sets for c-513, c-512, ...., c-1. That's why we reverse the order of the smallContextPowerSet.

        return backwardContextItems.Concat(forwardContextItems).ToArray();
    }

    static void Main(string[] args) {
        var toTakePowerSetOf = new[] { 3, -3, 39, -39, 392, -392, 3920, -3920, 9, -9, 92, -92, 920, -920, 9203, -9203, 2, -2, 20, -20, 203, -203 };

        var res = PartialPowerSet(toTakePowerSetOf, 513);

        Console.WriteLine(string.Join(",", res[513 + 1 + 513])); //Prints "3,-9,203"
    }

打印 3,-9,203

如何限制我的 powerset 功能？

How can I limit my powerset function?

c#

optimization

powerset