看不懂quro上关于android解锁种数的代码

Question

这个是链接 How many combinations does Android 9 point unlock have? min_seq_length = 4 def Middle(a, b): """Return the node between a and b if there is one, or None.""" if (a+b)%2 != 0: return None mid = (a+b)/2 if mid == 5: return mid if a%3 == b%3: return mid if (a-1)/3 == (b-1)/3: return mid return None def NextValid(base): """Generate valid moves j+1 given a sequence of moves 1..j.""" if len(base) >= 9: return if len(base) == 0: for i in xrange(1,10): yield i return for i in xrange(1,10): if not i in base: mid = Middle(i, base[-1]) if mid is None or mid in base: yield i def Sequences(base): """Generator for valid sequences of moves.""" if len(base) >= min_seq_length: yield list(base) for n in NextValid(base): for s in Sequences(base + [n]): yield s seqs_of_length = [0]*10 for seq in Sequences([]): # if len(seq) == 9: # print seq seqs_of_length[len(seq)] += 1 print 'Sequences by length:', seqs_of_length print 'Total number of sequences:', sum(seqs_of_length)

Answer 1

这段代码共有三个函数，连带main在内就是4个代码块，从下往上依次为：

1 main
for seq in Sequences([])：中Sequence([])是以一个点都没有的空状态作为初始状态传入Sequence中。Sequence会返回一个生成器，该生成器可以生成所有节点数大于min_sqe_length的连法。
下面一行则是判断当前遍历到的方法的步骤数，然后将对应步骤数的计数器加1.
最后两行分别输出每一种长度对应的连法种数，以及所有长度的总数。

2 Sequence函数
Sequence实际上是递归函数。base参数就是当前所对应的连法，下面的if语句会做一次判断，如果base的长度达于最小值则将该情况输出，否则略过，直接进入下一步。
下一步首先通过NextValid找到下一步可以连的点的集合，然后遍历该集合对于每一个点都将它与base合并后递归调用Sequence。实质上就是一个遍历树的过程。
需要注意的是Sequence中通过调用yield进行输出可能难以理解，可以等价的转化为list就容易理解了。每个Sequence函数实际上就是讲起调用的子函数所返回的所有list合并后并将自己的base加入，生成一个新的list返回上一级。

3 NextValid函数
该函数可以根据已经连过的点集合找到可以连的下一个点集。
首先如果base长度为9直接返回，因为9个点都连过了。
然后如果base长度为0则返回1-9所有的点。
最后对于其他情况，遍历1-9，找出所有i并返回，i不在base集合中且Middle(i, base[-1])不存在。换句话说就是i不曾被连过且i与之前最后一个点形成的连线中不存在未被连过的点。

4 Middle函数
作用为判断指定两点之间是否有第三点。如果存在第三点且第三点没有被不在之前经过的点之中，那么ab两点是无法直连的。这里用了多种判断，包括若第三点存在则ab之和必为偶数，若ab模3同余则ab在同一列等方法。