Generar códigos grises de n bits – Part 1

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.

  1. Sea L1 la lista de códigos Gray de (n-1) bits. Cree otra lista L2 que sea inversa a L1.
  2. Modifique la lista L1 anteponiendo un ‘0’ en todos los códigos de L1.
  3. Modifique la lista L2 anteponiendo un ‘1’ en todos los códigos de L2.
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *