Genere una permutación de [0, N-1] con XOR adyacente máximo que es mínimo entre otras permutaciones

Dado un número entero N , la tarea es imprimir una permutación de números de 0 a N-1 , tal que:

• No hay ningún elemento duplicado en la permutación.
• El XOR adyacente máximo de esta permutación es mínimo entre otras permutaciones
• Puede haber más de una permutación presente que satisfaga estas condiciones.

Ejemplos:

Entrada: N = 5
Salida: 1 2 3 0 4
Explicación:
El valor XOR máximo de dos elementos consecutivos de la permutación es 0 XOR 4 = 4
No existe ninguna otra permutación donde el valor XOR máximo de dos elementos consecutivos de la permutación es menor que 4.
Pueden existir otras permutaciones cuando el valor sea igual o superior a 4.

Entrada: N = 10
Salida: 1 2 3 4 5 6 7 0 8 9

Enfoque: La intuición para resolver este problema se basa en las propiedades de XOR mencionadas a continuación :

• Dentro de toda la permutación, habrá algunos números con el bit más significativo como 1 o como 0.
• Así que agrupe los números con el bit más significativo como 1 para que el bit más significativo se cancele.
• Pero siempre habrá un caso en la permutación donde un número con el bit más significativo como 1 residirá antes o después de un número donde el bit más significativo es 0. En ese punto, el XOR no cancelará el bit más significativo. operación.

• En ese caso, coloque el número mínimo con el bit más significativo como 1 y el número mínimo con el bit más significativo como 0 (posiblemente 0), juntos para obtener el valor XOR máximo.
• Este es el valor mínimo posible del valor XOR máximo entre todas las permutaciones.

Siga los pasos mencionados a continuación para implementar la observación anterior:

• Inicialmente, calcule el número mínimo menor o igual a N-1 que tiene el bit establecido más significativo.
• Imprima todos los números menores que el número mínimo con el bit establecido más significativo a partir de 1 consecutivamente.
• Imprimir 0.
• Imprima todos los números a partir de un número mínimo con un bit de configuración más significativo hasta N-1

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the desired permutation
void getPermutation(int n)
{
    // Calculate the maximum number
    // in the permutation
    int maxnum = n - 1;
 
    // Calculate the minimum number
    // bit is 1 where most significant
    int num = 1;
    while (maxnum > 0) {
        maxnum /= 2;
        num *= 2;
    }
    num /= 2;
 
    // Print all numbers less than the number
    // where most significant bit is set
    for (int i = 1; i <= num - 1; i++) {
        cout << i << " ";
    }
 
    // Print 0
    cout << 0 << " ";
 
    // Print all the numbers
    // greater than or equal to
    // the number where
    // most significant bit is set
    for (int i = num; i < n; i++) {
        cout << i << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 5;
   
    // Function call
    getPermutation(N);
    return 0;
}

// JAVA program to implement above approach
import java.util.*;
class GFG
{
   
    // Function to get the desired permutation
    public static void getPermutation(int n)
    {
       
        // Calculate the maximum number
        // in the permutation
        int maxnum = n - 1;
 
        // Calculate the minimum number
        // bit is 1 where most significant
        int num = 1;
        while (maxnum > 0) {
            maxnum /= 2;
            num *= 2;
        }
        num /= 2;
 
        // Print all numbers less than the number
        // where most significant bit is set
        for (int i = 1; i <= num - 1; i++) {
            System.out.print(i + " ");
        }
 
        // Print 0
        System.out.print(0 + " ");
 
        // Print all the numbers
        // greater than or equal to
        // the number where
        // most significant bit is set
        for (int i = num; i < n; i++) {
            System.out.print(i + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
 
        // Function call
        getPermutation(N);
    }
}
 
// This code is contributed by Taranpreet

# Python code for the above approach
 
# Function to get the desired permutation
def getPermutation(n):
 
    # Calculate the maximum number
    # in the permutation
    maxnum = n - 1
 
    # Calculate the minimum number
    # bit is 1 where most significant
    num = 1
    while (maxnum > 0):
        maxnum = maxnum//2
        num *= 2
 
    num = (num//2)
 
    # Print all numbers less than the number
    # where most significant bit is set
    for i in range(1, num):
        print(i, end=" ")
 
    # Print 0
    print(0, end=" ")
 
    # Print all the numbers
    # greater than or equal to
    # the number where
    # most significant bit is set
    for i in range(num, n):
        print(i, end=" ")
 
# Driver Code
N = 5
 
# Function call
getPermutation(N)
 
# This code is contributed by Potta Lokesh

// C# program to implement above approach
using System;
class GFG
{
   
    // Function to get the desired permutation
    static void getPermutation(int n)
    {
       
        // Calculate the maximum number
        // in the permutation
        int maxnum = n - 1;
 
        // Calculate the minimum number
        // bit is 1 where most significant
        int num = 1;
        while (maxnum > 0) {
            maxnum /= 2;
            num *= 2;
        }
        num /= 2;
 
        // Print all numbers less than the number
        // where most significant bit is set
        for (int i = 1; i <= num - 1; i++) {
            Console.Write(i + " ");
        }
 
        // Print 0
        Console.Write(0 + " ");
 
        // Print all the numbers
        // greater than or equal to
        // the number where
        // most significant bit is set
        for (int i = num; i < n; i++) {
            Console.Write(i + " ");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 5;
 
        // Function call
        getPermutation(N);
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program to implement above approach
 
    // Function to get the desired permutation
    const getPermutation = (n) => {
     
        // Calculate the maximum number
        // in the permutation
        let maxnum = n - 1;
 
        // Calculate the minimum number
        // bit is 1 where most significant
        let num = 1;
        while (maxnum > 0) {
            maxnum = parseInt(maxnum / 2);
            num *= 2;
        }
        num = parseInt(num / 2);
 
        // Print all numbers less than the number
        // where most significant bit is set
        for (let i = 1; i <= num - 1; i++) {
            document.write(`${i} `);
        }
 
        // Print 0
        document.write("0 ");
 
        // Print all the numbers
        // greater than or equal to
        // the number where
        // most significant bit is set
        for (let i = num; i < n; i++) {
            document.write(`${i} `);
        }
    }
 
    // Driver Code
    let N = 5;
 
    // Function call
    getPermutation(N);
 
// This code is contributed by rakeshsahni
 
</script>

1 2 3 0 4 

Complejidad de Tiempo: 0(N)
Espacio Auxiliar: 0(1)