2025年3月15日 星期六 甲辰(龙)年 月十四 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q46: 唯一的OX序列

时间:12-31来源:作者:点击数:37

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的不同矩阵,因此可以排除在搜索范围之外

以后回头来补上这些改进解。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门