es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Generar una lista de números binarios donde n bits están configurados en 1.

11 Jun, 2023 Programación

Quiero generar una lista de números binarios con m dígitos, donde n bits son iguales a 1 y los demás son iguales a 0. Por ejemplo, supongamos que m es 4. Quiero generar una lista de números binarios con 4 bits. De los 16 números, 6 de ellos tienen 2 bits iguales a 1, y los demás son todos 0s.

Quiero generar una lista para cualquier cantidad de bits m con n bits iguales a 1, al menos para el caso en que n = 2. Pero no estoy seguro de qué proceso seguir. Podría generar todos los números que contienen m bits y luego verificar cada uno individualmente, pero para una cantidad mayor de bits eso podría llevar un tiempo. Siento que debe haber un truco matemático más elegante para encontrar la respuesta.

Agradecería cualquier consejo sobre dónde empezar. No me importa si las respuestas están en seudocódigo o en cualquier lenguaje, siempre y cuando sean claras.

El problema XY
Estoy tratando de resolver un problema de ajedrez, donde hay dos piezas en el tablero. Primero estoy tratando de generar todas las combinaciones válidas de dos piezas en el tablero, que planeo hacer tratando el tablero de ajedrez como un número binario de 64 bits (0000 0000 0000 0000…0011) donde un bit encendido representa una pieza. Para hacer esto, necesito encontrar una manera elegante de generar la lista de números binarios.

Edit: He intentado implementar el algoritmo ingenuo en Python solo como demostración. Está tardando demasiado en ejecutarse en mi VS Code para m = 64, por lo que definitivamente no es la mejor solución:

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Generación de una lista de números binarios con m dígitos

    Para generar una lista de números binarios con m dígitos y n bits establecidos en 1, se puede utilizar el siguiente algoritmo:

    1. Crear una variable bits con n unos y m-n ceros.
    2. Generar todas las posibles permutaciones de bits.
    3. Para cada permutación, antepone m-n ceros.
    4. Convertir cada cadena binaria a su equivalente decimal.

    Aquí hay un ejemplo de implementación en Python:

    import itertools

def generate_binary_numbers(m, n):
    bits = '1' * n + '0' * (m - n)
    perms = set(itertools.permutations(bits))
    return [int(''.join('0' + ''.join(perm) for perm in perms), 2)]

# Ejemplo de uso
combinations = generate_binary_numbers(4, 2)
for c in combinations:
    print(f'{c:04b}')

    La salida para m=4 y n=2 será:

    0011
0101
0110
1001
1010
1100

    Este algoritmo generará rápidamente todas las combinaciones válidas de números binarios. Tenga en cuenta que tendrá dificultades para valores grandes de m y n, especialmente al convertir a decimal, ya que los números resultantes pueden no caber en la memoria disponible o en los límites de la CPU. En tales casos, puede ser necesario dividir el problema en piezas más pequeñas o considerar enfoques alternativos, como la manipulación de bits.

Comments are closed.