counting zigzag sequences

Question

Zigzag sequence is a sequence where every element is less or more than it's neighbours: 1 3 2 and 2 1 2 are zigzags, 1 2 3 and 1 2 2 are not.

With two numbers given n, k find out how many sequences of size n can be generated from numbers 1..k

Example: n = 3 k = 3 Answer: 10

121, 212, 131, 313, 232, 323, 132, 231, 312, 213 (no need to generate, just for clarity)

I came to this solution. Please, tell me if it can be done better.

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:])

possible duplicate: http://stackoverflow.com/questions/6914969/dynamic-programming-find-longest-subsequence-that-is-zig-zag — Aman Deep Gautam, Oct 17 '12 at 22:21

Sconibulus · Answer 1 · 2012-10-08T16:54:55.760

0

If you generate the sequence through recursive calls to a Zig (values less than last number) and Zag (values greater than last number) iterating through the possibilities, it gets a little better, and you can make it better yet (calculation-wise, not memory-wise) by storing solved subproblems in a static table.

edited Oct 08 '12 at 16:54

answered Oct 08 '12 at 16:38

Sconibulus

732
9
21

Ante · Accepted Answer · 2012-10-08T19:35:31.420

Orders in whole sequence is given with an ordering of first two elements. There are two types of ordering: up-down-up-... and down-up-down-... There are same number of sequences of both ordering, since sequence of one ordering can be transformed in other order by exchanging each number x with k+1-x.

Let U_k(n) be number of sequences with first up order of length n. Let U_k(n, f) be number of sequences with first up order of length n and with first number f. Similar define D_k(n) and D_k(n, f).

Then number of sequences of length n (for n>1) is:

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

Same argument gives:

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

Edit:

Slightly simpler implementation. M(n,k) returns n'th row (from back), and C(n,k) counts number of sequences.

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))

counting zigzag sequences

2 Answers2