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

目錄

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. 代碼及測試

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 29 07:51:03 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
from   collections import deque
import itertools as it
import numpy as np

N = 4
sigCount = 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]  = 1

count = 0
for key in sigCount:
    if sigCount[key] == 1:
        count += 1
tCost = time.perf_counter() - tStart

print('N = {0}, count={1}, tCost = {2:6.3f}(sec)'.format(N,count,tCost))   
           

        運作結果：N = 4, count=6902, tCost =  0.891(sec)

4. 後記

        有兩個可能改進方案：

1. 用二進制的形式來表示矩陣，以位操作的方式實作行和以及列和計算
2. 矩陣中任意一個子矩陣的4個頂點按對角線分為兩組，一組為全0、另一組為全1的情況下，很明顯可以構成出和它所對應相同的signature的不同矩陣，是以可以排除在搜尋範圍之外

        以後回頭來補上這些改進解。

        上一篇：Q45: 排序交換次數的最少化        

        下一篇：程式員的算法趣題Q47: 格雷碼循環

        本系列總目錄參見：程式員的算法趣題：詳細分析和Python全解