這個(gè)是鏈接 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 回答
慕少森
TA貢獻(xiàn)2019條經(jīng)驗(yàn) 獲得超9個(gè)贊
這段代碼共有三個(gè)函數(shù)，連帶main在內(nèi)就是4個(gè)代碼塊，從下往上依次為：
1 main
for seq in Sequences([])：中Sequence([])是以一個(gè)點(diǎn)都沒有的空狀態(tài)作為初始狀態(tài)傳入Sequence中。Sequence會(huì)返回一個(gè)生成器，該生成器可以生成所有節(jié)點(diǎn)數(shù)大于min_sqe_length的連法。
下面一行則是判斷當(dāng)前遍歷到的方法的步驟數(shù)，然后將對應(yīng)步驟數(shù)的計(jì)數(shù)器加1.
最后兩行分別輸出每一種長度對應(yīng)的連法種數(shù)，以及所有長度的總數(shù)。
2 Sequence函數(shù)
Sequence實(shí)際上是遞歸函數(shù)。base參數(shù)就是當(dāng)前所對應(yīng)的連法，下面的if語句會(huì)做一次判斷，如果base的長度達(dá)于最小值則將該情況輸出，否則略過，直接進(jìn)入下一步。
下一步首先通過NextValid找到下一步可以連的點(diǎn)的集合，然后遍歷該集合對于每一個(gè)點(diǎn)都將它與base合并后遞歸調(diào)用Sequence。實(shí)質(zhì)上就是一個(gè)遍歷樹的過程。
需要注意的是Sequence中通過調(diào)用yield進(jìn)行輸出可能難以理解，可以等價(jià)的轉(zhuǎn)化為list就容易理解了。每個(gè)Sequence函數(shù)實(shí)際上就是講起調(diào)用的子函數(shù)所返回的所有l(wèi)ist合并后并將自己的base加入，生成一個(gè)新的list返回上一級(jí)。
3 NextValid函數(shù)
該函數(shù)可以根據(jù)已經(jīng)連過的點(diǎn)集合找到可以連的下一個(gè)點(diǎn)集。
首先如果base長度為9直接返回，因?yàn)?個(gè)點(diǎn)都連過了。
然后如果base長度為0則返回1-9所有的點(diǎn)。
最后對于其他情況，遍歷1-9，找出所有i并返回，i不在base集合中且Middle(i, base[-1])不存在。換句話說就是i不曾被連過且i與之前最后一個(gè)點(diǎn)形成的連線中不存在未被連過的點(diǎn)。
4 Middle函數(shù)
作用為判斷指定兩點(diǎn)之間是否有第三點(diǎn)。如果存在第三點(diǎn)且第三點(diǎn)沒有被不在之前經(jīng)過的點(diǎn)之中，那么ab兩點(diǎn)是無法直連的。這里用了多種判斷，包括若第三點(diǎn)存在則ab之和必為偶數(shù)，若ab模3同余則ab在同一列等方法。
添加回答
舉報(bào)
0/150
提交
取消