Minimal bitstring bộ công đoàn với sự thay đổi thuật toán

Question

Tôi đang tìm một thuật toán để giải quyết, hoặc ít nhất là một tên thích hợp cho các vấn đề sau đây:

---

Tôi đã một tập B của bitstrings. Thuật toán nên tìm một tối thiểu (được định nghĩa là "có bit ít nhất thiết") bitstring S ví dụ rằng:

Đối với tất cả b trong B, có tồn tại một sự thay đổi N (trong ℤ) sao cho (S << N) & b == b.

---

Nếu nó giúp, mỗi b phù hợp trong một từ máy, và | B | là theo thứ tự của một vài trăm.

---

Tôi nghĩ chúng ta có thể giả định (mà không mất tính tổng quát) mà LSB của S và mỗi b là 1.

này vẻ với tôi như một số loại multiple sequence-alignment vấn đề.

Nếu chúng ta có thể tìm thấy nhau N _i cho mỗi b _i trong B (i = 1 .. | B |), nó trông giống như S chỉ là bitwise hoặc trên tất cả (b _i >>N _i).

trực giác của tôi là, bước đầu tiên là để loại bỏ tất cả các b từ B mà tồn tại khác bitstring c trong B và một số thay đổi M mà b & (c << M) == b. Cái gì tiếp theo?

Answer 1

Ví dụ cụ thể của tôi là B đủ nhỏ để có thể thực hiện được sức mạnh vũ phu, với một vài thủ thuật để cắt giảm tìm kiếm.

Với các chức năng sau đã được xác định,

• snoob, trả về số cao nhất kế tiếp với cùng một số bit set (theo quy định tại Delight vả Hacker của.2-1 (hoặc ban, HAKMEM mục 175))
• popcount, trả về số 1-bit trong đối số của nó
• clz, trả về số zero liên tiếp vào cuối nhất-đáng kể đối số của nó

Mã giả cho giải pháp của tôi là như sau:

min_ones = max popcount(b) for b in B 
max_ones = popcount(~0) 

for i = 0 .. |B|-1: 
    while !(B[i] & 1): B[i] >>= 1 

found_ones = false 
for ones = min_ones .. max_ones: 
    if found_ones: break 
    for S = (1 << ones)-1; clz(S) > 0; S = snoob(S): 
     if !(S & 1): continue 
     for b in B: 
      found = false 
      for N = 0 .. clz(b) - clz(S): 
       if (S >> N) & b == b: 
        found = true 
        break 
      if !found: break 
     if found: 
      print(S) 
      found_ones = true 

Những thay đổi vòng lặp đầu tiên đúng mỗi b nên nó LSB là 1; điều này cho phép chúng tôi chỉ sử dụng đúng ca cho N sau.

Vòng lặp qua S bắt đầu bằng số nhỏ nhất với ones bit được đặt; điều kiện dừng vòng lặp không hoàn toàn chính xác, nhưng nó hoạt động đủ tốt cho mục đích của tôi.

Vòng lặp trên N bắt đầu với LSB của S và b thẳng hàng, và sau đó đi đến nhiều nhất đáng kể một mẩu S và b thẳng hàng.

---

Hiện tại, tôi để lại câu hỏi chưa được giải quyết để xem liệu có giải pháp không brute-force phù hợp hay cho đến khi ai đó nói vấn đề là NP-hard.