我有一個 128 個 32 位數字的串列，我想知道，是否有 12 個數字的任意組合，以便所有數字異或得到所有位設定為 1 的 32 位數字。
所以我從幼稚的方法開始，并采用了這樣的組合生成器：
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 開頭的組合），或者通過存盤先前計算的組合來加速 XORing - 它仍然很慢。
P.S. I'd like it to run in reasonable time - minutes, hours not years. Adding a list of numbers as was requested in one of the comments:
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
uj5u.com熱心網友回復：
我不知道 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 32 個可能的 XOR 值的 550 萬倍。所以我試著保持樂觀，只嘗試了可能組合的一個子集。我將 128 個數字分成 28 個和 100 個數字的兩個塊，并嘗試從兩個塊中的每個塊中組合六個數字。我將第一個塊的所有可能的 XOR 放入一個哈希集中A，然后遍歷第二個塊的所有 XOR 以找到按位反轉在該集中的一個。然后我重建個人數字。
這樣我覆寫了 (28C6) 2 × (100C6) 2 = 4.5e14 組合，仍然是可能的 XOR 值的 100000 倍以上。所以可能仍然是一個很好的機會來找到一個有效的組合。
代碼（在線試用！）：
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)) = }')
uj5u.com熱心網友回復：
根據第1一位的位置將您的數字排列到存盤桶中。
要將第一位設定為1，您將必須使用相應存盤桶中的奇數個專案....
當你遞回時，嘗試保持一個不變數，即前導1位的數量正在增加，然后選擇將下一個0變為 a的存盤桶1，這將大大減少你必須嘗試的組合數量。
uj5u.com熱心網友回復：
我找到了一個可能的解決方案，它可以用于我的特定任務。作為直截了當的方法的主要問題，我看到了許多 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
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/457304.html
標籤：c# algorithm performance combinations
上一篇：bash更有效的方法來轉換奇數日期格式以被linux日期識別
下一篇：R-使用apply加速搜索