位明智的操作邏輯

Question

我有兩個相同大小的數組（array1和array2）0和1的。我如何獲得與array1結果數組合併爲array2的所有數組？例如，如果array1 = [1,1,1]和array2 = [1,1,1]。輸出應該是全部八個數組：[0，0，0]，[1,0,0]，....，[1,1,1]。有沒有有效的解決方案呢，還是隻有蠻力的方法？我試圖計算明智的差異首先，如果任何位是負數，然後返回false（不可能結合第一個數組與任何類型的數組來獲得數組2）。如果所有比特都是非負數，那麼......如果差分中的比特爲0，則它​​可以被0或1代替（這是錯誤的假設，儘管如果array1 = [0,0]，array2 = [0 ，0]，並且如果差值任何位爲0，則需要陣列必須有1在那個地方，使其1

Answer 1

您可以通過評估建立在每個時隙i數字選項：

for d in (0, 1): 
    if (array1[i] or d) == array2[i]): 
     digits[i].append(d) 

然後你只需要遍歷i
的目標是建立一個列表列表：[[0,1],[1],[0,1]]顯示t他在每個插槽中有效的數字。然後你可以使用itertools.product()構建所有有效陣列：

arrays = list(itertools.product(*digits)) 

你可以把所有這些在一起使用列表理解，這將導致：

list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(array1, array2)])) 

在行動：

>>> import itertools as it 
>>> a1, a2 = [1,1,1], [1,1,1] 
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)])) 
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)] 

>>> a1, a2 = [1,0,0], [1,1,1] 
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)])) 
[(0, 1, 1), (1, 1, 1)] 

>>> a1, a2 = [1,0,0], [0,1,1] 
>>> list(it.product(*[[d for d in (0, 1) if (x or d) == y] for x, y in zip(a1, a2)])) 
[] 

Answer 2

這是我會怎麼去解決這個問題：

1. 首先，讓我們想想你需要找到所有的二進制值的數組，當它們通過一個已知的二進制值合併時（通過某個操作符），=一個新的二進制值，不要試圖解決這個問題，假設你需要去從00到11.有多少可能的答案？假設你需要去回答米11到11.有多少可能的答案？你能做得更好嗎（在最壞的情況下）比暴力方法更好嗎？這會給你一個複雜的界限。
2. 考慮到這個粗略的約束，解決了一些有點好奇的問題。再深入探討這個問題。什麼是'按位聯合操作符'？是'和'？是'還是'？這是更復雜的東西嗎？ 「按位」聽起來像B[i] = A[i] OR X[i]，但任何人都問這個問題可能平均別的東西..
3. 根據不同的回答問題1和問題2，你有很多在這裏工作。我可以考慮一些不同的選項，但我認爲從這裏你可以想出一個算法。
4. 一旦你有了一個解決方案，你需要考慮一下「我能在這裏做得更好嗎？」很多回歸到關於這個問題的最初印象以及它們是如何構建的以及你有多少/多少認爲你可以優化

Answer 3

注意：我將用示例輸入來解釋以下內容： A = [0 0 1 0 1 1], B = [1 1 1 0 1 1]

假設你要計算X的方程A OR X = B，讓我們看到的是什麼，在一個位的每個選擇和B選項：

A OR X = B 
-------------------- 
0   0  0 
0   1  1 
1   N.A. 0 
1   (0,1) 1 

1. 如果A任何位爲1，其對應的B位是0，沒有可能的解決方案。返回一個空集。
2. 如果A和B中的相應位爲1，則X中的相應位不重要。現在

，看到對於X一種解決方案是B本身（如果條件＃1，如上所述，是滿足）。因此，讓我們構建一個數字start_num = B。這將是一個解決方案，其他解決方案將由此構建。

start_num = B = [1 1 1 0 1 1]

的 '選擇' 位是那些其中X可以取任何值，即那些位置A=1和B=1。讓我們創建另一個數字choice = A AND B，以便choice = 1表示這些位置。另請注意，如果有k職位，其中choice = 1，解決方案總數爲2^k。

choice = A AND B = [0 0 1 0 1 1]，因此k = 3

店鋪在（長度k的）的陣列，這些 '選擇' 的位置，從右側開始（LSB = 0）。讓我們稱這個數組pos_array。

pos_array = [0 1 3]

注意，在start_num所有的「選擇」位設置爲1，因此，所有其他的解決方案將具有這些位設置爲0的部分（1 <= p <= k）現在我們知道哪些位需要改變，我們需要以有效的方式制定這些解決方案。

這可以通過將所有的解決方案按照先前的解決方案和當前的解決方案之間的差異僅在一個位置的順序進行，從而使其有效地計算解決方案。例如，如果我們有兩個「選擇」位，下面的解釋之間簡單地通過一個等差數列所有組合運行，並通過他們在1位變化得有條不紊的區別：（

1-bit-toggle-order    decreasing order 
----------------------   ---------------------- 
1 1 // start     1 1 // start      
1 0 // toggle bit 0    1 0 // subtract 1 
0 0 // toggle bit 1    0 1 // subtract 1 
0 1 // toggle bit 0    0 0 // subtract 1 

我們想要利用按位操作的速度，因此我們將使用1位切換順序）。

現在，我們將建立各自的解決方案：（這是不實際的C代碼，只是一個說明）

addToSet(start_num); // add the initial solution to the set 

for(i=1; i<2^k; i++) 
{ 
    pos = 0; 
    count = i; 
    while((count & 1) != 0) 
    { 
     count = count>>1; 
     pos++; 
    } 

    toggle(start_num[pos_array[pos]]); // update start_num by toggling the desired bit 
    addToSet(start_num); // Add the updated vector to the set 
} 

如果這個代碼在上面的例子中運行，以下切換語句將被執行：

toggle(start_num[0]) 
toggle(start_num[1]) 
toggle(start_num[0]) 
toggle(start_num[3]) 
toggle(start_num[0]) 
toggle(start_num[1]) 
toggle(start_num[0]) 

，這將導致在下面的添加：

addToSet([1 1 1 0 1 0]) 
addToSet([1 1 1 0 0 0]) 
addToSet([1 1 1 0 0 1]) 
addToSet([1 1 0 0 0 1]) 
addToSet([1 1 0 0 0 0]) 
addToSet([1 1 0 0 1 0]) 
addToSet([1 1 0 0 1 1]) 

，whic h，除了已經存在的初始解決方案[1 1 1 0 1 1]之外，完成該組。

---

注：我不是位運算的專家，除了其他的事情。我認爲有更好的方法來編寫算法，更好地使用位訪問指針和按位二進制操作（如果有人可以提出改進建議，會很高興）。我提出的解決方案是解決這個問題的一般方法。