Generowanie sekwencji łańcuchów binarnych z symbolami k, gdzie następny ciąg różni się dwucyfrowo

Question

Zastanawiam się, czy algorytm generuje sekwencję ciągów binarnych o długości nz symbolami k, gdzie następny ciąg różni się dwucyfrowo.

Na przykład:

11100 
11010 
11001 
10101 
10110 
10011 
00111 
01011 
01101 
01110 
11100 

Oczywiście, nie należy stosować wszystkie n \choose k ciągów binarnych.

Answer 1

Powinieneś przeczytać my blog post na temat tego rodzaju permutacji (między innymi), aby uzyskać więcej tła - i śledzić niektóre z nich.

Oto wersja z moich leksykograficznego permutacji generator fashioned po sekwencji generacji Steinhaus-Johnson-Trotter generatorów permutacji, które wykonuje na wniosek:

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' 

Wyjście z powyższego programu jest następujący przykład:

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. Weźmy na gray-code(sekwencja w którym każda liczba kolejnych różni się o jeden bit).
2. Dodaj inny bit i przełącz go między 0 i 1.

 
0000 
1001 
0011 
1010 
0110 
1111 
0101 
1100 

To będzie generować dokładnie połowa ciągów n-bitowych. Jest to najbardziej możliwe do uzyskania - druga połowa nie może zostać wygenerowana, ponieważ, na przykład, zaczynając od ciągu wszystkich 0 i zmieniając dwa bity na raz, zawsze będzie parzysta liczba 1.

Answer 3

Myślę, że możesz ustawić to za pomocą rekursji.

Zainspirował mnie następującej tożsamości:

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

więc zdefiniować funkcję F (n, k), który wytwarza żądany sekwencję (tj sekwencja binarnych ciągów o długości n z dokładnie bitów k ustawione tak, że kolejne ciągi różnią się dwoma bitami).

Po pierwsze, zauważ, że możemy zmienić kolejność kolumn F (n, k) w dowolny sposób, jaki nam się podoba i wyprodukować kolejny, równie ważny, F (n, k).

Powyższa tożsamość sugeruje, że budujemy F (n, k) za pomocą F (n-1, k-1) i F (n-1, k). Niech A będzie ciągiem uzyskanym przez zmianę kolejności kolumn F (n-1, k-1), tak aby ostatni ciąg kończył się w k-1 1 s, a następnie dodawanie do każdego z nich 1. Niech B będzie ciągiem uzyskanym przez zmianę kolejności kolumn F (n-1, k) tak, aby pierwszy ciąg zakończył się k 1 s, a następnie dodano do każdego z nich 0. Wtedy F (n, k) jest po prostu połączeniem A i B. Wynikiem jest poprawny F (n, k), jako wewnętrzny dla A i B ciągi różnią się dwoma bitami, a ostatni ciąg A i pierwszy ciąg B różni się dwoma bitami (k + 1 do ostatniego i ostatni bit).

Pokażę przykład używając n = 5, k = 2. Otrzymujemy przez rekursji następujące dwie sekwencje F:

F(4,1): 0001 
     0010 
     0100 
     1000 

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

Aby dokonać, zamienić pierwszą i ostatnią kolumnę F (4,1) i dodać 1 do siebie:

A: 10001 
    00101 
    01001 
    00011 

dokonać B brak swapy kolumna jest konieczne, tak, że wystarczy dodać 0 każdym rzędzie F, (4,2):

B: 00110 
    01010 
    10010 
    10100 
    01100 
    11000 

to F (5,2) jest tylko połączeniem a i B.