最大化 XOR 序列上的 AND
Maximize AND on a sequence of XORs
问题
我们给出了 2 个长度为 n 的数组 a 和 b。我们通过重新排列 b 中的值来构建第三个数组 c。目标是找到最大化
的最优 c
result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])
其中 ^ 是 XOR，& 是 AND。
是否可以有效地做到这一点？迭代b的所有可能排列很简单，但这对于大n是不可行的。
更多详情
a中值的顺序是固定的。b 中值的顺序可以重新排列以形成 c。即以b = [1, 2, 3]开头，可能是重新排列为c = [2, 1, 3].b 可以就地重新排列（我在示例代码中这样做）。- 由于最佳
c 不一定是唯一的，因此可以返回任何最佳 c。
- 假设所有值都是 32 位无符号整数。
1 <= n <= 10,000.
测试用例
Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)
Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)
Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)
示例代码
这是我用于天真的解决方案的 C++ 代码，它详尽地尝试了 b 的所有排列（在 Windows 10 和 Visual Studio 2019 上测试）：
#include <algorithm> // next_permutation
#include <cstdint> // uint32_t
#include <iostream> // i/o
#include <vector> // vector
using uint = std::uint32_t;
using uvec = std::vector<uint>;
uint andxor(const uvec& a, const uvec& c)
{
// Start with all bits set
uint result = -1;
for (std::size_t i = 0; i < c.size(); ++i)
{
result &= a[i] ^ c[i];
}
return result;
}
uvec solvePermute(const uvec& a, uvec& b)
{
// next_permutation expects a pre-sorted input
std::sort(b.begin(), b.end());
// Initialize the result with the first permutation of b
uvec c = b;
uint bestResult = andxor(a, c);
// Try all permutations of b to maximize the result of andxor
while (std::next_permutation(b.begin(), b.end()))
{
uint result = andxor(a, b);
if (result > bestResult)
{
bestResult = result;
c = b;
}
}
return c;
}
int main()
{
// First test case
uvec a{ 3, 4, 5 };
uvec b{ 6, 7, 8 };
uvec c = solvePermute(a, b);
uint bestResult = andxor(a, c);
std::cout << "Maximum result is " << bestResult << " with c = ";
for (uint ci : c)
{
std::cout << ci << " ";
}
return 0;
}
TL;DR
我认为可以将其重新表述为 assignment problem，可以在 O(n^3) 时间内找到最佳解决方案。但我没有在我的回答中尝试这样做。
免责声明
我将要描述的方法仍然涉及检查排列。它通常似乎比原始方法需要更少的迭代，但我的解决方案的额外开销实际上可能会降低整体速度。我没有将我的方法的运行时间与天真的方法进行比较，我也没有详尽地检查它是否没有错误（对于提供的 3 个测试用例它似乎工作正常）。
话虽如此，我在此过程中确实有了一些见解，所以也许我的尝试会帮助其他人提出更有效的解决方案。希望我的解释是清楚的，我不是在胡说八道。
总体思路
假设我们创建一个无向的bipartite graph，其中两组独立的节点分别对应a和b，每个节点都是一个数组元素
让我们一次考虑一位，比如最低有效位 (LSB)。
我们将 LSB 标记为位 0。
我们还考虑第一个测试用例（为了简单起见，我们只考虑最低的 4 位而不是全部 32 位）：
Input:
a = [3, 4, 5] // binary: [0011, 0100, 0101]
b = [6, 7, 8] // binary: [0110, 0111, 1000]
我们的图表在 a 集合中有 3 个节点，标记为 3、4 和 5；它在 b 集合中有 3 个节点，分别标记为 6、7 和 8。如果 a 节点的所选位（位 0）与b 节点。例如，我们会在节点 3 和 6 之间画一条边，因为 3 的 LSB (0011) 与 6 的 LSB (0110).我们不会在节点 3 和节点 7 之间画一条边，因为 3 (0011) 的 LSB 与 7 (0111[=109) 的 LSB 相同=]).如果我们一直解决这个问题，我们最终会得到以下位 0 的邻接列表：
3: 6, 8
4: 7
5: 6, 8
我们有两组边，可以从 a 中的每个节点组成：
- 如果所选位为 1，则在
b 中所选位为 0 的所有节点绘制一条边。
- 如果所选位为 0，则在
b 中所选位为 1 的所有节点绘制一条边。
我们可以观察到，当且仅当该位为 1 的 a 个节点的数量与 b 个该位为 0 的节点。否则，该位在最终结果中不能为 1，因为我们必须将至少一个 a 节点与具有相同位值的 b 配对节点，在 XOR 之后为该位生成 0，因此在 AND 之后为该位生成 0。
现在，如果我们为 4 位中的每一位创建这样一个图，并确定最终结果中哪些位是 1 的候选位，这将为我们提供最佳结果的上限。这也为我们提供了一个明显的结果下限，因为我们知道我们至少可以找到 b 的排序，从而导致设置最重要的候选位。
下面给出了我们测试用例中每个位的邻接表。
Bit 0 (LSB)
3: 6, 8
4: 7
5: 6, 8
(candidate bit)
Bit 1
3: 8
4: 6, 7
5: 6, 7
(candidate bit)
Bit 2
3: 6, 7
4: 8
5: 8
(NOT candidate)
Bit 3 (MSB)
3: 8
4: 8
5: 8
(NOT candidate)
Upper bound: 3 (both candidate bits 0 and 1 are set)
Lower bound: 2 (only candidate bit 1 is set)
寻找 c
为了得到最优的c，我们需要从最高有效位开始。我们遍历所有有效的 cs（b 的排列，我们遵守该位的邻接列表），与 [= 的可能排列总数相比，希望其中的排列相对较少15=].
对于这些排列中的每一个，我们看看它们中的任何一个对于下一个最重要的候选位是否有效。如果其中 none 个是，那么我们检查之后的位，依此类推。如果在遵守邻接表的情况下，对于 MSB 上的任何排列，都不能包含其他位，那么最终结果中只有 MSB 可以为 1，这就是解决方案。否则，我们希望优先考虑对更重要的位起作用的排列，并且我们需要递归地检查对所有位有效的排列直到那个点。
排列“有效”是什么意思？本质上，邻接表充当了从 a 到 c 映射的约束。如果一个候选位的约束与另一个候选位的约束不冲突，我们知道这些位 can 在最终结果中都为 1。例如，查看位 0 和 1，我们看到有一种方法可以同时满足这两种映射（即 3: 8; 4: 7; 5: 6）。因此，该排列 (c = [8, 7, 6]) 对位 0 和 1 均有效。（事实上，该排列被证明是最佳排列。）
作为约束冲突的例子，考虑位 0 和位 2。位 2 要求节点 4 连接到节点 8。也就是说，在满足 a[i] == 4 的索引 i 处，我们需要设置 c[i] = 8 以便在最终结果中设置位 2。但是，bit 0 要求节点 4 连接到节点 7。这是一个冲突，因此不能在最终结果中同时设置 bit 0 和 bit 2。 （但是位 2 无论如何都不是候选位，因为 a 节点中的两个（4 和 5）的那个位为 1，但 b 节点（8）中只有一个为 0对于那一点。）
与已解决的图论问题的可能关系
我不是很熟悉图论问题，但在我看来这个问题的二分图公式与 最大加权二分匹配 也称为assignment problem。不过，我们的边缘目前没有加权。也许一条边可以根据它存在的位数来加权？也许更大的权重会被赋予更重要的位？我认为我们仍然只需要考虑来自候选位的图表。
本质上，从每个候选位的二部图构建一个nxn邻接矩阵。给边分配统一的权重pow(2, bit)；所以边缘权重对于位 0 为 1，对于位 1 为 2，对于位 2 为 4，依此类推。这确保了更重要的候选位优先于更小的候选位的任何组合。然后组合所有邻接矩阵的权重以构建最终的代表性邻接矩阵。这将是分配问题的输入。
如果此比较有效，则存在 Hungarian algorithm 可以在 O(n^3) 时间内最优地解决分配问题。这明显优于朴素排列方法所需的 O(n!) 时间。
乱码
为了完整起见，我包括了我为我提出的方法编写的代码，尽管我认为更值得研究将此问题重新表述为分配问题的可能性。要使用此代码，请从问题中提供的示例代码开始并将此代码复制到同一文件中。在 main 中，调用 solvePermuteLess 而不是 solvePermute.
#include <unordered_map>
#include <unordered_set>
uint recursiveVerification(size_t currentBit,
std::unordered_map<size_t, size_t>& a2bConstraints,
const uvec& possibleBits,
const std::unordered_map<uint, std::vector<size_t>>& aSetMap,
const std::unordered_map<uint, std::vector<size_t>>& bUnsetMap)
{
uint bestScore = 0;
std::unordered_map<size_t, size_t> a2bBest = a2bConstraints;
uint upperBoundScore = 0;
for (uint bit = currentBit; bit < possibleBits.size(); ++bit)
{
upperBoundScore += 1u << possibleBits[possibleBits.size() - bit - 1];
}
for (size_t bit = currentBit; bit < possibleBits.size(); ++bit)
{
uint bitValue = possibleBits[possibleBits.size() - bit - 1];
std::vector<size_t> aSet = aSetMap.at(bitValue);
std::vector<size_t> bUnset = bUnsetMap.at(bitValue);
std::sort(bUnset.begin(), bUnset.end());
do
{
// Set up necessary mappings for this permutation
std::unordered_map<size_t, size_t> a2b;
for (size_t i = 0; i < aSet.size(); ++i)
{
a2b[aSet[i]] = bUnset[i];
}
// Check for conflicts in mappings
bool hasConflicts = false;
for (auto jt = a2bConstraints.cbegin(); jt != a2bConstraints.cend(); ++jt)
{
auto findIt = a2b.find(jt->first);
if (findIt != a2b.end())
{
// The same value in `a` is being mapped. Make sure it's to
// the same value in `b`.
if (findIt->second != jt->second)
{
// Not mapped to same value; invalid permutation
hasConflicts = true;
break;
}
}
}
if (hasConflicts)
{
// We found conflicting mappings; try the next permutation
continue;
}
// If we reach this point, there were no mapping conflicts. We know
// this bit can be set alongside the parent bit. Merge the
// constraints and then try the next bit.
for (auto jt = a2bConstraints.cbegin(); jt != a2bConstraints.cend(); ++jt)
{
a2b[jt->first] = jt->second;
}
// Recursively check permutations of lower bits
uint score = (1u << bitValue)
+ recursiveVerification(bit + 1, a2b, possibleBits, aSetMap, bUnsetMap);
// Now a2b contains the best-performing mapping for this
// permutation. Track the best mapping across all permutations.
if (score > bestScore)
{
bestScore = score;
a2bBest = a2b;
// If we achieve the upper-bound result (all bits set), we know
// we can't do any better; so stop early
if (bestScore == upperBoundScore)
{
break;
}
}
} while (std::next_permutation(bUnset.begin(), bUnset.end()));
if (bestScore > 0)
{
// We were able to include the current bit, and we already found
// the optimal permutation for lower bits. We do not need to
// continue this loop, and we have our final score for this bit.
break;
}
// If we reach this point, we could not include the current bit, so
// we'll now try the next one
}
// Update the global constraints and return the score
a2bConstraints = a2bBest;
return bestScore;
}
uvec solvePermuteLess(const uvec& a, uvec& b)
{
// For each bit, find all values in `a` where it's set and in `b` where
// it's not set. We know that these are the only values we'd be interested
// in pairing in the end.
const uint BITSIZE = 32;
const size_t N = a.size();
std::unordered_map<uint, std::vector<size_t>> aSetMap;
std::unordered_map<uint, std::vector<size_t>> bUnsetMap;
for (uint bit = 0; bit < BITSIZE; ++bit)
{
for (size_t i = 0; i < N; ++i)
{
uint aiBit = (a[i] >> bit) & 0x1;
if (aiBit == 1)
{
aSetMap[bit].push_back(i);
}
uint biBit = (b[i] >> bit) & 0x1;
if (biBit == 0)
{
bUnsetMap[bit].push_back(i);
}
}
}
// Find which bits could possibly be set
uint upperBoundResult = 0;
uvec possibleBits;
for (uint bit = 0; bit < BITSIZE; ++bit)
{
if (aSetMap[bit].size() == bUnsetMap[bit].size())
{
upperBoundResult += 1u << bit;
possibleBits.push_back(bit);
}
}
// State the upper bound on the result, if we assume all `possibleBits` are
// set
std::cout << "Upper bound on result: " << upperBoundResult << "\n";
std::cout << "Possible set bits (LSB = 0): [ ";
for (uint bit : possibleBits)
{
std::cout << bit << " ";
}
std::cout << "]\n";
// If there's no hope, just return the original b
if (possibleBits.empty())
{
return b;
}
// Also state a lower bound on the result, namely the MSB
std::cout << "Lower bound on result: " << (1u << possibleBits.back()) << "\n";
// Iterate through all permutations of possibilities for each bit, starting
// with the MSB (which we know will be part of our solution)
uint bestScore = 0;
uvec c = b;
std::vector<size_t> aSet = aSetMap[possibleBits.back()];
std::vector<size_t> bUnset = bUnsetMap[possibleBits.back()];
std::sort(bUnset.begin(), bUnset.end());
do
{
// So far, we are unconstrained with what would be aUnset and bSet, but
// these might be constrained by later bits. Build the constraints
// mapping indices of a to indices of b. Currently unconstrained
// mappings will be treated as wildcards until further constraints are
// made for lower bits.
std::unordered_map<size_t, size_t> a2b;
for (size_t i = 0; i < aSet.size(); ++i)
{
a2b[aSet[i]] = bUnset[i];
}
// Recursively check permutations of lower bits
uint score = (1u << possibleBits.back())
+ recursiveVerification(1, a2b, possibleBits, aSetMap, bUnsetMap);
// If the current permutation outperformed the previous best (or if
// this is the first permutation), update the global results
if (score > bestScore)
{
bestScore = score;
// Build c using the mappings
c = uvec(N);
std::unordered_set<size_t> aUnmappedIndices(N);
std::unordered_set<size_t> bUnmappedIndices(N);
for (size_t j = 0; j < N; ++j)
{
aUnmappedIndices.insert(j);
bUnmappedIndices.insert(j);
}
for (auto it = a2b.cbegin(); it != a2b.cend(); ++it)
{
c[it->first] = b[it->second];
aUnmappedIndices.erase(it->first);
bUnmappedIndices.erase(it->second);
}
// For unconstrained mappings, use arbitrary ordering
for (auto ai = aUnmappedIndices.begin(), bi = bUnmappedIndices.begin(); ai != aUnmappedIndices.end(); ++ai, ++bi)
{
c[*ai] = b[*bi];
}
// If we achieved the upper bound result (all bits set), we know we
// can't do any better; so we might as well stop searching
if (bestScore == upperBoundResult)
{
break;
}
}
} while (std::next_permutation(bUnset.begin(), bUnset.end()));
return c;
}
狄龙的回答已经有了最重要的思想。利用这些思路，我们可以在线性时间和space.
内解决问题
关键目标是使结果的高位有效位 1，无论我们是否牺牲低位有效位。如果我们专注于单个位 k，那么我们可以执行以下操作：
- 将
a 中的第 k 位设置为 1 (a1) 和 0 (a0), 分别
- 将
b 中的第 k 位设置为 1 (b1) 和 0 (b0), 分别
- 如果
a1中的条目数等于b0中的条目数，我们可以将结果中的第k位设置为1。在这种情况下，我们认为分区成功。
分区具有以下含义：在我们的最终 c 中，我们需要将 a1 的条目与 b0 的条目和 [=22= 的条目进行匹配] 到 b1。如果我们这样做，XOR 运算将导致所有条目的 1，而 AND 运算将产生总体 1.
不，我们如何在算法中使用这种洞察力？
我选择用索引来表示 a 的分区（即，分区是一组索引集），用实际数字来表示 b 的分区。最初，我们从每个只有一个集合的分区开始（即，a 的分区具有所有索引的集合，b 的分区具有 b 作为元素）。
我们从最高位开始并尝试进行分区。
如果分区成功，我们最终会得到两个 a 和 b 的分区（其中一个可能是空的）。然后我们已经知道可以将 b 中的哪些数字放在哪些索引处。如果我们违反这个结果，我们会得到一个较小的最终结果。
如果我们的分区不成功，我们就直接忽略这一步。
现在让我们继续下一步。我们可能已经有了一个分区，它不仅有初始集，还有更细粒度的东西。我们不想混淆分区。因此，我们可以使用与以前相同的方法对分区进行分区。如果我们对所有分区都成功，我们从现在开始使用子分区。如果没有，我们使用原来的分区。
如果我们对所有位都这样做，我们最终会得到 b 中数字的映射以及它们可以放置的索引以获得最大的最终结果。它可能不是唯一的映射。如果分区包含多个元素，则任何映射都将产生最大值。所以我们只需要选择一个并得到结果。
这是您问题中的一个例子：
a = { 1, 11, 7, 4, 10, 11 }
= { 0001b, 1011b, 0111b, 0100b, 1010b, 1011b }
b = { 6, 20, 8, 9, 10, 7 }
= { 0110b, 10100b, 1000b, 1001b, 1010b, 0111b }
下面是最重要的算法步骤：
index partitioning | b partitioning
-----------+------------------------+-----------------------
initial | { 0, 1, 2, 3, 4, 5 } | {6, 20, 8, 9, 10, 7 }
------------+------------------------+-----------------------
after bit 3 | { 1, 4, 5 } | { 6, 20, 7 }
| { 0, 2, 3 } | { 8, 9, 10 }
------------+------------------------+-----------------------
after bit 0 | { 1, 5 } | { 6, 20 }
(final) | { 4 } | { 7 }
| { 0, 2 } | { 8, 10 }
| { 3 } | { 9 }
所以我们有一个非独特的案例。数字 6 和 20 可以同时出现在索引 1 和 5 处。但是数字 7 肯定会出现在索引 4 处。一种解决方案是：
c = { 8, 6, 10, 9, 7, 20 }
正在检查：
a = { 0001b, 1011b, 0111b, 0100b, 1010b, 1011b }
XOR
c = { 1000b, 0110b, 1010b, 1001b, 0111b, 10100b }
-------------------------------------------------
{ 1001b, 1101b, 1101b, 1101b, 1101b, 11111b }
AND = 1001b = 9
这里是一些示例 C++ 代码。请注意，代码的重点是可理解性。有一些事情可以更有效地实施。
#include <iostream>
#include <vector>
#include <cstdint>
struct Partition
{
std::vector<size_t> indices;
std::vector<uint32_t> bs;
};
struct Partitioning
{
bool success;
Partition p1;
Partition p2;
};
Partitioning partition(const std::vector<uint32_t>& a, const std::vector<size_t>& indices, const std::vector<uint32_t>& b, size_t bit)
{
uint32_t mask = 1 << bit;
Partitioning result;
// partition the indices of a
for (size_t i : indices)
{
uint32_t n = a[i];
if (n & mask)
result.p1.indices.push_back(i);
else
result.p2.indices.push_back(i);
}
// partition b
for (uint32_t n : b)
if (n & mask)
result.p2.bs.push_back(n);
else
result.p1.bs.push_back(n);
// check if we are successful
bool canMakeBit1 = result.p1.indices.size() == result.p1.bs.size();
result.success = canMakeBit1;
return result;
}
void findMax(const std::vector<uint32_t>& a, const std::vector<uint32_t>& b)
{
std::vector<uint32_t> aIndices(a.size());
for (size_t i = 0; i < a.size(); ++i)
aIndices[i] = i;
// current partitioning
std::vector<std::vector<uint32_t>> partsIndices;
partsIndices.push_back(aIndices);
std::vector<std::vector<uint32_t>> partsBs;
partsBs.push_back(b);
// temporary partitionings
std::vector<Partitioning> partitionings;
// assume 32 bits
size_t bit = 32;
do
{
--bit;
bool success = true;
partitionings.clear();
// try to partition all current partitions
for (size_t i = 0; i < partsIndices.size(); ++i)
{
partitionings.push_back(partition(a, partsIndices[i], partsBs[i], bit));
if (!partitionings.back().success)
{
success = false;
break;
}
}
// if all partitionings are successful
if (success)
{
// replace the current partitioning with the new one
partsIndices.clear();
partsBs.clear();
for (auto& p : partitionings)
{
if (p.p1.indices.size() > 0)
{
partsIndices.push_back(p.p1.indices);
partsBs.push_back(p.p1.bs);
}
if (p.p2.indices.size() > 0)
{
partsIndices.push_back(p.p2.indices);
partsBs.push_back(p.p2.bs);
}
}
}
} while (bit > 0);
// Generate c
std::vector<uint32_t> c(a.size());
for (size_t i = 0; i < partsIndices.size(); ++i)
{
const auto& indices = partsIndices[i];
const auto& bs = partsBs[i];
for (size_t j = 0; j < indices.size(); ++j)
{
c[indices[j]] = bs[j];
}
}
// Print the result
uint32_t result = 0xffffffff;
for (size_t i = 0; i < a.size(); ++i)
{
std::cout << c[i] << " ";
result = result & (a[i] ^ c[i]);
}
std::cout << std::endl << result << std::endl;
}
int main()
{
std::vector<uint32_t> a = { 1, 11, 7, 4, 10, 11 };
std::vector<uint32_t> b = { 6, 20, 8, 9, 10, 7 };
findMax(a, b);
return 0;
}
问题
我们给出了 2 个长度为 n 的数组 a 和 b。我们通过重新排列 b 中的值来构建第三个数组 c。目标是找到最大化
c
result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])
其中 ^ 是 XOR，& 是 AND。
是否可以有效地做到这一点？迭代b的所有可能排列很简单，但这对于大n是不可行的。
更多详情
a中值的顺序是固定的。b中值的顺序可以重新排列以形成c。即以b = [1, 2, 3]开头，可能是重新排列为c = [2, 1, 3]. 时得到的结果最大
如果需要，b可以就地重新排列（我在示例代码中这样做）。- 由于最佳
c不一定是唯一的，因此可以返回任何最佳c。 - 假设所有值都是 32 位无符号整数。
1 <= n <= 10,000.
测试用例
Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)
Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)
Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)
示例代码
这是我用于天真的解决方案的 C++ 代码，它详尽地尝试了 b 的所有排列（在 Windows 10 和 Visual Studio 2019 上测试）：
#include <algorithm> // next_permutation
#include <cstdint> // uint32_t
#include <iostream> // i/o
#include <vector> // vector
using uint = std::uint32_t;
using uvec = std::vector<uint>;
uint andxor(const uvec& a, const uvec& c)
{
// Start with all bits set
uint result = -1;
for (std::size_t i = 0; i < c.size(); ++i)
{
result &= a[i] ^ c[i];
}
return result;
}
uvec solvePermute(const uvec& a, uvec& b)
{
// next_permutation expects a pre-sorted input
std::sort(b.begin(), b.end());
// Initialize the result with the first permutation of b
uvec c = b;
uint bestResult = andxor(a, c);
// Try all permutations of b to maximize the result of andxor
while (std::next_permutation(b.begin(), b.end()))
{
uint result = andxor(a, b);
if (result > bestResult)
{
bestResult = result;
c = b;
}
}
return c;
}
int main()
{
// First test case
uvec a{ 3, 4, 5 };
uvec b{ 6, 7, 8 };
uvec c = solvePermute(a, b);
uint bestResult = andxor(a, c);
std::cout << "Maximum result is " << bestResult << " with c = ";
for (uint ci : c)
{
std::cout << ci << " ";
}
return 0;
}
TL;DR
我认为可以将其重新表述为 assignment problem，可以在 O(n^3) 时间内找到最佳解决方案。但我没有在我的回答中尝试这样做。
免责声明
我将要描述的方法仍然涉及检查排列。它通常似乎比原始方法需要更少的迭代，但我的解决方案的额外开销实际上可能会降低整体速度。我没有将我的方法的运行时间与天真的方法进行比较，我也没有详尽地检查它是否没有错误（对于提供的 3 个测试用例它似乎工作正常）。
话虽如此，我在此过程中确实有了一些见解，所以也许我的尝试会帮助其他人提出更有效的解决方案。希望我的解释是清楚的，我不是在胡说八道。
总体思路
假设我们创建一个无向的bipartite graph，其中两组独立的节点分别对应a和b，每个节点都是一个数组元素
让我们一次考虑一位，比如最低有效位 (LSB)。 我们将 LSB 标记为位 0。 我们还考虑第一个测试用例（为了简单起见，我们只考虑最低的 4 位而不是全部 32 位）：
Input:
a = [3, 4, 5] // binary: [0011, 0100, 0101]
b = [6, 7, 8] // binary: [0110, 0111, 1000]
我们的图表在 a 集合中有 3 个节点，标记为 3、4 和 5；它在 b 集合中有 3 个节点，分别标记为 6、7 和 8。如果 a 节点的所选位（位 0）与b 节点。例如，我们会在节点 3 和 6 之间画一条边，因为 3 的 LSB (0011) 与 6 的 LSB (0110).我们不会在节点 3 和节点 7 之间画一条边，因为 3 (0011) 的 LSB 与 7 (0111[=109) 的 LSB 相同=]).如果我们一直解决这个问题，我们最终会得到以下位 0 的邻接列表：
3: 6, 8
4: 7
5: 6, 8
我们有两组边，可以从 a 中的每个节点组成：
- 如果所选位为 1，则在
b中所选位为 0 的所有节点绘制一条边。 - 如果所选位为 0，则在
b中所选位为 1 的所有节点绘制一条边。
我们可以观察到，当且仅当该位为 1 的 a 个节点的数量与 b 个该位为 0 的节点。否则，该位在最终结果中不能为 1，因为我们必须将至少一个 a 节点与具有相同位值的 b 配对节点，在 XOR 之后为该位生成 0，因此在 AND 之后为该位生成 0。
现在，如果我们为 4 位中的每一位创建这样一个图，并确定最终结果中哪些位是 1 的候选位，这将为我们提供最佳结果的上限。这也为我们提供了一个明显的结果下限，因为我们知道我们至少可以找到 b 的排序，从而导致设置最重要的候选位。
下面给出了我们测试用例中每个位的邻接表。
Bit 0 (LSB)
3: 6, 8
4: 7
5: 6, 8
(candidate bit)
Bit 1
3: 8
4: 6, 7
5: 6, 7
(candidate bit)
Bit 2
3: 6, 7
4: 8
5: 8
(NOT candidate)
Bit 3 (MSB)
3: 8
4: 8
5: 8
(NOT candidate)
Upper bound: 3 (both candidate bits 0 and 1 are set)
Lower bound: 2 (only candidate bit 1 is set)
寻找 c
为了得到最优的c，我们需要从最高有效位开始。我们遍历所有有效的 cs（b 的排列，我们遵守该位的邻接列表），与 [= 的可能排列总数相比，希望其中的排列相对较少15=].
对于这些排列中的每一个，我们看看它们中的任何一个对于下一个最重要的候选位是否有效。如果其中 none 个是，那么我们检查之后的位，依此类推。如果在遵守邻接表的情况下，对于 MSB 上的任何排列，都不能包含其他位，那么最终结果中只有 MSB 可以为 1，这就是解决方案。否则，我们希望优先考虑对更重要的位起作用的排列，并且我们需要递归地检查对所有位有效的排列直到那个点。
排列“有效”是什么意思？本质上，邻接表充当了从 a 到 c 映射的约束。如果一个候选位的约束与另一个候选位的约束不冲突，我们知道这些位 can 在最终结果中都为 1。例如，查看位 0 和 1，我们看到有一种方法可以同时满足这两种映射（即 3: 8; 4: 7; 5: 6）。因此，该排列 (c = [8, 7, 6]) 对位 0 和 1 均有效。（事实上，该排列被证明是最佳排列。）
作为约束冲突的例子，考虑位 0 和位 2。位 2 要求节点 4 连接到节点 8。也就是说，在满足 a[i] == 4 的索引 i 处，我们需要设置 c[i] = 8 以便在最终结果中设置位 2。但是，bit 0 要求节点 4 连接到节点 7。这是一个冲突，因此不能在最终结果中同时设置 bit 0 和 bit 2。 （但是位 2 无论如何都不是候选位，因为 a 节点中的两个（4 和 5）的那个位为 1，但 b 节点（8）中只有一个为 0对于那一点。）
与已解决的图论问题的可能关系
我不是很熟悉图论问题，但在我看来这个问题的二分图公式与 最大加权二分匹配 也称为assignment problem。不过，我们的边缘目前没有加权。也许一条边可以根据它存在的位数来加权？也许更大的权重会被赋予更重要的位？我认为我们仍然只需要考虑来自候选位的图表。
本质上，从每个候选位的二部图构建一个nxn邻接矩阵。给边分配统一的权重pow(2, bit)；所以边缘权重对于位 0 为 1，对于位 1 为 2，对于位 2 为 4，依此类推。这确保了更重要的候选位优先于更小的候选位的任何组合。然后组合所有邻接矩阵的权重以构建最终的代表性邻接矩阵。这将是分配问题的输入。
如果此比较有效，则存在 Hungarian algorithm 可以在 O(n^3) 时间内最优地解决分配问题。这明显优于朴素排列方法所需的 O(n!) 时间。
乱码
为了完整起见，我包括了我为我提出的方法编写的代码，尽管我认为更值得研究将此问题重新表述为分配问题的可能性。要使用此代码，请从问题中提供的示例代码开始并将此代码复制到同一文件中。在 main 中，调用 solvePermuteLess 而不是 solvePermute.
#include <unordered_map>
#include <unordered_set>
uint recursiveVerification(size_t currentBit,
std::unordered_map<size_t, size_t>& a2bConstraints,
const uvec& possibleBits,
const std::unordered_map<uint, std::vector<size_t>>& aSetMap,
const std::unordered_map<uint, std::vector<size_t>>& bUnsetMap)
{
uint bestScore = 0;
std::unordered_map<size_t, size_t> a2bBest = a2bConstraints;
uint upperBoundScore = 0;
for (uint bit = currentBit; bit < possibleBits.size(); ++bit)
{
upperBoundScore += 1u << possibleBits[possibleBits.size() - bit - 1];
}
for (size_t bit = currentBit; bit < possibleBits.size(); ++bit)
{
uint bitValue = possibleBits[possibleBits.size() - bit - 1];
std::vector<size_t> aSet = aSetMap.at(bitValue);
std::vector<size_t> bUnset = bUnsetMap.at(bitValue);
std::sort(bUnset.begin(), bUnset.end());
do
{
// Set up necessary mappings for this permutation
std::unordered_map<size_t, size_t> a2b;
for (size_t i = 0; i < aSet.size(); ++i)
{
a2b[aSet[i]] = bUnset[i];
}
// Check for conflicts in mappings
bool hasConflicts = false;
for (auto jt = a2bConstraints.cbegin(); jt != a2bConstraints.cend(); ++jt)
{
auto findIt = a2b.find(jt->first);
if (findIt != a2b.end())
{
// The same value in `a` is being mapped. Make sure it's to
// the same value in `b`.
if (findIt->second != jt->second)
{
// Not mapped to same value; invalid permutation
hasConflicts = true;
break;
}
}
}
if (hasConflicts)
{
// We found conflicting mappings; try the next permutation
continue;
}
// If we reach this point, there were no mapping conflicts. We know
// this bit can be set alongside the parent bit. Merge the
// constraints and then try the next bit.
for (auto jt = a2bConstraints.cbegin(); jt != a2bConstraints.cend(); ++jt)
{
a2b[jt->first] = jt->second;
}
// Recursively check permutations of lower bits
uint score = (1u << bitValue)
+ recursiveVerification(bit + 1, a2b, possibleBits, aSetMap, bUnsetMap);
// Now a2b contains the best-performing mapping for this
// permutation. Track the best mapping across all permutations.
if (score > bestScore)
{
bestScore = score;
a2bBest = a2b;
// If we achieve the upper-bound result (all bits set), we know
// we can't do any better; so stop early
if (bestScore == upperBoundScore)
{
break;
}
}
} while (std::next_permutation(bUnset.begin(), bUnset.end()));
if (bestScore > 0)
{
// We were able to include the current bit, and we already found
// the optimal permutation for lower bits. We do not need to
// continue this loop, and we have our final score for this bit.
break;
}
// If we reach this point, we could not include the current bit, so
// we'll now try the next one
}
// Update the global constraints and return the score
a2bConstraints = a2bBest;
return bestScore;
}
uvec solvePermuteLess(const uvec& a, uvec& b)
{
// For each bit, find all values in `a` where it's set and in `b` where
// it's not set. We know that these are the only values we'd be interested
// in pairing in the end.
const uint BITSIZE = 32;
const size_t N = a.size();
std::unordered_map<uint, std::vector<size_t>> aSetMap;
std::unordered_map<uint, std::vector<size_t>> bUnsetMap;
for (uint bit = 0; bit < BITSIZE; ++bit)
{
for (size_t i = 0; i < N; ++i)
{
uint aiBit = (a[i] >> bit) & 0x1;
if (aiBit == 1)
{
aSetMap[bit].push_back(i);
}
uint biBit = (b[i] >> bit) & 0x1;
if (biBit == 0)
{
bUnsetMap[bit].push_back(i);
}
}
}
// Find which bits could possibly be set
uint upperBoundResult = 0;
uvec possibleBits;
for (uint bit = 0; bit < BITSIZE; ++bit)
{
if (aSetMap[bit].size() == bUnsetMap[bit].size())
{
upperBoundResult += 1u << bit;
possibleBits.push_back(bit);
}
}
// State the upper bound on the result, if we assume all `possibleBits` are
// set
std::cout << "Upper bound on result: " << upperBoundResult << "\n";
std::cout << "Possible set bits (LSB = 0): [ ";
for (uint bit : possibleBits)
{
std::cout << bit << " ";
}
std::cout << "]\n";
// If there's no hope, just return the original b
if (possibleBits.empty())
{
return b;
}
// Also state a lower bound on the result, namely the MSB
std::cout << "Lower bound on result: " << (1u << possibleBits.back()) << "\n";
// Iterate through all permutations of possibilities for each bit, starting
// with the MSB (which we know will be part of our solution)
uint bestScore = 0;
uvec c = b;
std::vector<size_t> aSet = aSetMap[possibleBits.back()];
std::vector<size_t> bUnset = bUnsetMap[possibleBits.back()];
std::sort(bUnset.begin(), bUnset.end());
do
{
// So far, we are unconstrained with what would be aUnset and bSet, but
// these might be constrained by later bits. Build the constraints
// mapping indices of a to indices of b. Currently unconstrained
// mappings will be treated as wildcards until further constraints are
// made for lower bits.
std::unordered_map<size_t, size_t> a2b;
for (size_t i = 0; i < aSet.size(); ++i)
{
a2b[aSet[i]] = bUnset[i];
}
// Recursively check permutations of lower bits
uint score = (1u << possibleBits.back())
+ recursiveVerification(1, a2b, possibleBits, aSetMap, bUnsetMap);
// If the current permutation outperformed the previous best (or if
// this is the first permutation), update the global results
if (score > bestScore)
{
bestScore = score;
// Build c using the mappings
c = uvec(N);
std::unordered_set<size_t> aUnmappedIndices(N);
std::unordered_set<size_t> bUnmappedIndices(N);
for (size_t j = 0; j < N; ++j)
{
aUnmappedIndices.insert(j);
bUnmappedIndices.insert(j);
}
for (auto it = a2b.cbegin(); it != a2b.cend(); ++it)
{
c[it->first] = b[it->second];
aUnmappedIndices.erase(it->first);
bUnmappedIndices.erase(it->second);
}
// For unconstrained mappings, use arbitrary ordering
for (auto ai = aUnmappedIndices.begin(), bi = bUnmappedIndices.begin(); ai != aUnmappedIndices.end(); ++ai, ++bi)
{
c[*ai] = b[*bi];
}
// If we achieved the upper bound result (all bits set), we know we
// can't do any better; so we might as well stop searching
if (bestScore == upperBoundResult)
{
break;
}
}
} while (std::next_permutation(bUnset.begin(), bUnset.end()));
return c;
}
狄龙的回答已经有了最重要的思想。利用这些思路，我们可以在线性时间和space.
内解决问题关键目标是使结果的高位有效位 1，无论我们是否牺牲低位有效位。如果我们专注于单个位 k，那么我们可以执行以下操作：
- 将
a中的第k位设置为1(a1) 和0(a0), 分别 - 将
b中的第k位设置为1(b1) 和0(b0), 分别 - 如果
a1中的条目数等于b0中的条目数，我们可以将结果中的第k位设置为1。在这种情况下，我们认为分区成功。
分区具有以下含义：在我们的最终 c 中，我们需要将 a1 的条目与 b0 的条目和 [=22= 的条目进行匹配] 到 b1。如果我们这样做，XOR 运算将导致所有条目的 1，而 AND 运算将产生总体 1.
不，我们如何在算法中使用这种洞察力？
我选择用索引来表示 a 的分区（即，分区是一组索引集），用实际数字来表示 b 的分区。最初，我们从每个只有一个集合的分区开始（即，a 的分区具有所有索引的集合，b 的分区具有 b 作为元素）。
我们从最高位开始并尝试进行分区。
如果分区成功，我们最终会得到两个 a 和 b 的分区（其中一个可能是空的）。然后我们已经知道可以将 b 中的哪些数字放在哪些索引处。如果我们违反这个结果，我们会得到一个较小的最终结果。
如果我们的分区不成功，我们就直接忽略这一步。
现在让我们继续下一步。我们可能已经有了一个分区，它不仅有初始集，还有更细粒度的东西。我们不想混淆分区。因此，我们可以使用与以前相同的方法对分区进行分区。如果我们对所有分区都成功，我们从现在开始使用子分区。如果没有，我们使用原来的分区。
如果我们对所有位都这样做，我们最终会得到 b 中数字的映射以及它们可以放置的索引以获得最大的最终结果。它可能不是唯一的映射。如果分区包含多个元素，则任何映射都将产生最大值。所以我们只需要选择一个并得到结果。
这是您问题中的一个例子：
a = { 1, 11, 7, 4, 10, 11 }
= { 0001b, 1011b, 0111b, 0100b, 1010b, 1011b }
b = { 6, 20, 8, 9, 10, 7 }
= { 0110b, 10100b, 1000b, 1001b, 1010b, 0111b }
下面是最重要的算法步骤：
index partitioning | b partitioning
-----------+------------------------+-----------------------
initial | { 0, 1, 2, 3, 4, 5 } | {6, 20, 8, 9, 10, 7 }
------------+------------------------+-----------------------
after bit 3 | { 1, 4, 5 } | { 6, 20, 7 }
| { 0, 2, 3 } | { 8, 9, 10 }
------------+------------------------+-----------------------
after bit 0 | { 1, 5 } | { 6, 20 }
(final) | { 4 } | { 7 }
| { 0, 2 } | { 8, 10 }
| { 3 } | { 9 }
所以我们有一个非独特的案例。数字 6 和 20 可以同时出现在索引 1 和 5 处。但是数字 7 肯定会出现在索引 4 处。一种解决方案是：
c = { 8, 6, 10, 9, 7, 20 }
正在检查：
a = { 0001b, 1011b, 0111b, 0100b, 1010b, 1011b }
XOR
c = { 1000b, 0110b, 1010b, 1001b, 0111b, 10100b }
-------------------------------------------------
{ 1001b, 1101b, 1101b, 1101b, 1101b, 11111b }
AND = 1001b = 9
这里是一些示例 C++ 代码。请注意，代码的重点是可理解性。有一些事情可以更有效地实施。
#include <iostream>
#include <vector>
#include <cstdint>
struct Partition
{
std::vector<size_t> indices;
std::vector<uint32_t> bs;
};
struct Partitioning
{
bool success;
Partition p1;
Partition p2;
};
Partitioning partition(const std::vector<uint32_t>& a, const std::vector<size_t>& indices, const std::vector<uint32_t>& b, size_t bit)
{
uint32_t mask = 1 << bit;
Partitioning result;
// partition the indices of a
for (size_t i : indices)
{
uint32_t n = a[i];
if (n & mask)
result.p1.indices.push_back(i);
else
result.p2.indices.push_back(i);
}
// partition b
for (uint32_t n : b)
if (n & mask)
result.p2.bs.push_back(n);
else
result.p1.bs.push_back(n);
// check if we are successful
bool canMakeBit1 = result.p1.indices.size() == result.p1.bs.size();
result.success = canMakeBit1;
return result;
}
void findMax(const std::vector<uint32_t>& a, const std::vector<uint32_t>& b)
{
std::vector<uint32_t> aIndices(a.size());
for (size_t i = 0; i < a.size(); ++i)
aIndices[i] = i;
// current partitioning
std::vector<std::vector<uint32_t>> partsIndices;
partsIndices.push_back(aIndices);
std::vector<std::vector<uint32_t>> partsBs;
partsBs.push_back(b);
// temporary partitionings
std::vector<Partitioning> partitionings;
// assume 32 bits
size_t bit = 32;
do
{
--bit;
bool success = true;
partitionings.clear();
// try to partition all current partitions
for (size_t i = 0; i < partsIndices.size(); ++i)
{
partitionings.push_back(partition(a, partsIndices[i], partsBs[i], bit));
if (!partitionings.back().success)
{
success = false;
break;
}
}
// if all partitionings are successful
if (success)
{
// replace the current partitioning with the new one
partsIndices.clear();
partsBs.clear();
for (auto& p : partitionings)
{
if (p.p1.indices.size() > 0)
{
partsIndices.push_back(p.p1.indices);
partsBs.push_back(p.p1.bs);
}
if (p.p2.indices.size() > 0)
{
partsIndices.push_back(p.p2.indices);
partsBs.push_back(p.p2.bs);
}
}
}
} while (bit > 0);
// Generate c
std::vector<uint32_t> c(a.size());
for (size_t i = 0; i < partsIndices.size(); ++i)
{
const auto& indices = partsIndices[i];
const auto& bs = partsBs[i];
for (size_t j = 0; j < indices.size(); ++j)
{
c[indices[j]] = bs[j];
}
}
// Print the result
uint32_t result = 0xffffffff;
for (size_t i = 0; i < a.size(); ++i)
{
std::cout << c[i] << " ";
result = result & (a[i] ^ c[i]);
}
std::cout << std::endl << result << std::endl;
}
int main()
{
std::vector<uint32_t> a = { 1, 11, 7, 4, 10, 11 };
std::vector<uint32_t> b = { 6, 20, 8, 9, 10, 7 };
findMax(a, b);
return 0;
}