Generar permutación de [1, N] teniendo XOR bit a bit de diferencias adyacentes como 0

Dado un número entero N , la tarea es generar una permutación de 1 a N tal que el XOR bit a bit de las diferencias entre elementos adyacentes sea 0, es decir, | UN[1]− UN[2] | ^ | UN[2]− UN[3] | ^ . . . ^ | UN[N −1] − UN[N] | = 0, donde |X – Y| representa la diferencia absoluta entre X e Y.

Ejemplos:

Entrada: N = 4
Salida: 2 3 1 4
Explicación:  |2 -3| ^ |3 -1| ^ |1-4| = 1 ^ 2 ^ 3 = 0

Entrada: N = 3
Salida: 1 2 3

Planteamiento: Este problema se puede resolver con base en la siguiente observación:

• El XOR de un número par de elementos iguales es 0. Entonces, si hay un número impar de elementos (lo que implica un número par de diferencias adyacentes), organícelos de tal manera que la diferencia entre dos elementos adyacentes sea la misma. 
• De lo contrario, si N es par (lo que implica un número impar de diferencias adyacentes), organice los primeros cuatro de tal manera que el XOR de las primeras tres diferencias sea 0. Luego, el resto de los elementos mencionados anteriormente se eliminan.

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

• Si N es impar, ordene todos los N elementos porque la diferencia entre dos elementos adyacentes cualesquiera será 1 y el número de diferencias adyacentes será par.
• Si N es par:
  • Mantenga 2, 3, 1, 4 como los primeros cuatro elementos porque las 3 diferencias tienen XOR 0.
  • Ahora comience desde 5 e imprima los elementos restantes en orden ordenado, lo que dará la diferencia como 1 para todas las diferencias pares restantes.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print shuffle array
vector<int> shuffleArray(int n)
{
    vector<int> res;
 
    // Base case
    if (n < 3)
        cout << -1 << endl;
 
    // When n is odd print array in
    // increasing order
    else if (n % 2 != 0) {
        for (int i = 1; i <= n; i++)
            res.push_back(i);
    }
 
    // When n is even print first 2 3 1 4
    // rest element in increasing order
    else {
        res = { 2, 3, 1, 4 };
        for (int i = 5; i <= n; i++)
            res.push_back(i);
    }
    return res;
}
 
// Driver code
int main()
{
    int N = 4;
 
    vector<int> ans = shuffleArray(N);
    for (int x : ans)
        cout << x << " ";
    return 0;
}

// Java implementation of above approach
import java.util.*;
public class GFG {
 
  // Function to print shuffle array
  static ArrayList<Integer> shuffleArray(int n)
  {
    ArrayList<Integer> res = new ArrayList<Integer>();
 
    // Base case
    if (n < 3)
      System.out.println(-1);
 
    // When n is odd print array in
    // increasing order
    else if (n % 2 != 0) {
      for (int i = 1; i <= n; i++)
        res.add(i);
    }
 
    // When n is even print first 2 3 1 4
    // rest element in increasing order
    else {
      res.clear();
 
      res.add(2);
      res.add(3);
      res.add(1);
      res.add(4);
 
      for (int i = 5; i <= n; i++)
        res.add(i);
    }
    return res;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int N = 4;
 
    ArrayList<Integer> ans = shuffleArray(N);
    for (int i = 0; i < ans.size(); i++)
      System.out.print(ans.get(i) + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python3 implementation of above approach
 
# Function to print shuffle array
def shuffleArray(n):
 
    res = []
 
    # Base case
    if (n < 3):
        print(-1)
 
    # When n is odd print array in
    # increasing order
    elif (n % 2 != 0):
        for i in range(1, n):
            res.append(i)
 
    # When n is even print first 2 3 1 4
    # rest element in increasing order
    else:
        res = [2, 3, 1, 4]
        for i in range(5, n):
            res.append(i)
 
    return res
 
# Driver code
if __name__ == '__main__':
    n = 4
    res = shuffleArray(n)
    for i in res:
        print(i, end=' ')
 
        # This code is contributed by richasalan57.

// C# implementation of above approach
using System;
using System.Collections;
 
class GFG
{
 
// Function to print shuffle array
static ArrayList shuffleArray(int n)
{
    ArrayList res = new ArrayList();
 
    // Base case
    if (n < 3)
        Console.WriteLine(-1);
 
    // When n is odd print array in
    // increasing order
    else if (n % 2 != 0) {
        for (int i = 1; i <= n; i++)
            res.Add(i);
    }
 
    // When n is even print first 2 3 1 4
    // rest element in increasing order
    else {
        res.Clear();
         
        res.Add(2);
        res.Add(3);
        res.Add(1);
        res.Add(4);
         
        for (int i = 5; i <= n; i++)
            res.Add(i);
    }
    return res;
}
 
// Driver code
public static void Main()
{
    int N = 4;
 
    ArrayList ans = shuffleArray(N);
    foreach (int x in ans)
        Console.Write(x + " ");
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript implementation of above approach
 
// Function to print shuffle array
function shuffleArray(n)
{
    let res = [];
 
    // Base case
    if (n < 3)
        document.write(-1,"</br>");
 
    // When n is odd print array in
    // increasing order
    else if (n % 2 != 0) {
        for (let i = 1; i <= n; i++)
            res.push(i);
    }
 
    // When n is even print first 2 3 1 4
    // rest element in increasing order
    else {
        res = [ 2, 3, 1, 4 ];
        for (let i = 5; i <= n; i++)
            res.push(i);
    }
    return res;
}
 
// Driver code
let N = 4;
 
let ans = shuffleArray(N);
for(let x of ans)
    document.write(x," ");
 
// This code is contributed by shinjanpatra
 
</script>

2 3 1 4 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)