加速处理组合中的 32 位数字（n 中的 k）

Question

我有一个 128 个 32 位数字的列表，我想知道是否有 12 个数字的任意组合，以便所有数字异或后给出 32 位数字，所有位都设置为 1。

所以我从简单的方法开始，采取了像这样的组合生成器：

        private static IEnumerable<int[]> Combinations(int k, int n)
        {
            var state = new int[k];
            var stack = new Stack<int>();
            stack.Push(0);

            while (stack.Count > 0)
            {
                var index = stack.Count - 1;
                var value = stack.Pop();

                while (value < n)
                {
                    state[index++] = value++;
                    if (value < n)
                    {
                        stack.Push(value);
                    }

                    if (index == k)
                    {
                        yield return state;
                        break;
                    }
                }
            }
        }

并像这样使用它（data32是给定的32位数字的数组）

foreach (var probe in Combinations(12, 128))
{
   int p = 0;
   foreach (var index in probe)
   {
      p = p ^ data32[index];
   }
   if (p == -1)
   {
      //print out found combination
   }
}

当然，检查所有23726045489546400个组合需要很长时间...... 所以我的问题是 - 我是否在选项中遗漏了一些如何加快检查过程的内容？ 即使我在分区中计算组合（例如，我可以启动 8 个线程，每个线程都会检查以数字 0..8 开头的组合），或者通过存储先前计算的组合来加速异或运算 - 它仍然很慢。

PS我希望它在合理的时间内运行 - 分钟，小时而不是几年。 按照评论之一的要求添加号码列表：

1571089837 2107702069 466053875 226802789 506212087 484103496 1826565655 944897655 1370004928 748118360 1000006005 952591039 2072497930 2115635395 966264796 1229014633 827262231 1276114545 1480412665 2041893083 512565106 1737382276 1045554806 172937528 1746275907 1376570954 1122801782 2013209036 1650561071 1595622894 425898265 770953281 422056706 477352958 1295095933 1783223223 842809023 1939751129 1444043041 1560819338 1810926532 353960897 1128003064 1933682525 1979092040 1987208467 1523445101 174223141 79066913 985640026 798869234 151300097 770795939 1489060367 823126463 1240588773 490645418 832012849 188524191 1034384571 1802169877 150139833 1762370591 1425112310 2121257460 205136626 706737928 265841960 517939268 2070634717 1703052170 1536225470 1511643524 1220003866 714424500 49991283 688093717 1815765740 41049469 529293552 1432086255 1001031015 1792304327 1533146564 399287468 1520421007 153855202 1969342940 742525121 1326187406 1268489176 729430821 1785462100 1180954683 422085275 1578687761 2096405952 1267903266 2105330329 471048135 764314242 459028205 1313062337 1995689086 1786352917 2072560816 282249055 1711434199 1463257872 1497178274 472287065 246628231 1928555152 1908869676 1629894534 885445498 1710706530 1250732374 107768432 524848610 2791827620 1607140095 1820646148 774737399 1808462165 194589252 1051374116 1802033814

Answer 1

我不知道C＃，我在Python做了一些事情，也许还是很有趣。为您的样品集找到解决方案大约需要0.8秒：

solution = {422056706, 2791827620, 506212087, 1571089837, 827262231, 1650561071, 1595622894, 512565106, 205136626, 944897655, 966264796, 477352958}
len(solution) = 12
solution.issubset(nums) = True
hex(xor(solution)) = '0xffffffff'

有128c12组合，是2 ³² 可能的XOR值的550万倍。因此，我尝试保持乐观，只尝试了可能的组合。我将128个数字分为28个块和100个数字，并尝试使用两个块中每个块的六个数字组合。我将第一个块的所有可能的XOR都放入哈希集中，然后浏览第二个块的所有XOR，以找到一个位于该集合的位倒置的XOR。然后，我重建单个数字。

这样，我覆盖（28C6） ² ×（100c6） ² = 4.5E14组合，仍然是可能的XOR值的100000倍。因此，可能仍然是找到有效组合的好机会。

Code (

from itertools import combinations
from functools import reduce
from operator import xor as xor_

nums = list(map(int, '1571089837 2107702069 466053875 226802789 506212087 484103496 1826565655 944897655 1370004928 748118360 1000006005 952591039 2072497930 2115635395 966264796 1229014633 827262231 1276114545 1480412665 2041893083 512565106 1737382276 1045554806 172937528 1746275907 1376570954 1122801782 2013209036 1650561071 1595622894 425898265 770953281 422056706 477352958 1295095933 1783223223 842809023 1939751129 1444043041 1560819338 1810926532 353960897 1128003064 1933682525 1979092040 1987208467 1523445101 174223141 79066913 985640026 798869234 151300097 770795939 1489060367 823126463 1240588773 490645418 832012849 188524191 1034384571 1802169877 150139833 1762370591 1425112310 2121257460 205136626 706737928 265841960 517939268 2070634717 1703052170 1536225470 1511643524 1220003866 714424500 49991283 688093717 1815765740 41049469 529293552 1432086255 1001031015 1792304327 1533146564 399287468 1520421007 153855202 1969342940 742525121 1326187406 1268489176 729430821 1785462100 1180954683 422085275 1578687761 2096405952 1267903266 2105330329 471048135 764314242 459028205 1313062337 1995689086 1786352917 2072560816 282249055 1711434199 1463257872 1497178274 472287065 246628231 1928555152 1908869676 1629894534 885445498 1710706530 1250732374 107768432 524848610 2791827620 1607140095 1820646148 774737399 1808462165 194589252 1051374116 1802033814'.split()))

def xor(vals):
    return reduce(xor_, vals)

A = {xor(a)^0xffffffff: a
     for a in combinations(nums[:28], 6)}

for b in combinations(nums[28:], 6):
    if a := A.get(xor(b)):
        break

solution = {*a, *b}

print(f'{solution = }')
print(f'{len(solution) = }')
print(f'{solution.issubset(nums) = }')
print(f'{hex(xor(solution)) = }')

Answer 2

根据第一个1位的位置将您的数字安排到存储桶中。

要将第一个位设置为1，您将必须使用相应的存储桶中的奇数项目。...

在您重复时，请尝试保持一个不变的领导1 位正在增加，然后选择将将下一个0更改为1的存储桶，这将大大减少您必须需要的组合数量尝试。

Answer 3

我找到了一个可能的解决方案，它可以适合我的特定任务。
作为简单方法的主要问题，我看到了许多 2E16 组合。
但是，如果我想检查 12 个元素的组合是否等于 0xFFFFFFFF，我可以检查是否存在具有相反值的 6 个元素的 2 种不同组合。
这会将组合数量减少到“仅”5E9，这是可以实现的。
第一次尝试时，我想存储所有组合，然后在大列表中找到相反的组合。但是，在 .NET 中，我找不到存储比 Int32.MaxValue 元素更多的快速方法。

考虑到评论和答案中的位的想法，我决定首先仅存储最左边位设置为 1 的异或和，然后根据定义，我只需要检查最左边位设置为 0 的和 =>存储量减少 2。
最后看来可能会出现许多冲突，因此存在许多具有相同异或和的组合。

当前版本可以找到此类组合，需要在 x64 模式下编译并使用（欢迎任何改进）：

    static uint print32(int[] comb, uint[] data)
    {
        uint p = 0;
        for (int i = 0; i < comb.Length; i++)
        {
            Console.Write("{0} ", comb[i]);
            p = p ^ data[comb[i]];
        }
        Console.WriteLine(" #[{0:X}]", p);
        return p;
    }

    static uint[] data32;

    static void Main(string[] args)
    {
        int n = 128;
        int k = 6;
        uint p = 0;
        uint inv = 0;
        long t = 0;

        //load n numbers from a file
        init(n);

        var lookup1x = new Dictionary<uint, List<byte>>();
        var lookup0x = new Dictionary<uint, List<byte>>();

        Stopwatch watch = new Stopwatch();
        watch.Start();

        //do not use IEnumerable generator, use function directly to reuse xor value
        var hash = new uint[k];
        var comb = new int[k];
        var stack = new Stack<int>();
        stack.Push(0);

        while (stack.Count > 0)
        {
            var index = stack.Count - 1;
            var value = stack.Pop();

            if (index == 0)
            {
                p = 0;
                Console.WriteLine("Start {0} sequence, combinations found: {1}",value,t);
            }
            else
            {
                //restore previous xor value
                p = hash[index - 1];
            }

            while (value < n)
            {
                //xor and store
                p = p ^ data32[value];
                hash[index] = p;
                //remember current state (combination)
                comb[index++] = value++;

                if (value < n)
                {
                    stack.Push(value);
                }

                //combination filled to end
                if (index == k)
                {
                    //if xor have MSB set, put it to lookup table 1x
                    if ((p & 0x8000000) == 0x8000000)
                    {
                        lookup1x[p] = comb.Select(i => (byte)i).ToList();
                        inv = p ^ 0xFFFFFFFF;
                        if (lookup0x.ContainsKey(inv))
                        {
                            var full = lookup0x[inv].Union(lookup1x[p]).OrderBy(x=>x).ToArray();
                            if (full.Length == 12)
                            {
                                print32(full, data32);
                            }
                        }
                    }
                    else
                    {
                        //otherwise put it to lookup table 2, but skip all combinations which are started with 0 
                        if (comb[0] != 0)
                        {
                            lookup0x[p] = comb.Select(i => (byte)i).ToList();
                            inv = p ^ 0xFFFFFFFF;
                            if (lookup1x.ContainsKey(inv))
                            {
                                var full = lookup0x[p].Union(lookup1x[inv]).OrderBy(x=>x).ToArray();
                                if (full.Length == 12)
                                {
                                    print32(full, data32);
                                }
                            }
                        }
                    }

                    t++;
                    break;
                }
            }
        }
        Console.WriteLine("Check was done in {0} ms ", watch.ElapsedMilliseconds);
        //end
    }