Dado un número N , genere patrones de bits de 0 a 2^N-1 de modo que los patrones sucesivos difieran en un bit.
Ejemplos:
Input: N = 2 Output: 00 01 11 10 Input: N = 3 Output: 000 001 011 010 110 111 101 100
Método 1
Las secuencias anteriores son Códigos Gray de diferentes anchos. A continuación se muestra un patrón interesante en los Códigos grises.
Los códigos Gray de n bits se pueden generar a partir de una lista de códigos Gray de (n-1) bits siguiendo los pasos siguientes.
- Sea L1 la lista de códigos Gray de (n-1) bits. Cree otra lista L2 que sea inversa a L1.
- Modifique la lista L1 anteponiendo un ‘0’ en todos los códigos de L1.
- Modifique la lista L2 anteponiendo un ‘1’ en todos los códigos de L2.
- Concatenar L1 y L2. La lista concatenada es una lista obligatoria de códigos Gray de n bits
Por ejemplo, los siguientes son pasos para generar la lista de códigos Gray de 3 bits a partir de la lista de códigos Gray de 2 bits. L1 = {00, 01, 11, 10} (Lista de códigos Gray de 2 bits) L2 = {10, 11, 01, 00} (Reverso de L1) Prefije todas las entradas de L1 con ‘0’, L1 se convierte en {000 , 001, 011, 010} Prefije todas las entradas de L2 con ‘1’, L2 se convierte en {110, 111, 101, 100} Concatene L1 y L2, obtenemos {000, 001, 011, 010, 110, 111, 101, 100} Para generar códigos Gray de n bits, comenzamos con una lista de códigos Gray de 1 bit. La lista de código Gray de 1 bit es {0, 1}. Repetimos los pasos anteriores para generar códigos Gray de 2 bits a partir de códigos Gray de 1 bit, luego códigos Gray de 3 bits a partir de códigos Gray de 2 bits hasta que el número de bits sea igual a n.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to generate n-bit Gray codes
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// This function generates all n bit Gray codes and prints the
// generated codes
void generateGrayarr(int n)
{
// base case
if (n <= 0)
return;
// 'arr' will store all generated codes
vector<string> arr;
// start with one-bit pattern
arr.push_back("0");
arr.push_back("1");
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
int i, j;
for (i = 2; i < (1<<n); i = i<<1)
{
// Enter the previously generated codes again in arr[] in reverse
// order. Nor arr[] has double number of codes.
for (j = i-1 ; j >= 0 ; j--)
arr.push_back(arr[j]);
// append 0 to the first half
for (j = 0 ; j < i ; j++)
arr[j] = "0" + arr[j];
// append 1 to the second half
for (j = i ; j < 2*i ; j++)
arr[j] = "1" + arr[j];
}
// print contents of arr[]
for (i = 0 ; i < arr.size() ; i++ )
cout << arr[i] << endl;
}
// Driver program to test above function
int main()
{
generateGrayarr(3);
return 0;
}
Java
// Java program to generate n-bit Gray codes
import java.util.*;
class GfG {
// This function generates all n bit Gray codes and prints the
// generated codes
static void generateGrayarr(int n)
{
// base case
if (n <= 0)
return;
// 'arr' will store all generated codes
ArrayList<String> arr = new ArrayList<String> ();
// start with one-bit pattern
arr.add("0");
arr.add("1");
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
int i, j;
for (i = 2; i < (1<<n); i = i<<1)
{
// Enter the previously generated codes again in arr[] in reverse
// order. Nor arr[] has double number of codes.
for (j = i-1 ; j >= 0 ; j--)
arr.add(arr.get(j));
// append 0 to the first half
for (j = 0 ; j < i ; j++)
arr.set(j, "0" + arr.get(j));
// append 1 to the second half
for (j = i ; j < 2*i ; j++)
arr.set(j, "1" + arr.get(j));
}
// print contents of arr[]
for (i = 0 ; i < arr.size() ; i++ )
System.out.println(arr.get(i));
}
// Driver program to test above function
public static void main(String[] args)
{
generateGrayarr(3);
}
}
Python3
# Python3 program to generate n-bit Gray codes
import math as mt
# This function generates all n bit Gray
# codes and prints the generated codes
def generateGrayarr(n):
# base case
if (n <= 0):
return
# 'arr' will store all generated codes
arr = list()
# start with one-bit pattern
arr.append("0")
arr.append("1")
# Every iteration of this loop generates
# 2*i codes from previously generated i codes.
i = 2
j = 0
while(True):
if i >= 1 << n:
break
# Enter the previously generated codes
# again in arr[] in reverse order.
# Nor arr[] has double number of codes.
for j in range(i - 1, -1, -1):
arr.append(arr[j])
# append 0 to the first half
for j in range(i):
arr[j] = "0" + arr[j]
# append 1 to the second half
for j in range(i, 2 * i):
arr[j] = "1" + arr[j]
i = i << 1
# print contents of arr[]
for i in range(len(arr)):
print(arr[i])
# Driver Code
generateGrayarr(3)
# This code is contributed
# by Mohit kumar 29
C#
using System;
using System.Collections.Generic;
// C# program to generate n-bit Gray codes
public class GfG
{
// This function generates all n bit Gray codes and prints the
// generated codes
public static void generateGrayarr(int n)
{
// base case
if (n <= 0)
{
return;
}
// 'arr' will store all generated codes
List<string> arr = new List<string> ();
// start with one-bit pattern
arr.Add("0");
arr.Add("1");
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
int i, j;
for (i = 2; i < (1 << n); i = i << 1)
{
// Enter the previously generated codes again in arr[] in reverse
// order. Nor arr[] has double number of codes.
for (j = i - 1 ; j >= 0 ; j--)
{
arr.Add(arr[j]);
}
// append 0 to the first half
for (j = 0 ; j < i ; j++)
{
arr[j] = "0" + arr[j];
}
// append 1 to the second half
for (j = i ; j < 2 * i ; j++)
{
arr[j] = "1" + arr[j];
}
}
// print contents of arr[]
for (i = 0 ; i < arr.Count ; i++)
{
Console.WriteLine(arr[i]);
}
}
// Driver program to test above function
public static void Main(string[] args)
{
generateGrayarr(3);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to generate n-bit Gray codes
// This function generates all n bit Gray codes and prints the
// generated codes
function generateGrayarr(n)
{
// base case
if (n <= 0)
return;
// 'arr' will store all generated codes
let arr = [];
// start with one-bit pattern
arr.push("0");
arr.push("1");
// Every iteration of this loop generates 2*i codes from previously
// generated i codes.
let i, j;
for (i = 2; i < (1<<n); i = i<<1)
{
// Enter the previously generated codes again in arr[] in reverse
// order. Nor arr[] has double number of codes.
for (j = i-1 ; j >= 0 ; j--)
arr.push(arr[j]);
// append 0 to the first half
for (j = 0 ; j < i ; j++)
arr[j]= "0" + arr[j];
// append 1 to the second half
for (j = i ; j < 2*i ; j++)
arr[j]= "1" + arr[j];
}
// print contents of arr[]
for (i = 0 ; i < arr.length ; i++ )
document.write(arr[i]+"<br>");
}
// Driver program to test above function
generateGrayarr(3);
// This code is contributed by unknown2108
</script>
Producción
000 001 011 010 110 111 101 100
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Método 2: enfoque recursivo
La idea es agregar recursivamente el bit 0 y 1 cada vez hasta que el número de bits no sea igual a N.
Condición Base: El caso base para este problema será cuando el valor de N = 0 o 1.
Si (N == 0)
devuelve {“0”}
si (N == 1)
devuelve {“0”, “1”}
Condición Recursiva: De lo contrario, para cualquier valor mayor a 1, genera recursivamente los códigos grises de los N – 1 bits y luego para cada uno de los códigos grises generados agrega el prefijo 0 y 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to generate
// n-bit Gray codes
#include <bits/stdc++.h>
using namespace std;
// This function generates all n
// bit Gray codes and prints the
// generated codes
vector<string> generateGray(int n)
{
// Base case
if (n <= 0)
return {"0"};
if (n == 1)
{
return {"0","1"};
}
//Recursive case
vector<string> recAns=
generateGray(n-1);
vector<string> mainAns;
// Append 0 to the first half
for(int i=0;i<recAns.size();i++)
{
string s=recAns[i];
mainAns.push_back("0"+s);
}
// Append 1 to the second half
for(int i=recAns.size()-1;i>=0;i--)
{
string s=recAns[i];
mainAns.push_back("1"+s);
}
return mainAns;
}
// Function to generate the
// Gray code of N bits
void generateGrayarr(int n)
{
vector<string> arr;
arr=generateGray(n);
// print contents of arr
for (int i = 0 ; i < arr.size();
i++ )
cout << arr[i] << endl;
}
// Driver Code
int main()
{
generateGrayarr(3);
return 0;
}
Java
// Java program to generate
// n-bit Gray codes
import java.io.*;
import java.util.*;
class GFG
{
// This function generates all n
// bit Gray codes and prints the
// generated codes
static ArrayList<String> generateGray(int n)
{
// Base case
if (n <= 0)
{
ArrayList<String> temp =
new ArrayList<String>(){{add("0");}};
return temp;
}
if(n == 1)
{
ArrayList<String> temp =
new ArrayList<String>(){{add("0");add("1");}};
return temp;
}
// Recursive case
ArrayList<String> recAns = generateGray(n - 1);
ArrayList<String> mainAns = new ArrayList<String>();
// Append 0 to the first half
for(int i = 0; i < recAns.size(); i++)
{
String s = recAns.get(i);
mainAns.add("0" + s);
}
// Append 1 to the second half
for(int i = recAns.size() - 1; i >= 0; i--)
{
String s = recAns.get(i);
mainAns.add("1" + s);
}
return mainAns;
}
// Function to generate the
// Gray code of N bits
static void generateGrayarr(int n)
{
ArrayList<String> arr = new ArrayList<String>();
arr = generateGray(n);
// print contents of arr
for (int i = 0 ; i < arr.size(); i++)
{
System.out.println(arr.get(i));
}
}
// Driver Code
public static void main (String[] args)
{
generateGrayarr(3);
}
}
// This code is contributed by rag2127.
Python3
# Python3 program to generate
# n-bit Gray codes
# This function generates all n
# bit Gray codes and prints the
# generated codes
def generateGray(n):
# Base case
if (n <= 0):
return ["0"]
if (n == 1):
return [ "0", "1" ]
# Recursive case
recAns = generateGray(n - 1)
mainAns = []
# Append 0 to the first half
for i in range(len(recAns)):
s = recAns[i]
mainAns.append("0" + s)
# Append 1 to the second half
for i in range(len(recAns) - 1, -1, -1):
s = recAns[i]
mainAns.append("1" + s)
return mainAns
# Function to generate the
# Gray code of N bits
def generateGrayarr(n):
arr = generateGray(n)
# Print contents of arr
print(*arr, sep = "\n")
# Driver Code
generateGrayarr(3)
# This code is contributed by avanitrachhadiya2155
C#
// Java program to generate
// n-bit Gray codes
using System;
using System.Collections.Generic;
class GFG {
// This function generates all n
// bit Gray codes and prints the
// generated codes
static List<String> generateGray(int n)
{
// Base case
if (n <= 0) {
List<String> temp = new List<String>();
temp.Add("0");
return temp;
}
if (n == 1) {
List<String> temp = new List<String>();
temp.Add("0");
temp.Add("1");
return temp;
}
// Recursive case
List<String> recAns = generateGray(n - 1);
List<String> mainAns = new List<String>();
// Append 0 to the first half
for (int i = 0; i < recAns.Count; i++) {
String s = recAns[i];
mainAns.Add("0" + s);
}
// Append 1 to the second half
for (int i = recAns.Count - 1; i >= 0; i--) {
String s = recAns[i];
mainAns.Add("1" + s);
}
return mainAns;
}
// Function to generate the
// Gray code of N bits
static void generateGrayarr(int n)
{
List<String> arr = new List<String>();
arr = generateGray(n);
// print contents of arr
for (int i = 0; i < arr.Count; i++)
{
Console.WriteLine(arr[i]);
}
}
// Driver Code
public static void Main(String[] args)
{
generateGrayarr(3);
}
}
// This code is contributed by grand_master.
Javascript
<script>
// Javascript program to generate
// n-bit Gray codes
// This function generates all n
// bit Gray codes and prints the
// generated codes
function generateGray(n)
{
// Base case
if (n <= 0)
{
let temp =["0"];
return temp;
}
if(n == 1)
{
let temp =["0","1"];
return temp;
}
// Recursive case
let recAns = generateGray(n - 1);
let mainAns = [];
// Append 0 to the first half
for(let i = 0; i < recAns.length; i++)
{
let s = recAns[i];
mainAns.push("0" + s);
}
// Append 1 to the second half
for(let i = recAns.length - 1; i >= 0; i--)
{
let s = recAns[i];
mainAns.push("1" + s);
}
return mainAns;
}
// Function to generate the
// Gray code of N bits
function generateGrayarr(n)
{
let arr = [];
arr = generateGray(n);
// print contents of arr
for (let i = 0 ; i < arr.length; i++)
{
document.write(arr[i]+"<br>");
}
}
// Driver Code
generateGrayarr(3);
// This code is contributed by ab2127
</script>
Producción
000 001 011 010 110 111 101 100
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Método 3: (Usando conjunto de bits)
Primero debemos encontrar el número binario del 1 al n y luego convertirlo en una string y luego imprimirlo usando la función de substring de la string.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
void GreyCode(int n)
{
// power of 2
for (int i = 0; i < (1 << n); i++)
{
// Generating the decimal
// values of gray code then using
// bitset to convert them to binary form
int val = (i ^ (i >> 1));
// Using bitset
bitset<32> r(val);
// Converting to string
string s = r.to_string();
cout << s.substr(32 - n) << " ";
}
}
// Driver Code
int main()
{
int n;
n = 4;
// Function call
GreyCode(n);
return 0;
}
Java
// Java implementation of the above approach
import java.lang.Math;
class GFG {
static void GreyCode(int n)
{
// power of 2
for (int i = 0; i < (1 << n); i++)
{
// Generating the decimal
// values of gray code then using
// bitset to convert them to binary form
int val = (i ^ (i >> 1));
// Converting to binary string
String s = Integer.toBinaryString(val);
System.out.print(
String.format("%1$" + 4 + "s", s)
.replace(' ', '0')
+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int n = 4;
// Function call
GreyCode(n);
}
}
// This code is contributed by phasing17
Python3
# Python3 implementation of the above approach def GreyCode(n): # power of 2 for i in range(1 << n): # Generating the decimal # values of gray code then using # bitset to convert them to binary form val = (i ^ (i >> 1)) # Converting to binary string s = bin(val)[2::] print(s.zfill(4), end = " ") # Driver Code n = 4 # Function call GreyCode(n) # This code is contributed by phasing17
Javascript
// JavaScript implementation of the above approach
function GreyCode(n)
{
// power of 2
for (var i = 0; i < (1 << n); i++)
{
// Generating the decimal
// values of gray code then using
// bitset to convert them to binary form
var val = (i ^ (i >> 1));
// Converting to binary string
s = val.toString(2);
process.stdout.write(s.padStart(4, '0') + " ");
}
}
// Driver Code
let n = 4;
// Function call
GreyCode(n);
// This code is contributed by phasing17
C#
// C# implementation of the above approach
using System;
class GFG {
static void GreyCode(int n)
{
// power of 2
for (int i = 0; i < (1 << n); i++) {
// Generating the decimal
// values of gray code then using
// bitset to convert them to binary form
int val = (i ^ (i >> 1));
// Converting to binary string
string s = Convert.ToString(val, 2);
Console.Write(s.PadLeft(4, '0') + " ");
}
}
// Driver Code
public static void Main(string[] args)
{
int n = 4;
// Function call
GreyCode(n);
}
}
// This code is contributed by phasing17
Producción
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA