目錄
1。 問題描述
2。 解題分析
3。 程式碼及測試
4。 後記
1. 問題描述
當n=4時，像上述例子一樣，根據統計結果重新排列O和X的位置，只有一種排列方式的O和X的排列一共有多少種呢？
2. 解題分析
因為是對O計數，可以用1代表O，用0代表x，這樣原矩陣就轉化為一個二進位制矩陣。
以下采用暴力搜尋法。
對N*N的所有可能的二進位制矩陣進行N行和N列的，所得的2*N個值形成的排列{r1_sum， r2_sum， …，rN_sum， c1_sum， c2_sum， …， cN_sum }構成這個矩陣的signature。然後查詢值對應唯一的矩陣的signature的個數。可以在遍歷所有矩陣時，對各種signature出現的次數進行計數，最後計數值為1的signature個數即為所求結果。signature出現的次數可以用雜湊表來儲存，在python中就是dict（）。
N*N的所有可能的二進位制矩陣種類數為 ， N=4時為65536，隨著N增大急劇增大。
演算法流程如下所示：
3. 程式碼及測試
執行結果：N = 4， count=6902， tCost = 0。891（sec）
4. 後記
有兩個可能改進方案：
用二進位制的形式來表示矩陣，以位操作的方式實現行和以及列和計算
矩陣中任意一個子矩陣的4個頂點按對角線分為兩組，一組為全0、另一組為全1的情況下，很明顯可以構成出和它所對應相同的signature的不同矩陣，因此可以排除在搜尋範圍之外。
