描述:
这个是链接 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)
解决方案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在同一列等方法。