資訊專欄INFORMATION COLUMN
摘要：可以在遍歷所有矩陣時，對各種出現(xiàn)的次數進行計數，最后計數值為的個數即為所求結果。上一篇排序交換次數的最少化排序交換次數的最少化本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解
目錄
?????????當n=4時，像上述例子一樣，根據統(tǒng)計結果重新排列O和X的位置，只有一種排列方式的O和X的排列一共有多少種呢？
????????因為是對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的個數?？梢栽诒闅v所有矩陣時，對各種signature出現(xiàn)的次數進行計數，最后計數值為1的signature個數即為所求結果。signature出現(xiàn)的次數可以用哈希表來存儲，在python中就是dict()。
????????N*N的所有可能的二進制矩陣種類數為 , N=4時為65536，隨著N增大急劇增大。
????????算法流程如下所示：
?
?
# -*- coding: utf-8 -*-"""Created on Wed Sep 29 07:51:03 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom typing import List# from queue import Queuefrom collections import dequeimport itertools as itimport numpy as npN = 4sigCount = dict()tStart = time.perf_counter()for node in it.product([0,1],repeat=N**2): a = np.array(node).reshape(N,N) # print(a) col_sum = np.sum(a,axis=0) row_sum = np.sum(a,axis=1) sig = tuple(np.concatenate((col_sum,row_sum))) if sig in sigCount: sigCount[sig] += 1 else: sigCount[sig] = 1count = 0for key in sigCount: if sigCount[key] == 1: count += 1tCost = time.perf_counter() - tStartprint("N = {0}, count={1}, tCost = {2:6.3f}(sec)".format(N,count,tCost)) ????????運行結果：N = 4, count=6902, tCost = ?0.891(sec)
????????有兩個可能改進方案：
????????以后回頭來補上這些改進解。
? ? ? ? 上一篇：Q45: 排序交換次數的最少化? ? ? ??
????????本系列總目錄參見：程序員的算法趣題：詳細分析和Python全解
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/121664.html
摘要：能以最少交換次數到達升序有序排列記為的數列記為就等價于從代表的節(jié)點在這張圖中到達對應的節(jié)點的最短路徑長度。上一篇質數矩陣質數矩陣下一篇唯一的序列本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 4. 后記 ...
摘要：漢明距離可以用異或操作實現(xiàn)。這個問題其實可以看作是，具有個節(jié)點的全連接無向圖，每條邊的權重值代表兩個節(jié)點所代表的數字的段碼顯示的二進制表示之間的漢明距離。 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問題描述 ????????問題：求把10個數字全部顯示出來時，亮燈/滅...
摘要：基于以上討論可得，本題求解流程如下所示代碼及測試運行結果上一篇水果酥餅日下一篇異或楊輝三角形本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 3. 代碼及測試 1. 問題描述 ????????六度空間理論非常有名。大概的意思是1個人只需要通過6個中間人就...
摘要：但是由于不能使用作為，所以將表示狀態(tài)的列表轉換為后再用作的。上一篇將牌洗為逆序下一篇糖果惡作劇本系列總目錄參見程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 2.1?節(jié)點狀態(tài)表示 ???????2.2?鄰節(jié)點搜索 ???????2.3?路徑歷史記憶以及判斷鄰節(jié)點是否在...
摘要：中的統(tǒng)一的終點是全白狀態(tài)。比如說，的第個數恰好是，它可以由根據題設規(guī)則重排而得。上一篇填充白色填充白色下一篇優(yōu)雅的地址本系列總目錄參見程序員的算法趣題詳細分析和全解程序員的算法趣題詳細分析和全解 目錄 1. 問題描述 2. 解題分析 2.1??Naive Approach--正向全量搜索 ...
閱讀 2209·2021-09-30 09:47
閱讀 959·2021-08-27 13:01
閱讀 2959·2019-08-30 15:54
閱讀 3685·2019-08-30 15:53
閱讀 825·2019-08-29 14:07
閱讀 710·2019-08-28 18:16
閱讀 795·2019-08-26 18:37
閱讀 1406·2019-08-26 13:27
