计算锯齿形序列

Question

锯齿形序列是一个序列，其中每个元素都小于或大于其相邻元素：1 3 2和2 1 2是锯齿形，1 2 3和1 2 2不是。

用两个给定 n 的数字，k 找出可以从数字 1 生成多少个大小为 n 的序列。

示例：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:])

Answer 1

整个序列中的顺序是用前两个元素的顺序给出的。有两种类型的排序：上-下-上-...和上下-...两种排序的序列数量相同，因为一个排序的序列可以通过将每个数字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))

Answer 2

如果你通过递归调用 Zig（小于最后一个数字的值）和 Zag（大于最后一个数字的值）迭代各种可能性来生成序列，它会变得更好一些，你可以通过将解决的子问题存储在静态表中来使其变得更好（计算方面，而不是内存方面）。