Tạo chuỗi các chuỗi nhị phân với chuỗi k, chuỗi tiếp theo khác hai chữ số

Question

Tôi tự hỏi về trình tự tạo chuỗi nhị phân có độ dài n với k, trong đó chuỗi tiếp theo khác hai chữ số.

Ví dụ:

11100 
11010 
11001 
10101 
10110 
10011 
00111 
01011 
01101 
01110 
11100 

Tất nhiên, có phải được sử dụng tất cả n \choose k chuỗi nhị phân.

Answer 1

Bạn nên đọc my blog post về loại hoán vị này (trong số những thứ khác) để có thêm nền tảng - và theo một số liên kết ở đó.

Đây là một phiên bản của hoán vị tự từ điển của tôi Generator fashioned sau khi trình tự thế hệ của máy phát điện hoán vị Steinhaus-Johnson-Trotter mà không theo yêu cầu:

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' 

Kết quả của chương trình trên là như sau ví dụ:

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. Chụp gray-code(chuỗi trong đó mỗi số liên tiếp khác nhau một chút).
2. Chuẩn bị bit khác và chu kỳ giữa 0 và 1.

 
0000 
1001 
0011 
1010 
0110 
1111 
0101 
1100 

Điều này sẽ tạo ra chính xác một nửa số chuỗi n bit. Đây là phần lớn bạn có thể nhận được - một nửa khác không thể được tạo ra bởi vì, ví dụ, bắt đầu bằng một chuỗi tất cả các bit của 0 và thay đổi hai bit cùng một lúc, sẽ luôn có một số chẵn là 1.

Answer 3

Tôi nghĩ bạn có thể thiết lập điều này bằng cách sử dụng đệ quy.

Tôi đã lấy cảm hứng từ sắc sau đây:

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

Vì vậy, chúng ta định nghĩa một hàm F (n, k) mà tạo ra chuỗi yêu cầu (ví dụ, một chuỗi các chuỗi nhị phân có độ dài n có chính xác k bit thiết lập, sao cho các chuỗi liên tiếp khác nhau bởi hai bit).

Đầu tiên, quan sát rằng chúng ta có thể sắp xếp lại các cột F (n, k) theo bất kỳ cách nào chúng ta thích và tạo ra một giá trị khác, bằng nhau, F (n, k).

Danh tính trên cho thấy chúng tôi xây dựng F (n, k) sử dụng F (n-1, k-1) và F (n-1, k). Gọi A là các chuỗi thu được bằng cách sắp xếp lại các cột của F (n-1, k-1) sao cho chuỗi cuối cùng kết thúc bằng k-1 1 s, sau đó thêm 1 vào mỗi chuỗi. Gọi B là các chuỗi thu được bằng cách sắp xếp lại các cột của F (n-1, k) sao cho chuỗi đầu tiên kết thúc bằng k 1 s, sau đó thêm 0 vào mỗi chuỗi. Sau đó F (n, k) chỉ là kết nối của A và B. Kết quả là một F (n, k) hợp lệ, như bên trong A và B các chuỗi khác nhau bởi hai bit, và chuỗi cuối cùng của A và đầu tiên chuỗi B khác nhau bởi hai bit (k + 1 đến bit cuối cùng và bit cuối cùng).

Tôi sẽ hiển thị ví dụ sử dụng n = 5, k = 2. Chúng tôi nhận được bằng đệ quy hai chuỗi F sau:

F(4,1): 0001 
     0010 
     0100 
     1000 

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

để làm cho A, trao đổi các cột đầu tiên và cuối cùng của F (4,1) và thêm 1 cho mỗi:

A: 10001 
    00101 
    01001 
    00011 

để làm cho B , không có giao dịch hoán đổi cột là cần thiết, vì vậy chúng tôi chỉ cần thêm một 0 để mỗi hàng của F (4,2):

B: 00110 
    01010 
    10010 
    10100 
    01100 
    11000 

Sau đó F (5,2) chỉ là sự nối của A và B.