計數Z字形序列

鋸齒序列是序列，其中每一個元素是比它的鄰居更少或更多：1 3 2和2 1 2是曲折，1 2 3和1 2 2不是。計數Z字形序列

隨着給定的n兩個數，K找出如何大小爲n的許多序列可以從數字1..k

實施例來生成：N = 3，K = 3的答案：10

121，212 ，131,313,232,323,132,231,312,213（爲了清楚起見，不需要生成）

我來到這個解決方案。請告訴我是否可以做得更好。

import sys 

ZAG = {} 
ZIG = {} 

def zag(n, i): 
    result = 0 

    for j in xrange(1, i):  
     if (n - 1, j) not in ZIG: 
      ZIG[(n - 1, j)] = zig(n - 1, j) 
     result += ZIG[(n - 1, j)] 

    return result  

def zig(n, i): 
    result = 0 

    for j in xrange(i + 1, MAX_NUMBER + 1): 
     if (n - 1, j) not in ZAG: 
      ZAG[(n - 1, j)] = zag(n - 1, j) 
     result += ZAG[(n - 1, j)] 

    return result 

def count(n): 
    if n == 1: 
     return MAX_NUMBER 

    result = 0 

    for i in xrange(1, MAX_NUMBER + 1): 
     ZIG[(1, i)] = 1 
     ZAG[(1, i)] = 1 

    for i in xrange(1, MAX_NUMBER + 1): 
     result += 2*zag(n, i) 

    return result 

def main(argv): 
    global MAX_NUMBER 
    MAX_NUMBER = int(argv[1]) 
    print count(int(argv[0])) 

if __name__ == "__main__": 
    main(sys.argv[1:])

來源

2012-10-08 Sam Davydov

可能重複：http://stackoverflow.com/questions/6914969/dynamic-programming-find-longest-subsequence-that-is-zig-zag –

整個序列中的順序是以前兩個元素的順序給出的。有兩種類型的排序：上 - 下 - 上 - 和下 - 下 - ...。兩個排序的序列數目相同，因爲一個排序的順序可以通過交換每個順序號碼x與k+1-x。

讓U_k(n)爲具有首位長度爲n的序列的序列數目。令U_k(n, f)爲具有首位長度爲n且首位數爲f的序列數目。類似地定義爲D_k(n)和D_k(n, f)。

然後號碼長度n（爲n>1）的序列是：

U_k(n) + D_k(n) = 2*U_k(n) = 2*(sum U_k(n, f) for f in 1 ... k).

相同的參數，得出：

U_k(n, f) = sum D_k(n-1, s) for s = f+1 ... k 
      = sum U_k(n-1, s) for s = 1 ... k-f 
U_k(1, f) = 1

編輯：

稍微簡單的實現。 M(n,k)返回第n行（從後面），並且C(n,k)計數序列的數量。

def M(n, k): 
    if n == 1: return [1]*k 
    m = M(n-1, k) 
    return [sum(m[:i]) for i in xrange(k)][::-1] 

def C(n, k): 
    if n < 1: return 0 
    if n == 1: return k 
    return 2*sum(M(n,k))

來源

2012-10-08 17:49:55 Ante

如果產生通過遞歸調用鋸齒序列（值小於最後一位數字）和字形（比去年數量值較大），通過的可能性迭代，它變得更好一點，你可以把它通過將解決的子問題存儲在靜態表中，更好（計算方面，而不是內存方面）。

來源

2012-10-08 16:38:30 Sconibulus

計數Z字形序列

回答

相關問題