Блог

Проблема

Нам даны 2 массива a , и b оба имеют длину n . Мы строим третий массив c , переставляя значения внутри b . Цель состоит в том, чтобы найти оптимальный c , который максимизирует

 result = (a[0] ^ c[0]) amp; (a[1] ^ c[1]) amp; ... amp; (a[n - 1] ^ c[n - 1])
 

где ^ XOR и amp; есть И.

Можно ли сделать это эффективно? Легко перебрать все возможные перестановки 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 uvecamp; a, const uvecamp; c)
{
    // Start with all bits set
    uint result = -1;

    for (std::size_t i = 0; i < c.size();   i)
    {
        result amp;= a[i] ^ c[i];
    }
    return resu<
}

uvec solvePermute(const uvecamp; a, uvecamp; 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 = resu<
            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;
}
 

В ответе Диллона уже есть самые важные идеи. Используя эти идеи, мы можем решить проблему в линейном времени и пространстве.

Ключевая цель состоит в том , чтобы сделать очень значимые биты результата 1 , независимо от того, жертвуем ли мы менее значимыми битами. Если мы сосредоточимся на одном бите k , то сможем сделать следующее:

• разделите числа, в a которых их k -й бит установлен в 1 ( a1 ) и 0 ( a0 ) соответственно
• разделите числа, в b которых их k -й бит установлен в 1 ( b1 ) и 0 ( b0 ) соответственно
• если количество записей в a1 равно числу входящих b0 , мы можем установить k -й бит в результате 1 равным . В этом случае мы считаем разделение успешным.

Разделы имеют следующее значение: В нашем финале c нам нужно сопоставить записи a1 to с записями b0 и записями a0 to b1 . Если мы сделаем это, операция XOR приведет 1 ко всем записям, а операция И приведет к общему 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>amp; a, const std::vector<size_t>amp; indices, const std::vector<uint32_t>amp; b, size_t bit)
{
    uint32_t mask = 1 << bit;

    Partitioning resu<

    // partition the indices of a
    for (size_t i : indices)
    {
        uint32_t n = a[i];
        if (n amp; mask)
            result.p1.indices.push_back(i);
        else
            result.p2.indices.push_back(i);
    }
    
    // partition b
    for (uint32_t n : b)
        if (n amp; 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 resu<
}

void findMax(const std::vector<uint32_t>amp; a, const std::vector<uint32_t>amp; 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 (autoamp; 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 autoamp; indices = partsIndices[i];
        const autoamp; 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 amp; (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;
}
 

TL;DR

Я думаю, что это можно переформулировать как задачу назначения, для которой оптимальное решение может быть найдено за O(n^3) времени. Но я не пытался сделать это в своем ответе.

Отказ от ответственности

Подход, который я буду описывать, по-прежнему включает проверку перестановок. Обычно кажется, что для этого требуется меньше итераций, чем для наивного подхода, но дополнительные накладные расходы моего решения могут фактически замедлить его в целом. Я не сравнивал время выполнения моего подхода с наивным подходом, и я не полностью проверил, свободен ли он от ошибок (похоже, он отлично работает для 3 предоставленных тестовых случаев).

Тем не менее, у меня были некоторые идеи на этом пути, так что, возможно, моя попытка помочь кому-то еще придумать более эффективное решение. Надеюсь, мое объяснение будет ясным, и я не просто бреду.

Общая идея

Представьте , что мы создаем неориентированный двудольный граф, где два независимых набора узлов соответствуют a и b , и каждый узел является элементом массива.

Давайте рассмотрим по одному биту за раз, скажем, наименее значимый бит (LSB). Мы обозначим LSB как бит 0. Давайте также рассмотрим первый тестовый случай (и для простоты мы рассмотрим только самые низкие 4 бита вместо всех 32).:

 Input:
a = [3, 4, 5]  // binary: [0011, 0100, 0101]
b = [6, 7, 8]  // binary: [0110, 0111, 1000]
 

Наш график имеет 3 узла в a наборе с метками 3, 4 и 5; и он имеет 3 узла в b наборе с метками 6, 7 и 8. Мы рисуем границу между узлами, если выбранный бит (бит 0) a узла отличается от выбранного бита b узла. Например, мы бы нарисовали ребро между узлами 3 и 6, потому что LSB 3 (001 1) отличается от LSB 6 (011 0). Мы бы не стали проводить границу между узлами 3 и 7, потому что LSB 3 (001 1) совпадает с LSB 7 (011 1). Если мы проработаем это до конца, мы получим следующий список смежности для бита 0:

 3: 6, 8
4: 7
5: 6, 8
 

We have two sets of edges that can be made from each node in a :

• Если выбранный бит равен 1, нарисуйте ребро для всех узлов, в b которых выбранный бит равен 0.
• Если выбранный бит равен 0, нарисуйте ребро для всех узлов, в b которых выбранный бит равен 1.

Мы можем заметить, что выбранный бит потенциально может быть равен 1 в конечном оптимальном результате тогда и только тогда, когда число a узлов, для которых этот бит равен 1, совпадает с числом b узлов, для которых этот бит равен 0. В противном случае этот бит не может быть равен 1 в конечном результате, так как нам пришлось бы связать по крайней мере один a узел с узлом с одинаковым битовым значением b , получив 0 для этого бита после XOR и, следовательно, 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 , нам нужно начать с наиболее значимого бита-кандидата. Мы перебираем все допустимые c s (перестановки b , в которых мы придерживаемся списка смежности для этого бита), которых, как мы надеемся, будет относительно немного по сравнению с общим количеством возможных перестановок b .

Для каждой из этих перестановок мы видим, действительны ли какие-либо из них для следующего по значимости бита-кандидата. Если ни один из них не является таковым, то мы проверяем бит после этого и так далее. Если никакой другой бит не может быть включен при соблюдении списка смежности для любой перестановки в MSB, то только MSB может быть 1 в конечном результате, и это решение. В противном случае мы хотим расставить приоритеты перестановок, которые работают для более значимых битов, и нам нужно рекурсивно проверить перестановки, которые действительны для всех битов до этого момента.

Что значит, чтобы перестановка была «действительной»? По сути, список смежности действует как ограничение на сопоставление от a до c . Если ограничения одного бита-кандидата не противоречат ограничениям другого бита-кандидата, мы знаем, что эти биты могут быть равны 1 в конечном результате. Например, глядя на биты 0 и 1, мы видим, что существует способ удовлетворить обоим этим отображениям (а именно, 3: 8; 4: 7; 5: 6 ). Следовательно, эта перестановка ( c = [8, 7, 6] ) справедлива как для битов 0, так и для 1. (И действительно, эта перестановка оказывается оптимальной).

В качестве примера конфликтующих ограничений рассмотрим биты 0 и 2. Бит 2 требует, чтобы узел 4 был подключен к узлу 8. То есть, при индексе i , который удовлетворяет a[i] == 4 , нам нужно установить c[i] = 8 , чтобы бит 2 был установлен в конечном результате. Однако бит 0 требует, чтобы узел 4 был подключен к узлу 7. Это конфликт, поэтому биты 0 и 2 не могут быть установлены в конечном результате. (Но бит 2 в любом случае не был битом-кандидатом, потому что два a узла (4 и 5) имеют 1 для этого бита, но только один из b узлов (8) имеет 0 для этого бита.)

Возможное отношение к решаемым задачам теории графов

Я не очень хорошо знаком с проблемами теории графов, но мне кажется, что эта двудольная графовая формулировка проблемы связана с максимальным взвешенным двудольным сопоставлением, также известным как проблема присвоения. Хотя наши границы в настоящее время невзвешены. Может быть, ребро можно было бы взвесить в зависимости от того, для скольких битов оно существует? Возможно, больший вес был бы придан более значимым битам? Я думаю, что нам все равно нужно было бы рассматривать только графики из битов-кандидатов.

По сути, постройте n n матрицу смежности x из двудольного графика каждого бита-кандидата. Назначьте ребрам одинаковый вес pow(2, bit) ; таким образом, вес ребер равен 1 для бита 0, 2 для бита 1, 4 для бита 2 и так далее. Это гарантирует, что более значимые биты-кандидаты предпочтительнее любой комбинации меньших. Затем объедините веса по всем матрицам смежности, чтобы построить окончательную репрезентативную матрицу смежности. Это было бы вкладом в проблему назначения.

Если это сравнение корректно, существует венгерский алгоритм оптимального решения задачи назначения за 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>amp; a2bConstraints,
    const uvecamp; possibleBits,
    const std::unordered_map<uint, std::vector<size_t>>amp; aSetMap,
    const std::unordered_map<uint, std::vector<size_t>>amp; 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 uvecamp; a, uvecamp; 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) amp; 0x1;
            if (aiBit == 1)
            {
                aSetMap[bit].push_back(i);
            }

            uint biBit = (b[i] >> bit) amp; 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;
}