Phương pháp hiệu quả để có được một số, không thể tạo ra từ bất kỳ kết hợp XORing nào

Question

Nếu có bất kỳ số nào trong phạm vi [0 .. 2 ] không thể tạo thành phần XOR của một hoặc nhiều số từ một tập hợp nhất định, có phương pháp hiệu quả nào in ít nhất một trong số các số không truy cập được hoặc kết thúc bằng thông tin, rằng không có số không truy cập được không? Vấn đề này có tên không? Nó có tương tự như một vấn đề khác hay bạn có bất kỳ ý tưởng nào, làm thế nào để giải quyết nó?

Answer 1

Mỗi số có thể được coi là vectơ trong không gian vectơ (Z/2)^64 trên Z/2. Về cơ bản, bạn muốn biết các vectơ có cho toàn bộ không gian không, và nếu không, để tạo ra một không gian mở rộng (ngoại trừ khoảng thời gian luôn bao gồm véc tơ không - bạn sẽ phải đặc biệt trường hợp này nếu bạn thực sự muốn một hoặc nhiều) . Điều này có thể được thực hiện thông qua loại bỏ Gaussian.

Trong không gian vectơ đặc biệt này, loại bỏ Gaussian khá đơn giản. Bắt đầu với một bộ trống cho cơ sở. Làm như sau cho đến khi không còn số nữa. (1) Vứt bỏ tất cả các con số bằng không. (2) Quét số bit thấp nhất của các số còn lại (bit thấp nhất cho x là x & ~(x - 1)) và chọn một bit có bộ bit đặt hàng thấp nhất. (3) Đặt nó trên cơ sở. (4) Cập nhật tất cả các số khác với cùng một bit được thiết lập bởi XORing nó với phần tử cơ sở mới. Không còn số nào có bit này hoặc bất kỳ bộ bit đặt hàng nào thấp hơn, vì vậy chúng tôi sẽ chấm dứt sau 64 lần lặp lại.

Cuối cùng, nếu có 64 phần tử thì không gian con là mọi thứ. Nếu không, chúng tôi đã ít hơn 64 lần lặp lại và bỏ qua một chút: số chỉ có bit này không được kéo dài.

Để không có trường hợp đặc biệt: không là một tùy chọn nếu và chỉ khi chúng tôi không bao giờ vứt bỏ một số (tức là, các vectơ đầu vào độc lập).

---

Ví dụ trên số 4-bit

Bắt đầu với 0110, 0011, 1001, 1010. Chọn 0011 bởi vì nó có những thiết lập bit. Cơ sở bây giờ là {0011}. Các vectơ khác là {0110, 1010, 1010}; lưu ý rằng 1010 đầu tiên = 1001 XOR 0011.

Chọn 0110 vì nó có bộ bit twos. Cơ sở bây giờ là {0011, 0110}. Các vectơ khác là {1100, 1100}.

Chọn 1100. Cơ sở giờ là {0011, 0110, 1100}. Các vectơ khác là {0000}.

Vứt bỏ 0000. Chúng tôi đã hoàn tất. Chúng tôi bỏ qua bit thứ tự cao, vì vậy 1000 không nằm trong nhịp.

Answer 2

Vì nhạc rap chỉ ra bạn có thể nghĩ ra vấn đề khi tìm cơ sở trong không gian vectơ. Tuy nhiên, không nhất thiết phải giải quyết nó hoàn toàn, chỉ để tìm xem nó có khả thi hay không, và nếu không: đưa ra một giá trị ví dụ (đó là một vector nhị phân) mà không thể được mô tả dưới dạng bộ được cung cấp .

Điều này có thể được thực hiện trong O (n^2) về kích thước của bộ đầu vào. Điều này nên được so sánh với Loại trừ Gauss là O (n^3), http://en.wikipedia.org/wiki/Gaussian_elimination.

64 bit không có vấn đề gì cả. Với ví dụ mã python dưới 1000 bit với một tập hợp với 1000 giá trị ngẫu nhiên từ 0 đến 2^1000-1 mất khoảng một giây.

Thay vì thực hiện loại bỏ Gauss nó đủ để tìm hiểu xem chúng ta có thể viết lại ma trận của tất cả các bit vào mẫu hình tam giác, chẳng hạn như: (đối với phiên bản 4 bit :)

original  triangular 
1110 14   1110 14 
1011 11   111 7 
    111 7   11 3 
    11 3   1 1 
    1 1   0 0 

Các tác phẩm giải pháp như thế này: Đầu tiên tất cả các giá trị ban đầu với cùng một bit quan trọng nhất là các vị trí cùng nhau trong một danh sách các danh sách. Ví dụ:

[[14,11],[7],[3],[1],[]] 

Mục nhập trống cuối cùng thể hiện không có số 0 trong danh sách gốc. Bây giờ, phải mất một giá trị từ sự xâm nhập đầu tiên và thay thế mà nhập với một danh sách chứa chỉ số đó:

[[14],[7],[3],[1],[]] 

và sau đó lưu trữ các xor số giữ với tất cả các mục gỡ bỏ ở đúng nơi trong vector. Đối với trường hợp của chúng tôi, chúng tôi có 14^11 = 5 như vậy:

[[14],[7,5],[3],[1],[]] 

Bí quyết là chúng tôi không cần quét và cập nhật tất cả các giá trị khác, chỉ các giá trị có cùng bit quan trọng nhất.

Bây giờ, xử lý mục 7,5 theo cách tương tự. Giữ 7, thêm 7^5 = 2 vào danh sách:

[[14],[7],[3,2],[1],[]] 

Bây giờ 3,2 lá [3] và thêm 1:

[[14],[7],[3],[1,1],[]] 

Và 1,1 lá [1] và thêm 0 đến mục cuối cùng cho phép các giá trị không có chút thiết lập:

[[14],[7],[3],[1],[0]] 

Nếu cuối cùng vector chứa ít nhất một số ở mỗi mục vector (như trong ví dụ của chúng tôi) cơ sở đã hoàn thành và bất kỳ số lượng phù hợp.

Dưới đây là đoạn code hoàn chỉnh:

# return leading bit index ir -1 for 0. 
# example 1 -> 0 
# example 9 -> 3 
def leadbit(v): 
    # there are other ways, yes... 
    return len(bin(v))-3 if v else -1 

def examinebits(baselist,nbitbuckets): 
    # index 1 is least significant bit. 
    # index 0 represent the value 0  
    bitbuckets=[[] for x in range(nbitbuckets+1)] 
    for j in baselist: 
     bitbuckets[leadbit(j)+1].append(j) 
    for i in reversed(range(len(bitbuckets))): 
     if bitbuckets[i]: 
      # leave just the first value of all in bucket i 
      bitbuckets[i],newb=[bitbuckets[i][0]],bitbuckets[i][1:] 
      # distribute the subleading values into their buckets 
      for ni in newb: 
       q=bitbuckets[i][0]^ni 
       lb=leadbit(q)+1 
       if lb: 
        bitbuckets[lb].append(q) 
       else: 
        bitbuckets[0]=[0] 
     else: 
      v=2**(i-1) if i else 0 
      print "bit missing: %d. Impossible value: %s == %d"%(i-1,bin(v),v) 
      return (bitbuckets,[i])  
    return (bitbuckets,[]) 

sử dụng Ví dụ: (8 bit)

import random 
nbits=8 
basesize=8 
topval=int(2**nbits) 
# random set of values to try: 
basel=[random.randint(0,topval-1) for dummy in range(basesize)] 
bl,ii=examinebits(basel,nbits) 

bl bây giờ là danh sách tam giác của các giá trị, lên đến điểm mà nó là không thể (trong trường hợp). Thiếu bit (nếu có) được tìm thấy trong ii [0].

Đối với các thiết lập cố gắng sau các giá trị: [242, 242, 199, 197, 177, 177, 133, 36] phiên bản tam giác là:

base value: 10110001 177 
base value: 1110110 118 
base value: 100100 36 
base value: 10000 16 
first missing bit: 3 val: 8 
(the below values where not completely processed) 
base value:  10 2 
base value:  1 1 
base value:  0 0 

Danh sách trên được in như thế này:

for i in range(len(bl)): 
    bb=bl[len(bl)-i-1] 
    if ii and len(bl)-ii[0] == i: 
     print "example missing bit:" ,(ii[0]-1), "val:", 2**(ii[0]-1) 
     print "(the below values where not completely processed)" 
    if len(bb): 
     b=bb[0] 
     print ("base value: %"+str(nbits)+"s") %(bin(b)[2:]), b