如何找到給定的後續值的所有位掩碼組合可以是「0」，j可以是「1」？

輸入。
我有一個位數組大小n和兩個整數，1<=i<=n和0<=j<=n。 i指示後續數字的最大值，可以是0。 j指示後續數字的最大值，可以是1。如何找到給定的後續值的所有位掩碼組合可以是「0」，j可以是「1」？

所需的輸出
我搜索返回所有可能的比特陣列尺寸n滿足這些約束的方法。

只循環遍歷所有數組組合（首先沒有約束）會導致指數時間。（特別是如果i/j>>1，我想你可以做得更好）。如何有效地找到這些位掩碼組合？

例
輸入：i = 1，j = 2，n = 3

結果：可能的陣列是[0,1,0], [1,0,1],[1,1,0],[0,1,1]。

來源

2016-11-21 CanBeChangedLater.Hopefully

100111和011100是'i'還是'j'？ – Surt

使用遞歸公式，您可以修剪大部分搜索空間（任何時候遞歸調用將具有「i」或「j」負數，您可以修剪） –

對於100111，i => 2和j> = 3。對於011100，i => 2和j> = 3。（i和j表示相同的後續數字的最大值，輸入由兩個i，j和數組大小n組成） –

這是動態編程解決方案的不錯問題。有足夠的方法返回以給定數字（0或1）給定長度開始的字符串數量。比的長度n的位數是從0開始並與記憶化1.

簡單的Python溶液起始串的之和爲：

_c = {} # Cache 

def C(d, n, ij): 
    if n <= 1: 
     return 1 
    if (d, n) not in _c: 
     _c[(d, n)] = sum(C(1-d, n-x, ij) for x in xrange(1, min(ij[d], n)+1)) 
    return _c[(d, n)] 

def B(n, i, j): 
    ij = [i, j] # Easier to index 
    _c.clear() # Clears cache 
    return C(0, n, ij) + C(1, n, ij) 

print B(3, 1, 2) 
print B(300, 10, 20)

結果是：

4 
1896835555769011113367758506440713303464223490691007178590554687025004528364990337945924158

由於用於值給定的數字和長度取決於相反數字的值和長度小於給定的長度，解決方案也可以通過逐漸計算長度來獲得。 Python解決方案：

def D(n, i, j): 
    c0 = [1] # Initialize arrays 
    c1 = [1] 
    for x in xrange(1, n+1): # For each next digit calculate value 
     c0.append(sum(c1[x-y] for y in xrange(1, min(i, x)+1))) 
     c1.append(sum(c0[x-y] for y in xrange(1, min(j, x)+1))) 
    return c0[-1] + c1[-1] # Sum strings starting of length n with 0 and 1 

print D(3, 1, 2) 
print D(300, 10, 20)

後面的方法在C++中更容易實現。

來源

2016-11-23 20:14:19 Ante

如何找到給定的後續值的所有位掩碼組合可以是「0」，j可以是「1」？

回答

相關問題