看不懂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在同一列等方法。