de cuántas formas se pueden hacer 9 "unos" o "ceros"

Question

¿Cuántas posibilidades hay de crear un número de 9 cifras a partir de dos cifras? 0 y 1 (cero y uno), es decir, ¿de cuántas formas se pueden ordenar estos dos dígitos?

Ej: 000000000

000000001

000010010

111101111

111000100

000011001

111110000

010101000

001101110

ect.

¿Existe algún programa que pueda crear todas las combinaciones posibles? Le agradeceré su respuesta.

Answer 1

Para cada dígito tienes dos posibilidades. Esto hace un total de $2^9$ posibilidades.

Para generar todas las combinaciones, basta con anidar $9$ para los bucles. Por ejemplo, si tuviera que generar todos los $3$ -números de dígitos con $0$ y $1$ puedes hacer..:

para $i$ de $0$ a $1$ :
...para $j$ de $0$ a $1$ :
......for $k$ de $0$ a $1$ :
.........volver $\overline{ijk}$

Answer 2

Ya se ha explicado que existen $p^n$ listas de longitud $n$ con elementos arbitrarios de un alfabeto de longitud $p$ . Es sólo una aplicación de la regla del producto . Veamos cómo generar estas listas.

La siguiente función de Python enumera todos los $n$ -tuplas de la lista $a$ . Esta función (así como todas las alternativas a continuación) se implementa como un generador de Python, para permitir el bucle en las tuplas sin construir toda la lista. Es lo suficientemente parecido al pseudocódigo como para implementarlo en otro lenguaje si es necesario.

def tuples(a, n):
    m = len(a)
    u = [0] * n
    while True:
        yield tuple(a[i] for i in u)
        j = n - 1
        while j >= 0 and u[j] == m - 1:
            u[j] = 0
            j -= 1
        if j < 0:
            return
        u[j] += 1

Por ejemplo, para $4$ bits:

>>> list(tuples([0, 1], 4))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),
 (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1),
 (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1),
 (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]

Para $9$ la salida es demasiado grande para imprimir aquí, pero se obtiene la longitud $2^9$ como se esperaba:

>>> sum(1 for u in tuples([0, 1], 9))
512

---

Tenga en cuenta que en Python, lo mismo se puede lograr con una función incorporada:

import itertools
>>> list(itertools.product([0, 1], repeat=4))

[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),
 (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1),
 (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1),
 (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]

---

Dado que está enumerando secuencias de bits, existe un algoritmo aún más sencillo: realice un bucle sobre todos los números comprendidos entre $0$ y $2^9-1$ y convertir cada uno en base $2$ .

def bits(n):
    for p in range(1 << n):
        u = []
        for i in range(n):
            u.append(p & 1)
            p >>= 1
        yield tuple(u)

Por ejemplo:

>>> list(bits(4))
[(0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (1, 1, 0, 0),
 (0, 0, 1, 0), (1, 0, 1, 0), (0, 1, 1, 0), (1, 1, 1, 0),
 (0, 0, 0, 1), (1, 0, 0, 1), (0, 1, 0, 1), (1, 1, 0, 1),
 (0, 0, 1, 1), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 1, 1)]

>>> sum(1 for u in bits(9))
512

---

Una forma más sencilla aún, utilizando la función incorporada de Python para convertir a binario.

def bits(n):
    m = 1 << n
    return (tuple(int(s) for s in bin(m + k)[3:]) for k in range(m))

Por ejemplo:

>>> list(bits(4))
[(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1),
 (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1),
 (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1),
 (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]

>>> sum(1 for u in bits(9))
512