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>
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>
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
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