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

y1chuan 发布于2021-09-30 09:47 / 2178人阅读

摘要：可以在遍历所有矩阵时，对各种出现的次数进行计数，最后计数值为的个数即为所求结果。上一篇排序交换次数的最少化排序交换次数的最少化本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解

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

4. 后记

有两个可能改进方案：

用二进制的形式来表示矩阵，以位操作的方式实现行和以及列和计算
矩阵中任意一个子矩阵的4个顶点按对角线分为两组，一组为全0、另一组为全1的情况下，很明显可以构成出和它所对应相同的signature的不同矩阵，因此可以排除在搜索范围之外

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

上一篇：Q45: 排序交换次数的最少化

本系列总目录参见：程序员的算法趣题：详细分析和Python全解

云服务器 GPU云服务器最短路算法的程序最复杂的程序算法最厉害的算法想法程序 linux 硬盘序列号唯一

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/121664.html

程序员的算法趣题Q45: 排序交换次数的最少化

摘要：能以最少交换次数到达升序有序排列记为的数列记为就等价于从代表的节点在这张图中到达对应的节点的最短路径长度。上一篇质数矩阵质数矩阵下一篇唯一的序列本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 ...

flybywind 2021-09-29 09:35 评论0 收藏0
程序员的算法趣题Q37: 翻转7段码(1)

摘要：汉明距离可以用异或操作实现。这个问题其实可以看作是，具有个节点的全连接无向图，每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述问题：求把10个数字全部显示出来时，亮灯/灭...

RdouTyping 2021-09-24 09:48 评论0 收藏0
程序员的算法趣题Q19: 朋友的朋友还是朋友吗？

摘要：基于以上讨论可得，本题求解流程如下所示代码及测试运行结果上一篇水果酥饼日下一篇异或杨辉三角形本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述六度空间理论非常有名。大概的意思是1个人只需要通过6个中间人就...

oogh 2021-09-10 10:51 评论0 收藏0
程序员的算法趣题Q43: 让玻璃杯水量减半

摘要：但是由于不能使用作为，所以将表示状态的列表转换为后再用作的。上一篇将牌洗为逆序下一篇糖果恶作剧本系列总目录参见程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 2.1 节点状态表示 2.2 邻节点搜索 2.3 路径历史记忆以及判断邻节点是否在...

chenjiang3 2021-09-02 15:21 评论0 收藏0
程序员的算法趣题Q39: 反复排序

摘要：中的统一的终点是全白状态。比如说，的第个数恰好是，它可以由根据题设规则重排而得。上一篇填充白色填充白色下一篇优雅的地址本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解目录 1. 问题描述 2. 解题分析 2.1 Naive Approach--正向全量搜索 ...

gitmilk 2021-09-26 09:55 评论0 收藏0