TL;DR
I think it's possible to reformulate this as an assignment problem, for which the optimal solution can be found in O(n^3) time. But I did not attempt this in my answer.
Disclaimer
The approach I'll be describing still involves checking permutations. It generally seems to require fewer iterations than the naive approach, but the additional overhead of my solution might actually slow it down overall. I have not compared the runtime of my approach to the naive approach, and I have not exhaustively checked to see if it's free of errors (it seems to work fine for the 3 provided test cases).
That said, I did have some insights along the way, so maybe my attempt at this will help someone else come up with a more efficient solution. Hopefully my explanation is clear and I'm not just rambling.
General idea
Imagine we create an undirected bipartite graph where the two independent sets of nodes correspond to a and b, and each node is an array element.
Let's consider one bit at a time, say, the least-significant bit (LSB).
We'll label the LSB as bit 0.
Let's also consider the first test case (and for simplicity, we'll only consider the lowest 4 bits instead of all 32):
Input:
a = [3, 4, 5] // binary: [0011, 0100, 0101]
b = [6, 7, 8] // binary: [0110, 0111, 1000]
Our graph has 3 nodes in the a set labelled 3, 4, and 5; and it has 3 nodes in the b set labelled 6, 7, and 8. We draw an edge between nodes if the chosen bit (bit 0) of the a node is different from the chosen bit of the b node. For example, we would draw an edge between nodes 3 and 6, because the LSB of 3 (0011) is different from the LSB of 6 (0110). We would not draw an edge between nodes 3 and 7, because the LSB of 3 (0011) is the same as the LSB of 7 (0111). If we work this out all the way, we end up with the following adjacency list for bit 0:
3: 6, 8
4: 7
5: 6, 8
We have two sets of edges that can be made from each node in a:
- If the chosen bit is 1, draw an edge to all nodes in
b where the chosen bit is 0.
- If the chosen bit is 0, draw an edge to all nodes in
b where the chosen bit is 1.
We can observe that the chosen bit could potentially be 1 in the final, optimal result if and only if the number of a nodes for which that bit is 1 is the same as the number of b nodes for which that bit is 0. Otherwise, that bit cannot be 1 in the final result, as we would have to pair at least one a node with a same-bit-valued b node, producing 0 for that bit after XOR and thus 0 for that bit after AND.
Now, if we create such a graph for each of the 4 bits and determine which bits are candidates for being 1 in the final result, this gives us an upper bound on the optimal result. This also gives us an obvious lower bound on the result, as we know we could at least find an ordering of b that results in the most-significant candidate bit being set.
The adjacency lists for each bit in our test case are given below.
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)
Finding c
To get the optimal c, we need to start with the most-significant candidate bit. We loop through all valid cs (permutations of b where we adhere to the adjacency list for that bit), of which there would hopefully be relatively few compared to the total number of possible permutations of b.
For each of these permutations, we see if any of them are valid for the next-most-significant candidate bit. If none of them are, then we check the bit after that, and so on. If no other bit can be included while adhering to the adjacency list for any permutation on the MSB, then only the MSB can be 1 in the final result and that's the solution. Otherwise, we want to prioritize permutations that work for bits that are more significant, and we need to recursively check the permutations that are valid for all bits up to that point.
What does it mean for a permutation to be "valid"? Essentially, the adjacency list acts as a constraint on the mapping from a to c. If the constraints of one candidate bit do not conflict with those of another candidate bit, we know those bits can both be 1 in the final result. For example, looking at bits 0 and 1, we see that there is a way to satisfy both of these mappings (namely, 3: 8; 4: 7; 5: 6). Therefore, that permutation (c = [8, 7, 6]) is valid for both bits 0 and 1. (And indeed, this permutation turns out to be the optimal one.)
For an example of conflicting constraints, consider bits 0 and 2. Bit 2 requires node 4 to be connected to node 8. That is, at index i which satisfies a[i] == 4, we need to set c[i] = 8 in order for bit 2 to be set in the final result. However, bit 0 requires node 4 to be connected to node 7. This is a conflict, so bits 0 and 2 cannot both be set in the final result. (But bit 2 wasn't a candidate bit anyway, because two of the a nodes (4 and 5) have a 1 for that bit but only one of the b nodes (8) has a 0 for that bit.)
Possible relation to solved graph theory problems
I'm not very familiar with graph theory problems, but it seems to me like this bipartite graph formulation of the problem is related to maximum weighted bipartite matching also known as the assignment problem. Though, our edges are currently unweighted. Maybe an edge could be weighted according to how many bits it exists for? Perhaps a greater weight would be given to more significant bits? I think we would still need to only consider graphs from candidate bits.
Essentially, build a nxn adjacency matrix from the bipartite graph of each candidate bit. Assign uniform weight pow(2, bit) to the edges; so edge weights are 1 for bit 0, 2 for bit 1, 4 for bit 2, and so on. This ensures that more significant candidate bits are preferred over any combination of lesser ones. Then combine the weights across all adjacency matrices to build the final representative adjacency matrix. This would be the input to the assignment problem.
If this comparison is valid, there is the Hungarian algorithm for optimally solving the assignment problem in O(n^3) time. This is significantly better than the O(n!) time needed for the naive permutations approach.
Messy code
For the sake of completeness, I'm including the code I wrote for my proposed approach, although I think it's more worthwhile investigating the potential of reformulating this problem as an assignment problem. To use this code, start from the sample code provided in the question and copy this code into the same file. Inside main, call solvePermuteLess instead of 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;
}
