Рубрики

Найти максимальное подмножество XOR данного набора

Дан набор натуральных чисел. найти максимальное значение подмножества XOR в данном наборе. Ожидаемая временная сложность O (n).

Примеры:

Input: set[] = {2, 4, 5}
Output: 7
The subset {2, 5} has maximum XOR value

Input: set[] = {9, 8, 5}
Output: 13
The subset {8, 5} has maximum XOR value

Input: set[] = {8, 1, 2, 12, 7, 6}
Output: 15
The subset {1, 2, 12} has maximum XOR value

Input: set[] = {4, 6}
Output: 6
The subset {6} has maximum XOR value

Обратите внимание, что эта проблема отличается от максимального значения XOR для подмассива . Здесь нам нужно найти подмножество вместо подмассива.

Простое решение — сгенерировать все возможные подмножества данного набора, найти XOR каждого подмножества и вернуть подмножество с максимальным XOR.

Ниже приведен эффективный алгоритм, который работает за O (n) времени.
Идея основана на следующих фактах:

  1. Число битов для представления всех элементов является фиксированным и составляет 32 бита для целого числа в большинстве компиляторов.
  2. Если максимальный элемент имеет старший значащий бит MSB в позиции i, то результат равен по крайней мере 2 i
1. Initialize index of chosen elements as 0. Let this index be 
   'index'
2. Traverse through all bits starting from most significant bit. 
   Let i be the current bit.
......(a) Find the maximum element with i'th bit set.  If there
          is no element with i'th bit set, continue to smaller 
          bit.  
......(b) Let the element with i'th bit set be maxEle and index
          of this element be maxInd. Place maxEle at 'index' and
          (by swapping set[index] and set[maxInd]) 
......(c) Do XOR of maxEle with all numbers having i'th  bit as set.
......(d) Increment index 
3. Return XOR of all elements in set[]. Note that set[] is modified
   in step 2.c.

Ниже приведена реализация этого алгоритма.

C ++

// C ++ программа для поиска
// максимальное подмножество XOR
#include<bits/stdc++.h>

using namespace std;

  
// Количество бит в
// представлять int
#define INT_BITS 32

  
// Функция для возврата
// максимальное подмножество XOR
// в наборе []

int maxSubarrayXOR(int set[], int n)

{

    // Инициализируем индекс

    // выбранные элементы

    int index = 0;

  

    // пройти через все

    // биты целого числа

    // начиная с самого

    // значащий бит (MSB)

    for (int i = INT_BITS-1; i >= 0; i--)

    {

        // Инициализируем индекс

        // максимальный элемент и

        // максимальный элемент

        int maxInd = index;

        int maxEle = INT_MIN;

        for (int j = index; j < n; j++)

        {

            // Если я установил бит [j]

            // установлено и установлено [j]

            // больше, чем макс.

            if ( (set[j] & (1 << i)) != 0 

                     && set[j] > maxEle )

                maxEle = set[j], maxInd = j;

        }

  

        // Если не было

        // элемент с i'th

        // бит установлен, перейти к

        // меньше я

        if (maxEle == INT_MIN)

        continue;

  

        // Поместить максимальный элемент

        // с установленным битом

        // по индексу 'index'

        swap(set[index], set[maxInd]);

  

        // Обновляем maxInd и

        // инкрементный индекс

        maxInd = index;

  

        // Делаем XOR из set [maxIndex]

        // со всеми номерами, имеющими

        // я бит как установлено.

        for (int j=0; j<n; j++)

        {

            // XOR установить [maxInd] те

            // числа, которые имеют

            // я установил бит

            if (j != maxInd &&

               (set[j] & (1 << i)) != 0)

                set[j] = set[j] ^ set[maxInd];

        }

  

        // Увеличение индекса

        // выбранные элементы

        index++;

    }

  

    // Окончательный результат

    // XOR всех элементов

    int res = 0;

    for (int i = 0; i < n; i++)

        res ^= set[i];

    return res;

}

  
// Драйвер программы

int main()

{

    int set[] = {9, 8, 5};

    int n = sizeof(set) / sizeof(set[0]);

      

    cout << "Max subset XOR is ";

    cout << maxSubarrayXOR(set, n);

    return 0;

}

Джава

// Java-программа для поиска
// максимальное подмножество XOR

import java.util.*;

  

class GFG {

      
// Количество бит в
// представлять int

static final int INT_BITS = 32;

  
// Функция для возврата
// максимальное подмножество XOR
// в наборе []

static int maxSubarrayXOR(int set[], int n)

{

    // Инициализируем индекс

    // выбранные элементы

    int index = 0;

  

    // пройти через все

    // биты целого числа

    // начиная с самого

    // значащий бит (MSB)

    for (int i = INT_BITS - 1; i >= 0; i--) 

    {

    // Инициализируем индекс

    // максимальный элемент и

    // максимальный элемент

    int maxInd = index;

    int maxEle = Integer.MIN_VALUE;

    for (int j = index; j < n; j++) {

          

        // Если я установил бит [j]

        // установлено и установлено [j]

        // больше, чем макс.

        if ((set[j] & (1 << i)) != 0 && set[j] > maxEle)

        {

        maxEle = set[j];

        maxInd = j;

        }

    }

  

    // Если не было

    // элемент с i'th

    // бит установлен, перейти к

    // меньше я

    if (maxEle == -2147483648)

        continue;

  

    // Поместить максимальный элемент

    // с установленным битом

    // по индексу 'index'

    int temp = set[index];

    set[index] = set[maxInd];

    set[maxInd] = temp;

  

    // Обновляем maxInd и

    // инкрементный индекс

    maxInd = index;

  

    // Делаем XOR из set [maxIndex]

    // со всеми номерами, имеющими

    // я бит как установлено.

    for (int j = 0; j < n; j++) {

          

        // XOR установить [maxInd] те

        // числа, которые имеют

        // я установил бит

        if (j != maxInd && (set[j] & (1 << i)) != 0)

        set[j] = set[j] ^ set[maxInd];

    }

  

    // Увеличение индекса

    // выбранные элементы

    index++;

    }

  

    // Окончательный результат

    // XOR всех элементов

    int res = 0;

    for (int i = 0; i < n; i++)

    res ^= set[i];

    return res;

}

  
// Код драйвера

public static void main(String arg[]) {

    int set[] = {9, 8, 5};

    int n = set.length;

  

    System.out.print("Max subset XOR is ");

    System.out.print(maxSubarrayXOR(set, n));

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python программа для поиска
# максимальное подмножество XOR

  
Количество бит в
# представляют int

INT_BITS=32

   
# Функция для возврата
# максимальное подмножество XOR
# в наборе []

def maxSubarrayXOR(set,n):

  

    # Инициализировать индекс

    # выбранные элементы

    index = 0

   

    # Пройдите через все

    # битов целого числа

    # начиная с самого

    # значащий бит (MSB)

    for i in range(INT_BITS-1,-1,-1):

      

        # Инициализировать индекс

        # максимальный элемент и

        # максимальный элемент

        maxInd = index

        maxEle = -2147483648

        for j in range(index,n):

          

            # Если я немного сета [j]

            # установлено и установлено [j]

            # больше, чем макс.

            if ( (set[j] & (1 << i)) != 0 

                     and set[j] > maxEle ):

                  

                maxEle = set[j]

                maxInd = j

          

        # Если бы не было

        # элемент с i'th

        # бит установлен, перейдите к

        # меньше я

        if (maxEle ==-2147483648):

            continue

   

        # Положить максимальный элемент

        # с установленным битом

        # по индексу 'index'

        temp=set[index]

        set[index]=set[maxInd]

        set[maxInd]=temp

   

        # Обновите maxInd и

        # индекс приращения

        maxInd = index

   

        # Делать XOR из набора [maxIndex]

        # со всеми номерами, имеющими

        # я немного как установлено.

        for j in range(n):

          

            # XOR установить [maxInd] те

            # числа, которые имеют

            # я установил бит

            if (j != maxInd and

               (set[j] & (1 << i)) != 0):

                set[j] = set[j] ^ set[maxInd]

          

   

        # Индекс приращения

        # выбранные элементы

        index=index + 1

      

   

    # Окончательный результат

    # XOR всех элементов

    res = 0

    for i in range(n):

        res =res ^ set[i]

    return res

  
# Код драйвера

  

set= [9, 8, 5]

n =len(set)

  

print("Max subset XOR is ",end="")

print(maxSubarrayXOR(set, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для поиска
// максимальное подмножество XOR

using System;

  

class GFG

      

    // Количество бит в

    // представлять int

    static int INT_BITS = 32;

      

    // Функция для возврата

    // максимальное подмножество XOR

    // в наборе []

    static int maxSubarrayXOR(int []set

                              int n)

    {

          

        // Инициализируем индекс

        // выбранные элементы

        int index = 0;

      

        // пройти через все

        // биты целого числа

        // начиная с самого

        // значащий бит (MSB)

        for (int i = INT_BITS - 1; 

                 i >= 0; i--) 

        {

              

        // Инициализируем индекс

        // максимальный элемент и

        // максимальный элемент

        int maxInd = index;

        int maxEle = int.MinValue;

        for (int j = index; j < n; j++)

        {

              

            // Если я установил бит [j]

            // установлено и установлено [j]

            // больше, чем макс.

            if ((set[j] & (1 << i)) != 0 &&

                 set[j] > maxEle)

            {

                maxEle = set[j];

                maxInd = j;

            }

        }

      

        // Если не было

        // элемент с i'th

        // бит установлен, перейти к

        // меньше я

        if (maxEle == -2147483648)

            continue;

      

        // Поместить максимальный элемент

        // с установленным битом

        // по индексу 'index'

        int temp = set[index];

        set[index] = set[maxInd];

        set[maxInd] = temp;

      

        // Обновляем maxInd и

        // инкрементный индекс

        maxInd = index;

      

        // Делаем XOR из set [maxIndex]

        // со всеми номерами, имеющими

        // я бит как установлено.

        for (int j = 0; j < n; j++) 

        {

          

            // XOR установить [maxInd] те

            // числа, которые имеют

            // я установил бит

            if (j != maxInd && (set[j] & 

               (1 << i)) != 0)

            set[j] = set[j] ^ set[maxInd];

    }

  

        // Увеличение индекса

        // выбранные элементы

        index++;

    }

  

    // Окончательный результат

    // XOR всех элементов

        int res = 0;

        for (int i = 0; i < n; i++)

        res ^= set[i];

        return res;

    }

      

    // Код драйвера

    public static void Main() 

    {

        int []set = {9, 8, 5};

        int n = set.Length;

      

        Console.Write("Max subset XOR is ");

        Console.Write(maxSubarrayXOR(set, n));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php 
// PHP программа для поиска максимального подмножества XOR

  
// Количество бит для представления int

$INT_BITS = 32;

  
// Функция для возврата максимального подмножества XOR
// в наборе []

function maxSubarrayXOR(&$set, $n)

{

    global $INT_BITS;

      

    // Инициализируем индекс выбранных элементов

    $index = 0;

  

    // Пройти через все биты целого числа

    // начиная с самого старшего бита (MSB)

    for ($i = $INT_BITS - 1; $i >= 0; $i--)

    {

        // Инициализируем индекс максимального элемента

        // и максимальный элемент

        $maxInd = $index;

        $maxEle = 0;

        for ($j = $index; $j < $n; $j++)

        {

            // Если я установил бит [j]

            // установлено и установлено [j]

            // больше, чем макс.

            if ( ($set[$j] & (1 << $i)) != 0 && 

                  $set[$j] > $maxEle )

            {

                $maxEle = $set[$j];

                $maxInd = $j;

            }

        }

  

        // Если не было элемента с i'th

        // бит установлен, перейти к меньшему

        if ($maxEle == 0)

        continue;

  

        // Поместить максимальный элемент с i'th bit

        // установить на индекс 'index'

        $t = $set[$index];

        $set[$index] = $set[$maxInd];

        $set[$maxInd] = $t;

  

        // Обновление maxInd и индекса приращения

        $maxInd = $index;

  

        // Делаем XOR для set [maxIndex] со всеми числами

        // имея i-й бит, как установлено.

        for ($j = 0; $j < $n; $j++)

        {

            // XOR устанавливает [maxInd] те числа, которые

            // установить бит i

            if ($j != $maxInd &&

               ($set[$j] & (1 << $i)) != 0)

                $set[$j] = $set[$j] ^ $set[$maxInd];

        }

  

        // Увеличение индекса выбранных элементов

        $index++;

    }

  

    // Конечный результат - XOR всех элементов

    $res = 0;

    for ($i = 0; $i < $n; $i++)

        $res ^= $set[$i];

    return $res;

}

  
// Код драйвера

$set = array(9, 8, 5);

$n = sizeof($set);

echo "Max subset XOR is ";

echo maxSubarrayXOR($set, $n);

  
// Этот код предоставлен ita_c
?>

Выход:

Max subset XOR is 13

Иллюстрация:

Let the input set be : {9, 8, 5}

We start from 31st bit [Assuming Integers are 32 bit 
long]. The loop will continue without doing anything till 4'th bit.

The 4th bit is set in set[0] i.e. 9 and this is the maximum
element with 4th bit set. So we choose this element and check
if any other number has the same bit set. If yes, we XOR that 
number with 9. The element set[1], i.e., 8 also has 4'th bit 
set. Now set[] becomes {9, 1, 5}.  We add 9 to the list of 
chosen elements by incrementing 'index'

We move further and find the maximum number with 3rd bit set
which is set[2] i.e. 5  No other number in the array has 3rd
bit set. 5 is also added to the list of chosen element.

We then iterate for bit 2 (no number for this) and then for 
1 which is 1. But numbers 9 and 5 have the 1st bit set. Thus
we XOR 9 and 5 with 1 and our set becomes (8, 1, 4)

Finally, we XOR current elements of set and get the result
as 8 ^ 1 ^ 4 = 13.

Как это работает?
Давайте сначала разберем простой случай, когда все элементы имеют наиболее значимые биты (MSB) в разных позициях. Задача в этом конкретном случае проста, нам нужно сделать XOR всех элементов.
Если входные данные содержат несколько чисел с одним и тем же MSB, то не очевидно, какое из них нам следует включить в XOR. Что мы делаем, это уменьшаем входной список в эквивалентную форму, которая не содержит более одного числа одинаковой длины. Взяв максимальный элемент, мы знаем, что MSB этого будет в выводе. Пусть этот MSB будет в положении i. Если имеется больше элементов с i-ым набором (или тем же самым MSB), мы XOR их с максимальным числом, так что i-ый бит становится 0 в них, и проблема уменьшается до i-1 битов.

Ссылки:
http://math.stackexchange.com/questions/48682/maximization-with-xor-operator

Примечание. Приведенный выше метод аналогичен устранению по Гауссу. Рассмотрим матрицу размером 32 xn, где 32 — количество битов, а n — количество элементов в массиве.

Эта статья предоставлена Ekta Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти максимальное подмножество XOR данного набора

0.00 (0%) 0 votes