如何加速指數時間碼

Question

我正在寫一個模擬。我需要解決的問題如下。

我給出了一個長度爲l的隨機二進制向量t（python中的一個列表）。然後，我對相同長度的二進制向量進行採樣，並測量每個採樣向量與t之間的漢明距離（即對齊失配的數量）並存儲結果。我想確定長度爲l的二進制向量與迄今爲止發現的距離是否相符。顯然t是但它也可能是其他許多人也是。

我的代碼如下。

import random 
import itertools 
import operator 

l=23 
t = [random.randint(0,1) for b in range(l)] 
stringsleft = set(itertools.product([0,1],repeat=l)) 

xcoords = [] 
ycoords = [] 
iters = l 
for i in xrange(iters): 
    print i, len(stringsleft) 
    xcoords.append(i) 
    ycoords.append(math.log(len(stringsleft))) 
    pattern = [random.randint(0,1) for b in range(l)] 
    distance = sum(itertools.imap(operator.ne, pattern, t)) 
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if sum(itertools.imap(operator.ne, pattern, y)) == distance])) 

不幸的是很慢的，並且使用了大量的內存，並在所有如果我增加l至30是否有可能加快這解決l=30情況下不能正常工作？

更新
我由整數替換名單所以現在有l=26運行做了一個小的優化。

l=26 
t = random.randint(0,2**l) 
stringsleft = set(range(2**l)) 
xcoords = [] 
ycoords = [] 
iters = l 
for i in xrange(iters): 
    print i, len(stringsleft) 
    if (len(stringsleft) > 1): 
     xcoords.append(i) 
     ycoords.append(math.log(len(stringsleft),2)) 
    pattern = random.randint(0,2**l) 
    distance = bin(pattern^t).count('1') 
    stringsleft = stringsleft.intersection(set([y for y in stringsleft if bin(pattern^y).count('1') == distance])) 

是阻止我前往l=30的問題是內存的使用，而不是時間。

Answer 1

我一直在想這個，我最後寫的程序基本上是Sneftel的方法。起初，沒有選擇，我們有漢明距離列表。然後說我們爲第一個值選擇1，那麼如果序列的其餘部分與漢明距離兼容，那麼所有具有0的序列只能兼容 - 1.與1相同。

我也有一個遞歸的版本，但是使用堆棧將其更改爲循環，以便我可以使用yield將其轉換爲可生成兼容序列的生成器。

我做的一個優化是，如果在海明距離大於1/2時出現猜測，我將0和1翻轉，這樣新的猜測就保證了海明距離< = 1/2。

如果l = 30，我會得到不錯的表現，儘管它取決於猜測的數量以及他們是多麼幸運。

由於我較早的主謀思想，我仍然在想'猜測'的角度來思考，試圖找出'序列'。

代碼：

import random 

LENGTH = 30 
NUMGUESSES = 20 


def guess(): 
    return [random.randint(0, 1) for i in range(LENGTH)] 

SEQUENCE = guess() 
GUESSES = [guess() for i in range(NUMGUESSES)] 


def hamming(a, b): 
    return sum(aelem != belem for aelem, belem in zip(a, b)) 


# Flip if hamming > LENGTH/2 
mid = LENGTH/2 
for i in range(NUMGUESSES): 
    if hamming(SEQUENCE, GUESSES[i]) > mid: 
     GUESSES[i] = [1 - g for g in GUESSES[i]] 

HAMMINGS = [hamming(SEQUENCE, g) for g in GUESSES] 

print "Sequence:", SEQUENCE 
print 
for h, g in zip(HAMMINGS, GUESSES): 
    print "Guess and hamming:", g, h 
print 


def compatible_sequences(guesses, hammings): 
    # Use a stack instead of recursion, so we can make this a generator. 
    stack = [] 
    # Start: we have chosen nothing yet, and the hammings have start values 
    stack.append(([], hammings)) 

    while stack: 
     so_far, hammingsleft = stack.pop() 

     if -1 in hammingsleft: 
      # Skip, choices so far are incompatible with the guesses 
      continue 

     if len(so_far) == LENGTH: 
      # Success if all the Hamming distances were exactly correct 
      if all(h == 0 for h in hammingsleft): 
       yield so_far 
      continue 

     # Not done yet, add choices 0 and 1 to the queue 
     place_in_guess = len(so_far) 
     for choice in (1, 0): 
      stack.append(
       (so_far + [choice], 
       [h - (g[place_in_guess] != choice) 
        for h, g in zip(hammingsleft, guesses)])) 

print "Compatible sequences:" 
for nr, sequence in enumerate(compatible_sequences(GUESSES, HAMMINGS), 1): 
    print nr, sequence 

Answer 2

編輯：我錯了。在Mastermind中，您也瞭解正確的顏色數量，但不在正確的位置。這改變了可能的解決方案的數量，因此兩個問題之間沒有明顯的準確轉換，所以我不能在下面做出結論。現在留下答案，也許它可以幫助別人思考問題。

我回答：

壞消息，它至少NP完全問題。

你的問題讓我想起了遊戲Mastermind（Wikipedia）。在那個頁面上，他們還提到了「主謀可滿足性問題：給定一套雙色的主謀猜測和答案，有沒有可能的猜測？

因此，這個問題有比你更多的信息：Mastermind給出的數量在正確的位置修正顏色（==長度減去哈蒙德距離），再加上錯誤位置的正確顏色的數量，並且他們只是試圖確定可能性的數量是否大於0.而這個問題是根據this paper

Answer 3

回溯算法可以在這裏工作，狀態將是一個（部分）向量和每個示例向量的剩餘漢明距離給定一個狀態，你嘗試追加一個0，並減少每個向量的漢明距離有一個1我那個地方。如果任何距離降到零以下，解決方案是不可接受的;否則，你遞歸。然後你用1做同樣的事情。一旦矢量完成，如果所有距離都爲零，就輸出它。

這仍然是指數級的時間，但應該快得多。