Generazione di sequenze di stringhe binarie con k dove la stringa successiva differisce in due cifre

Question

Mi chiedo in merito alla sequenza di generazione di stringhe binarie di lunghezza n con k quelle in cui la stringa successiva differisce in due cifre.

Ad esempio:

11100 
11010 
11001 
10101 
10110 
10011 
00111 
01011 
01101 
01110 
11100 

Naturalmente, ci deve essere utilizzato in tutte le n \choose k stringhe binarie.

Answer 1

Si consiglia di leggere my blog post su questo tipo di permutazione (tra le altre cose) per ottenere più background - e seguire alcuni dei collegamenti lì.

Ecco una versione dei miei permutazioni lessicografiche generatore modellato dopo la sequenza di generazione di generatori permutazione Steinhaus-Johnson-Trotter che fa come richiesto:

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' 

L'output del programma sopra è il seguente esempio:

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] 

Answer 2

1. Take a gray-code(sequenza in cui ogni numero successivo differisce di un bit).
2. Prevedere un altro bit e spostarlo tra 0 e 1.

 
0000 
1001 
0011 
1010 
0110 
1111 
0101 
1100 

Questo genererà esattamente la metà delle stringhe di n-bit. Questo è il massimo che si può ottenere - l'altra metà non può essere generata perché, ad esempio, iniziando con una stringa di tutti gli 0 e cambiando due bit alla volta, ci sarà sempre un numero pari di 1.

Answer 3

Penso che si possa impostare usando la ricorsione.

mi sono ispirato la seguente identità:

choose(n,k) = choose(n-1,k-1) + choose(n-1,k) 

Così si definisce una funzione F (n, k) che produce la sequenza richiesta (vale a dire, una sequenza di stringhe binarie di lunghezza n con esattamente k bit impostato, in modo tale che le stringhe successive differiscano di due bit).

Innanzitutto, osserviamo che possiamo riordinare le colonne di F (n, k) in qualsiasi modo ci piaccia e produrre un altro, altrettanto valido, F (n, k).

L'identità sopra suggerisce di costruire F (n, k) usando F (n-1, k-1) e F (n-1, k). Sia A essere stringhe ottenute riordinando le colonne di F (n-1, k-1) in modo che l'ultima stringa termini in k-1 1 s, quindi aggiungendo uno 1 a ciascuno. Sia B le stringhe ottenute riordinando le colonne di F (n-1, k) in modo che la prima stringa termini in k 1 s, quindi aggiungendo uno 0 a ciascuna. Quindi F (n, k) è solo la concatenazione di A e B. Il risultato è un F (n, k) valido, poiché all'interno di A e B le stringhe differiscono di due bit e l'ultima stringa di A e la prima la stringa di B differisce di due bit (il k + 1 ° all'ultimo bit e l'ultimo bit).

Mostrerò un esempio usando n = 5, k = 2. Otteniamo ricorsivamente seguenti due sequenze F:

F(4,1): 0001 
     0010 
     0100 
     1000 

F(4,2): 0011 
     0101 
     1001 
     1010 
     0110 
     1100 

per fare una, scambiare la prima e l'ultima colonna di F (4,1) e aggiungere 1 tra:

A: 10001 
    00101 
    01001 
    00011 

fare B , non sono necessarie swap colonna, quindi abbiamo aggiungere un 0 per ogni fila di F (4,2):

B: 00110 
    01010 
    10010 
    10100 
    01100 
    11000 

Poi F (5,2) è solo la concatenazione di a e B.