def NextLeaf(a, L, k):
    # generates all L^k permutations
    for i in reversed(xrange(L)):
        if (a[i] < k):
            a[i] += 1
            break
        else:
            a[i] = 1
    return a


def NextVertex(a, i, L, k):
    # generates all nodes in a
    # search tree with L^k leafs
    if (i < L):
        a[i] = 1
        return (a, i+1)
    else:
        for j in reversed(xrange(L)):
            if (a[j] < k):
                a[j] += 1
                return (a, j+1)
            a[j] = 0
    return (a, 0)


def Bypass(a, i, L, k):
    # ignore children of
    # an interior node
    for j in reversed(xrange(i)):
        if (a[j] < k):
            a[j] += 1
            return (a, j+1)
        a[j] = 0
    return (a, 0)


if __name__ == "__main__":
    # Testing code
    print "All leafs:"
    s = [1,1,1]
    for i in xrange(9):
        print s
        s = NextLeaf(s,3,2)

    print "\nAll nodes:"
    s = [0,0,0]
    level = 0
    for i in xrange(16):
        print s, level
        s, level = NextVertex(s,level,3,2)

    print "\nPrune Interior:"
    s = [0,0,0]
    level = 0
    for i in xrange(12):
        print s, level
        if ((level == 2) and (s[0] != s[1])):
            s, level = Bypass(s,level,3,2)
        else:
            s, level = NextVertex(s,level,3,2)

    print "\nPrune Exterior:"
    s = [0,0,0]
    level = 0
    for i in xrange(12):
        print s, level
        if ((level == 2) and (s[0] == s[1])):
            s, level = Bypass(s,level,3,2)
        else:
            s, level = NextVertex(s,level,3,2)

    raw_input("Press [Enter] to quit")