Dados dos números enteros N y S , la tarea es encontrar una permutación circular de números del rango [0, 2 (N – 1) ] , comenzando con S tal que el recuento de bits que no coinciden entre cualquier par de números adyacentes sea uno .
Ejemplos:
Entrada: N = 2, S = 3
Salida: [3, 2, 0, 1]
Explicación:
La representación binaria de los números 3, 2, 0 y 1 son “11”, “10”, “01” y “00” respectivamente.
Por lo tanto, ordenarlos en el orden [3, 2, 0, 1] asegura que el número de bits de diferencia entre cada par de elementos adyacentes (circulares) sea 1.Entrada: N = 3, S = 2
Salida: [2, 6, 7, 5, 4, 0, 1, 3]
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Una simple observación es que los números en el rango [2 i , 2 i + 1 – 1] se pueden obtener en su orden natural colocando ‘1’ antes de cada número en el rango [0, 2 i – 1] .
- Por lo tanto, el problema se puede resolver recursivamente agregando ‘1’ antes de cada número antes de 2 i – 1 th índice e invirtiéndolo antes de agregar los nuevos números a su permutación.
Siga los pasos a continuación para resolver el problema:
- Inicialice una lista, digamos res , para almacenar la permutación requerida.
- Inicialice un número entero, digamos index , para almacenar la posición de S en la permutación que comienza con 0 .
- Itere sobre el rango [0, N – 1] y recorra la array res[] en orden inverso y verifique si la suma del número actual y 2 i es S o no. Si se determina que es cierto, actualice el índice con el índice actual de res y agregue el número actual + 2 i a la lista res .
- Rotar la lista res[] por posiciones de índice .
- Después de completar los pasos anteriores, imprima la lista res[] como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the permutation of
// integers from a given range such that
// number of mismatching bits between
// pairs of adjacent elements is 1
vector<int> circularPermutation(int n, int start)
{
// Initialize an arrayList to
// store the resultant permutation
vector<int> res = {0};
vector<int> ret;
// Store the index of rotation
int index = -1;
// Iterate over the range [0, N - 1]
for(int k = 0, add = 1 << k; k < n;
k++, add = 1 << k)
{
// Traverse all the array elements
// up to (2 ^ k)-th index in reverse
for (int i = res.size() - 1;
i >= 0; i--)
{
// If current element is S
if (res[i] + add == start)
index = res.size();
res.push_back(res[i] + add);
}
}
// Check if S is zero
if (start == 0)
return res;
// Rotate the array by index
// value to the left
while (ret.size() < res.size())
{
ret.push_back(res[index]);
index = (index + 1) % res.size();
}
return ret;
}
// Driver Code
int main()
{
int N = 2, S = 3;
vector<int> print = circularPermutation(N, S);
cout << "[";
for(int i = 0; i < print.size() - 1; i++ )
{
cout << print[i] << ", ";
}
cout << print[print.size() - 1] << "]";
return 0;
}
// This code is contributed by susmitakundugoaldanga
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the permutation of
// integers from a given range such that
// number of mismatching bits between
// pairs of adjacent elements is 1
public static List<Integer> circularPermutation(
int n, int start)
{
// Initialize an arrayList to
// store the resultant permutation
List<Integer> res = new ArrayList<>(List.of(0)),
ret = new ArrayList<>();
// Store the index of rotation
int index = -1;
// Iterate over the range [0, N - 1]
for (int k = 0, add = 1 << k; k < n;
k++, add = 1 << k) {
// Traverse all the array elements
// up to (2 ^ k)-th index in reverse
for (int i = res.size() - 1;
i >= 0; i--) {
// If current element is S
if (res.get(i) + add == start)
index = res.size();
res.add(res.get(i) + add);
}
}
// Check if S is zero
if (start == 0)
return res;
// Rotate the array by index
// value to the left
while (ret.size() < res.size()) {
ret.add(res.get(index));
index = (index + 1) % res.size();
}
return ret;
}
// Driver Code
public static void main(String[] args)
{
int N = 2, S = 3;
System.out.println(
circularPermutation(N, S));
}
}
Python3
# Python3 program for the above approach # Function to find the permutation of # integers from a given range such that # number of mismatching bits between # pairs of adjacent elements is 1 def circularPermutation(n, start): # Initialize an arrayList to # store the resultant permutation res = [0] ret = [] # Store the index of rotation index, add = -1, 1 # Iterate over the range [0, N - 1] for k in range(n): add = 1<<k # Traverse all the array elements # up to (2 ^ k)-th index in reverse for i in range(len(res) - 1, -1, -1): # If current element is S if (res[i] + add == start): index = len(res) res.append(res[i] + add) add = 1 << k # Check if S is zero if (start == 0): return res # Rotate the array by index # value to the left while (len(ret) < len(res)): ret.append(res[index]) index = (index + 1) % len(res) return ret # Driver Code if __name__ == '__main__': N,S = 2, 3 print (circularPermutation(N, S)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the permutation of
// integers from a given range such that
// number of mismatching bits between
// pairs of adjacent elements is 1
public static List<int> circularPermutation(
int n, int start)
{
// Initialize an arrayList to
// store the resultant permutation
List<int> res = new List<int>(){0};
List<int> ret = new List<int>();
// Store the index of rotation
int index = -1;
// Iterate over the range [0, N - 1]
for (int k = 0, add = 1 << k; k < n;
k++, add = 1 << k)
{
// Traverse all the array elements
// up to (2 ^ k)-th index in reverse
for (int i = res.Count - 1;
i >= 0; i--)
{
// If current element is S
if (res[i] + add == start)
index = res.Count;
res.Add(res[i] + add);
}
}
// Check if S is zero
if (start == 0)
return res;
// Rotate the array by index
// value to the left
while (ret.Count < res.Count)
{
ret.Add(res[index]);
index = (index + 1) % res.Count;
}
return ret;
}
// Driver Code
static public void Main ()
{
int N = 2, S = 3;
List<int> print = circularPermutation(N, S);
Console.Write("[");
for(int i = 0; i < print.Count - 1; i++ )
{
Console.Write(print[i] + ", ");
}
Console.Write(print[print.Count-1] + "]");
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Function to find the permutation of
// integers from a given range such that
// number of mismatching bits between
// pairs of adjacent elements is 1
function circularPermutation(n, start)
{
// Initialize an arrayList to
// store the resultant permutation
var res = [0];
var ret = [];
// Store the index of rotation
var index = -1;
// Iterate over the range [0, N - 1]
for(var k = 0, add = 1 << k; k < n;
k++, add = 1 << k)
{
// Traverse all the array elements
// up to (2 ^ k)-th index in reverse
for (var i = res.length - 1;
i >= 0; i--)
{
// If current element is S
if (res[i] + add == start)
index = res.length;
res.push(res[i] + add);
}
}
// Check if S is zero
if (start == 0)
return res;
// Rotate the array by index
// value to the left
while (ret.length < res.length)
{
ret.push(res[index]);
index = (index + 1) % res.length;
}
return ret;
}
// Driver Code
var N = 2, S = 3;
var print = circularPermutation(N, S);
document.write( "[");
for(var i = 0; i < print.length - 1; i++ )
{
document.write( print[i] + ", ");
}
document.write( print[print.length - 1] + "]");
</script>
Producción:
[3, 2, 0, 1]
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA