当n=4时,像上述例子一样,根据统计结果重新排列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的个数。可以在遍历所有矩阵时,对各种signature出现的次数进行计数,最后计数值为1的signature个数即为所求结果。signature出现的次数可以用哈希表来存储,在python中就是dict()。
N*N的所有可能的二进制矩阵种类数为, N=4时为65536,随着N增大急剧增大。
算法流程如下所示:
- # -*- 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)
有两个可能改进方案:
以后回头来补上这些改进解。