La iteración a través de cada ruta de acceso de un Trinomio de Árbol

Question

Estoy tratando de subir con un algoritmo para recorrer todas las rutas posibles de un trinomio de árbol y estoy teniendo dificultades viene con uno. Hay alguna literatura sobre este o tiene cualquier otra persona por algo similar?

Para ser específicos, estoy tratando de calcular el P&L de operaciones bursátiles desde el nodo 0 para cada posible ruta final.

EDIT: permítanme aclarar - para un 1 paso trinomio árbol hay tres caminos: 1 (arriba) 0 (medio) o -1 (abajo). La adición de otro paso hace que el árbol tiene 5 puntos finales y 9 rutas de acceso: 11 (arriba,arriba) 10 (arriba,a mediados de) 01 (mediados de, arriba) 1-1 (arriba,abajo) 00 (mid,mid) -11 (abajo,arriba) 0-1 (m,d) -10 (d,m) -1-1 (d,d)

Soy consciente de que el número total de caminos que terminan en un punto dado es dado por Pascal del tetraedro, pero no sé cómo venir para arriba con todas las rutas de acceso para un arbitrario (n-paso) del árbol. Así que tengo el 1,-1,1,-1,0 secuencia que en este caso sería de final en el medio de nodo de un 5 paso árbol.

Answer 1

Si he entendido correctamente, he aquí un ejemplo en Python. Cualquier otro lenguaje de programación debe ser capaz de hacer algo similar:

def search(path):
    if len(path) == 5:
        if sum(path) == 0:
            print path
    else:
        search(path+[1])
        search(path+[0])
        search(path+[-1])

Simplemente invocar con un array vacío:

>> search([])
[1, 1, 0, -1, -1]
[1, 1, -1, 0, -1]
[1, 1, -1, -1, 0]
[1, 0, 1, -1, -1]
[1, 0, 0, 0, -1]
[1, 0, 0, -1, 0]
[1, 0, -1, 1, -1]
[1, 0, -1, 0, 0]
[1, 0, -1, -1, 1]
[1, -1, 1, 0, -1]
[1, -1, 1, -1, 0]
[1, -1, 0, 1, -1]
[1, -1, 0, 0, 0]
[1, -1, 0, -1, 1]
[1, -1, -1, 1, 0]
[1, -1, -1, 0, 1]
[0, 1, 1, -1, -1]
[0, 1, 0, 0, -1]
[0, 1, 0, -1, 0]
[0, 1, -1, 1, -1]
[0, 1, -1, 0, 0]
[0, 1, -1, -1, 1]
[0, 0, 1, 0, -1]
[0, 0, 1, -1, 0]
[0, 0, 0, 1, -1]
[0, 0, 0, 0, 0]
[0, 0, 0, -1, 1]
[0, 0, -1, 1, 0]
[0, 0, -1, 0, 1]
[0, -1, 1, 1, -1]
[0, -1, 1, 0, 0]
[0, -1, 1, -1, 1]
[0, -1, 0, 1, 0]
[0, -1, 0, 0, 1]
[0, -1, -1, 1, 1]
[-1, 1, 1, 0, -1]
[-1, 1, 1, -1, 0]
[-1, 1, 0, 1, -1]
[-1, 1, 0, 0, 0]
[-1, 1, 0, -1, 1]
[-1, 1, -1, 1, 0]
[-1, 1, -1, 0, 1]
[-1, 0, 1, 1, -1]
[-1, 0, 1, 0, 0]
[-1, 0, 1, -1, 1]
[-1, 0, 0, 1, 0]
[-1, 0, 0, 0, 1]
[-1, 0, -1, 1, 1]
[-1, -1, 1, 1, 0]
[-1, -1, 1, 0, 1]
[-1, -1, 0, 1, 1]

Answer 2

Para convertir un índice de base 3 (en realidad a una matriz con la base de 3 dígitos, cada uno de seleccionar un movimiento arriba/mid/abajo) sólo se deben alternar un modulo-3 (resto) operador y división de enteros por 3. O se pide algo más?