Me pregunto acerca del algoritmo que genera secuencia de cadenas binarias de longitud n con k unas donde la siguiente cadena difiere en dos dígitos.Generando secuencia de cadenas binarias con k donde la siguiente cadena difiere en dos dígitos
Por ejemplo:
11100
11010
11001
10101
10110
10011
00111
01011
01101
01110
11100
Por supuesto, no se deben utilizar todos los n \choose k cadenas binarias.
Debe leer my blog post en este tipo de permutación (entre otras cosas) para obtener más información y seguir algunos de los enlaces allí.
Aquí es una versión de mis permutaciones lexicográficas generador de moda después de la secuencia de generación de generadores de permutación Steinhaus-Johnson-Trotter que hace a lo solicitado:
def l_perm3(items):
'Generator yielding Lexicographic permutations of a list of items'
if not items:
yield [[]]
else:
dir = 1
new_items = []
this = [items.pop()]
for item in l_perm(items):
lenitem = len(item)
try:
# Never insert 'this' above any other 'this' in the item
maxinsert = item.index(this[0])
except ValueError:
maxinsert = lenitem
if dir == 1:
# step down
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem, -1, -1)
if i <= maxinsert]:
yield new_item
else:
# step up
for new_item in [item[:i] + this + item[i:]
for i in range(lenitem + 1)
if i <= maxinsert]:
yield new_item
dir *= -1
from math import factorial
def l_perm_length(items):
'''\
Returns the len of sequence of lexicographic perms of items.
Each item of items must itself be hashable'''
counts = [items.count(item) for item in set(items)]
ans = factorial(len(items))
for c in counts:
ans /= factorial(c)
return ans
if __name__ == '__main__':
n = [1, 1, 1, 0, 0]
print '\nLexicograpic Permutations of %i items: %r' % (len(n), n)
for i, x in enumerate(l_perm3(n[:])):
print('%3i %r' % (i, x))
assert i+1 == l_perm_length(n), 'Generated number of permutations is wrong'
La salida del programa anterior es el siguiente, por ejemplo:
Lexicograpic Permutations of 5 items: [1, 1, 1, 0, 0]
0 [1, 1, 1, 0, 0]
1 [1, 1, 0, 1, 0]
2 [1, 0, 1, 1, 0]
3 [0, 1, 1, 1, 0]
4 [0, 1, 1, 0, 1]
5 [1, 0, 1, 0, 1]
6 [1, 1, 0, 0, 1]
7 [1, 0, 0, 1, 1]
8 [0, 1, 0, 1, 1]
9 [0, 0, 1, 1, 1]
¡Esto es todo! ¡Muchas gracias! – ushik
0 y 1.0000 1001 0011 1010 0110 1111 0101 1100
Esto generará exactamente la mitad de las cadenas de n bits. Esto es lo máximo que puede obtener, la otra mitad no se puede generar porque, por ejemplo, comenzando con una cadena de 0 y cambiando dos bits a la vez, siempre habrá un número par de 1.
@Mooing: Eso funcionaría también. Sin embargo, mira mi edición. –
Eso no es lo que quería ya que necesito cadenas con ** exactamente k **. Su ejemplo tiene 0, 2, 2, 2, 2, 4, 2, 2 ... – ushik
Creo que puede configurar esto usando recursividad.
Estaba inspirado por la siguiente identidad:
choose(n,k) = choose(n-1,k-1) + choose(n-1,k)
Así que definir una función F (n, k) que produce la secuencia solicitada (es decir, una secuencia de cadenas binarias de longitud n con exactamente k bits set, tal que las cadenas sucesivas difieren en dos bits).
En primer lugar, tenga en cuenta que podemos reordenar las columnas de F (n, k) de la forma que deseemos y producir otra, igualmente válida, F (n, k).
La identidad anterior sugiere que construyamos F (n, k) usando F (n-1, k-1) y F (n-1, k). Sean A las cadenas obtenidas reordenando las columnas de F (n-1, k-1) para que la última cadena termine en k-1 1 s, y luego agregue un 1 a cada una. Deje B ser las cadenas obtenidas al reordenar las columnas de F (n-1, k) para que la primera cadena termine en k 1 s, y luego agregue un 0 a cada una. Entonces F (n, k) es simplemente la concatenación de A y B. El resultado es una F válida (n, k), como interna a A y B, las cadenas difieren en dos bits, y la última cadena de A y la primera la secuencia de B se diferencia en dos bits (el k + 1º al último bit y el último bit).
Mostraré un ejemplo usando n = 5, k = 2. Obtenemos mediante la repetición de las siguientes dos secuencias F:
F(4,1): 0001
0010
0100
1000
F(4,2): 0011
0101
1001
1010
0110
1100
para hacer una, cambiamos la primera y la última columna de F (4,1) y añadimos a cada 1:
A: 10001
00101
01001
00011
para hacer B , no hay permutas de columna son necesarios, por lo que sólo tiene que añadir un 0 a cada fila de F (4,2):
B: 00110
01010
10010
10100
01100
11000
Entonces F (5,2) es simplemente la concatenación de a y B.
Si es tarea, marque en consecuencia. y ¿qué quieres decir con n \ choose k? – Rndm
@shg no, no es una tarea. ;) y por n \ choose k Me refiero al número de k-combinaciones (coeficiente binomial). – ushik