一个非常特殊的找数字的问题

dancefly09

最近在群里看到了一个关于找数字的问题，思考几天了，百思不得其解，想不到任何合适的算法，很困扰，特此发到论坛上看看，大家出出主意。问题描述如下：

描述

数据源为100行6列的，共600个数字，每个数字，都在[1,100]范围内的正整数

从1-100个数字中挑出6个整数，同时满足以下条件

1、在100行中的N行内，这6个数字的任意一个，在每行中都不存在

2、在100行中的剩余的[100-n]行内，每一行至少出现了6个数字中的一个。

要求找出满足要求的6个数，如果有多组，则均列出来，如果结果过多，则列出前100组

找数字.zip (20.33 KB, 下载次数: 10)

2019-1-11 13:09 上传

点击文件名下载附件

lsdongjh

任意6个数都会符合要求的

lsdongjh

粗浅的逻辑思路：
1、列出100选6的各种组合，并用字典保存。（这一步运算近12亿条结果哦)
2、计算出各个数字出现的行号
3、根据组合字典，代入行号，再用字典去重，计算出 出现的行数，这时，字典就是 各种组合出现的行数。（运算的结果还是 12 亿条左右）
4、输入N ，读出字典值为 100-N 的各个KEY

yydyyydtc

穷举遍历，就完事了啊。你的600个数字是固定不变的，然后就按照条件挨个执行比较。
先按条件一，把符合的都列出来。并且再找一列记住改行的行数。
列出来的再按照条件2去挨个比较，由于是100-n的所有行，所以注意下n=1和n=100的时候的代码就可以了

dunxp

先遍历一遍获得600个格子内数字集合A（即总共出现了哪些数字）
然后取N行内的数字集合B
简单的计算一下集合C=A-B（即这N行内不包含的数字）
然后就是从集合C取6个数这种简单的排列组合问题了

dunxp

额，看错题了，没注意到要剩余100-N行每行都包括。

dunxp

补充一下，生成集合A时计算一下各数出现次数Ci
集合C直接判断每个数的次数Ci是否等于100-N，这样比循环要快。
但取哪N行还是要通过循环的方式

dancefly09

lsdongjh 发表于 2019-1-11 15:26
粗浅的逻辑思路：
1、列出100选6的各种组合，并用字典保存。（这一步运算近12亿条结果哦)
2、计算出各个 ...

第一步直接粗暴的遍历循环，估计不太现实。。要耗时非常非常久

DevilW

先用字典生成1-100的关键字，再把 n 行内出现过的关键字清除掉，剩下的关键字再组合、比对

dancefly09

DevilW 发表于 2019-1-11 17:21
先用字典生成1-100的关键字，再把 n 行内出现过的关键字清除掉，剩下的关键字再组合、比对

有个问题，这N行不是给定的，就是不知道到底是哪些行满足条件