程序員的算法趣題Q46: 唯一的OX序列

y1chuan 發(fā)布于2021-09-30 09:47 / 2225人閱讀

摘要：可以在遍歷所有矩陣時(shí)，對(duì)各種出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，最后計(jì)數(shù)值為的個(gè)數(shù)即為所求結(jié)果。上一篇排序交換次數(shù)的最少化排序交換次數(shù)的最少化本系列總目錄參見(jiàn)程序員的算法趣題詳細(xì)分析和全解程序員的算法趣題詳細(xì)分析和全解

1. 問(wèn)題描述

2. 解題分析

3. 代碼及測(cè)試

4. 后記

1. 問(wèn)題描述

?????????當(dāng)n=4時(shí)，像上述例子一樣，根據(jù)統(tǒng)計(jì)結(jié)果重新排列O和X的位置，只有一種排列方式的O和X的排列一共有多少種呢？

2. 解題分析

????????因?yàn)槭菍?duì)O計(jì)數(shù)，可以用1代表O，用0代表x，這樣原矩陣就轉(zhuǎn)化為一個(gè)二進(jìn)制矩陣。

????????以下采用暴力搜索法。

????????對(duì)N*N的所有可能的二進(jìn)制矩陣進(jìn)行N行和N列的，所得的2*N個(gè)值形成的排列{r1_sum, r2_sum, …,rN_sum, c1_sum, c2_sum, …, cN_sum }構(gòu)成這個(gè)矩陣的signature。然后查詢值對(duì)應(yīng)唯一的矩陣的signature的個(gè)數(shù)。可以在遍歷所有矩陣時(shí)，對(duì)各種signature出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù)，最后計(jì)數(shù)值為1的signature個(gè)數(shù)即為所求結(jié)果。signature出現(xiàn)的次數(shù)可以用哈希表來(lái)存儲(chǔ)，在python中就是dict()。

????????N*N的所有可能的二進(jìn)制矩陣種類數(shù)為 , N=4時(shí)為65536，隨著N增大急劇增大。

????????算法流程如下所示：

3. 代碼及測(cè)試

# -*- 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))

????????運(yùn)行結(jié)果：N = 4, count=6902, tCost = ?0.891(sec)

4. 后記

????????有兩個(gè)可能改進(jìn)方案：

用二進(jìn)制的形式來(lái)表示矩陣，以位操作的方式實(shí)現(xiàn)行和以及列和計(jì)算
矩陣中任意一個(gè)子矩陣的4個(gè)頂點(diǎn)按對(duì)角線分為兩組，一組為全0、另一組為全1的情況下，很明顯可以構(gòu)成出和它所對(duì)應(yīng)相同的signature的不同矩陣，因此可以排除在搜索范圍之外

????????以后回頭來(lái)補(bǔ)上這些改進(jìn)解。

? ? ? ? 上一篇：Q45: 排序交換次數(shù)的最少化? ? ? ??

????????本系列總目錄參見(jiàn)：程序員的算法趣題：詳細(xì)分析和Python全解