30 行 Python 代码搞定 X 算法

这篇文章是在没有搭建这个Blog之前帮jobbole翻译的,现在只是复制回来自己做个存档,jobbole链接在这。 假如你对数独解法感兴趣,你可能听说过精确覆盖问题。给定全集 X 和 X 的子集的集合 Y ,存在一个 Y 的子集 Y*,使得 Y* 构成 X 的一种分割。 这儿有个Python写的例子。 X = {1, 2, 3, 4, 5, 6, 7} Y = { 'A': [1, 4, 7], 'B': [1, 4], 'C': [4, 5, 7], 'D': [3, 5, 6], 'E': [2, 3, 6, 7], 'F': [2, 7]} 这个例子的唯一解是['B', 'D', 'F']。 精确覆盖问题是NP完备(译注:指没有任何一个够快的方法可以在合理的时间内,意即多项式时间 找到答案)。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链,使用双向链表来表示该问题的矩阵。 然而,舞蹈链实现起来可能相当繁琐,并且不易写地正确。接下来就是展示Python奇迹的时刻了!有天我决定用Python来编写X 算法,并且我想出了一个有趣的舞蹈链变种。 算法 主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了 Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表,换句话说就是能从列中快速访问行元素。为实现这个目的,我们把X转换为字典。在上述的例子中,它应该写为 X = { 1: {'A', 'B'}, 2: {'E', 'F'}, 3: {'D', 'E'}, 4: {'A', 'B', 'C'}, 5: {'C', 'D'}, 6: {'D', 'E'}, 7: {'A', 'C', 'E', 'F'}} 眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上,我们需要能快速删除和添加行到每列,这就是为什么我们使用集合。另一方面,高德纳没有提到这点,实际上整个算法中所有行是保持不变的。...

July 22, 2014 · 2 min · HuangWei

百度面试题 - 搜索框的suggestion

题目内容 百度搜索框的suggestion,比如输入北京,搜索框下面会以北京为前缀,展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词。 如何设计使得空间和时间复杂度尽量低。 ...

September 23, 2012 · 2 min · HuangWei

Bloom Filter 原理与应用

这篇是从老blog里复制出来,用markdown格式更新了下,纯当练手。 介绍 Bloom Filter是一种简单的节省空间的随机化的数据结构,支持用户查询的集合。一般我们使用STL的std::set, stdext::hash_set,std::set是用红黑树实现的,stdext::hash_set是用桶式哈希表。上述两种数据结构,都会需要保存原始数据信息,当数据量较大时,内存就会是个问题。如果应用场景中允许出现一定几率的误判,且不需要逆向遍历集合中的数据时,Bloom Filter是很好的结构。 优点 查询操作十分高效。 节省空间。 易于扩展成并行。 集合计算方便。 代码实现方便。 有误判的概率,即存在False Position。 无法获取集合中的元素数据。 不支持删除操作。 缺点 有误判的概率,即存在False Position。 无法获取集合中的元素数据。 不支持删除操作。 ...

November 17, 2010 · 1 min · HuangWei

关于中国邮递员问题和欧拉图应用

中国邮递员问题 1962年有管梅谷先生提出中国邮递员问题(简称CPP)。一个邮递员从邮局出发,要走完他所管辖的每一条街道,可重复走一条街道,然后返回邮局。任何选择一条尽可能短的路线。 这个问题可以转化为:给定一个具有非负权的赋权图G, 用添加重复边的方法求G的一个Euler赋权母图G*,使得尽可能小。 求G*的Euler 环游。 人们也开始关注另一类似问题,旅行商问题(简称TSP)。TSP是点路优化问题,它是NPC的。而CPP是弧路优化问题,该问题有几种变形,与加权图奇点的最小完全匹配或网络流等价,有多项式算法。1 欧拉图 图G中经过每条边一次并且仅一次的回路称作欧拉回路。存在欧拉回路的图称为欧拉图。 无向图欧拉图判定 无向图G为欧拉图,当且仅当G为连通图且所有顶点的度为偶数。 有向图欧拉图判定 有向图G为欧拉图,当且仅当G的基图2连通,且所有顶点的入度等于出度。 欧拉回路性质 性质1 设C是欧拉图G中的一个简单回路,将C中的边从图G中删去得到一个新的图G’,则G’的每一个极大连通子图都有一条欧拉回路。 性质2 设C1、C2是图G的两个没有公共边,但有至少一个公共顶点的简单回路,我们可以将它们合并成一个新的简单回路C’。 欧拉回路算法 在图G中任意找一个回路C; 将图G中属于回路C的边删除; 在残留图的各极大连通子图中分别寻找欧拉回路; 将各极大连通子图的欧拉回路合并到C中得到图G的欧拉回路。 由于该算法执行过程中每条边最多访问两次,因此该算法的时间复杂度为O(|E|)。 如果使用递归形式,得注意|E|的问题。使用非递归形式防止栈溢出。 如果图 是有向图,我们仍然可以使用以上算法。 http://acm.hdu.edu.cn/showproblem.php?pid=1116 有向图欧拉图和半欧拉图判定 http://acm.pku.edu.cn/JudgeOnline/problem?id=2337 输出路径 中国邮递员问题① 一个邮递员从邮局出发,要走完他所管辖的每一条街道,可重复走一条街道,然后返回邮局。所有街道都是双向通行的,且每条街道都有一个长度值。任何选择一条尽可能短的路线。 分析 双向连通,即给定无向图G。 如果G不连通,则无解。 如果G是欧拉图,则显然欧拉回路就是最优路线。 如果G连通,但不是欧拉图,说明图中有奇点3。奇点都是成对出现的,证明从略。 对于最简单情况,即2个奇点,设(u,v)。我们可以在G中对(u,v)求最短路径R,构造出新图G’ = G ∪ R。此时G’就是欧拉图。...

September 8, 2007 · 3 min · HuangWei

关于数论中的互质数的最大不能组合数

最近看数论,转头重新思考了这题,参考了下论文和lrj的黑书,重新证明一遍,做个笔记。 例题:HDOJ 1792 A New Change Problem 题意:给定A和B,A和B互质,求最大不能组合数,和不能组合数的个数。 基础知识: $$\gcd(A, B) = 1 \Rightarrow \operatorname{lcm}(A, B) = AB$$ 剩余类,把所有整数划分成$m$个等价类,每个等价类由相互同余的整数组成 任何数分成$m$个剩余类,分别为 $mk,mk+1,mk+2,\cdots,mk+(m-1)$ 分别记为$\{0(\mod m)\},\{1(\mod m)\}$ 而$n$的倍数肯定分布在这$m$个剩余类中 因为$\gcd(m,n)=1$,所以每个剩余类中都有一些数是$n$的倍数,并且是平均分配它的旁证,可见HDOJ 1222 Wolf and Rabbit 设 $k_{min} = \min \{ k \mid nk \in \{i (\mod m)\} \},~ i \in [0, m)$ 则 $nk_{min}$ 是$\{i (mod m)\}$中$n$的最小倍数。特别的,$nm \in \{0 (\mod m)\}$ $nk_{min}$ 是个标志,它表明$\{i (\mod m)\}$中$nk_{min}$ 后面所有数,即$nk_{min} + jm$必定都能被组合出来 那也说明最大不能组合数必定小于$nk_{min}$ 我们开始寻找$\max\{ nk_{min} \}$ $\operatorname{lcm}(m, n) = mn$,所以很明显$(m-1)n$是最大的...

August 30, 2007 · 1 min · HuangWei

Number Theory 4.5 Relative Primality

当 $\gcd(m, n) = 1$时,我们称 $m$和$n$互素。 约定用 $m\bot n$来表示两者互素。 $$m / \gcd(m, n) ;\bot; n / \gcd(m, n)$$ 由 gcd和素数序列的关系我们可以得出 $$k \bot m \text{ and } k \bot n \Leftrightarrow k \bot mn$$ 书上看到一种很好玩的一种构造算法。 用来构造所有具有 $m\bot n$的非负分数 $m/n$集合,称为Stem-Brocot tree。 建树思想是: 从两个分数$(0/1, 1/0)$开始,重复以下操作,在两个邻接的分数 $m/n$和 $m'/n'$之间插入 $(m+m')/(n+n')$。 这颗树构造能保证相同分数不会出现两次,基于以下事实: 如果在任何构造阶段 $m/n$和 $m'/n'$是相继的分数,则有 $m’n - mn' = 1$ 证明: 开始时,$11 - 00 = 1$满足条件,计算出中间值 $(m+m')/(n+n')$后, $ \begin{array}{l} (m + m')n - m(n + n') = 1 ;\\ m'(n + n') - (m + m')n' = 1 ; \end{array} $...

August 24, 2007 · 1 min · HuangWei