Minimal unione insieme bitstring con turni algoritmo

Question

sto cercando un algoritmo per risolvere, o almeno un nome proprio per il seguente problema:

---

Ho una serie B di stringhe di bit. L'algoritmo dovrebbe trovare un minimo (definito come "minor quantità di bit aventi SET") stringa di bit S tale che:

Per tutti b in B, esiste uno spostamento N (in ℤ) tale che (S << N) & b == b.

---

Se aiuta, ogni b si inserisce in una parola della macchina, e | B | è dell'ordine di un paio di centinaia.

---

credo che possiamo supporre (senza perdita di generalità) che l'LSB di S e ogni b è 1.

Questa mi sembra una sorta di multiple sequence-alignment problema.

se possiamo trovare ogni N _i per ogni b _i in B (i = 1 .. | B |), sembra che S è solo il bit a bit o tutto (b _i >>N _i).

mia intuizione è, il primo passo è quello di rimuovere ogni b da B per i quali esiste un'altra stringa di bit c in B e certo spostamento M tale che b & (c << M) == b. Qual'è il prossimo?

Answer 1

La mia istanza specifica di B era abbastanza piccola da essere suscettibile alla forza bruta, con alcuni accorgimenti per potare la ricerca.

Con le seguenti funzioni già definite,

• snoob, restituisce il numero successivo più alto con lo stesso numero di bit impostati (come definito nella fig Delight Hacker.2-1 (od originariamente, HAKMEM articolo 175))
• popcount, restituisce il numero di bit a 1 nella sua tesi
• clz, restituisce il numero di zeri consecutivi alla fine più significativo della sua tesi

pseudocodice per la mia soluzione è la seguente:

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 

il loop primi turni di destra ogni b quindi la sua LSB è 1; questo ci consente di utilizzare solo turni giusti per N successivamente.

Il ciclo su S inizia con il numero più piccolo con ones bit impostati; la condizione di arresto del ciclo non è del tutto corretta, ma funziona abbastanza bene per i miei scopi.

Il loop oltre N inizia con l'LSB di S e b allineati, e poi va a più significativi un bit di S e b allineati.

---

Per ora, sto lasciando la questione irrisolta per vedere se una soluzione adeguata non forza bruta viene intorno, o fino a quando qualcuno dice che il problema è NP-hard.