Algorithm for finding path combinations?

Question

Imagine you have a dancing robot in n-dimensional euclidean space starting at origin P_0 = (0,0,...,0).

The robot can make m types of dance moves D_1, D_2, ..., D_m

D_i is an n-vector of integers (D_i_1, D_i_2, ..., D_i_n)

If the robot makes dance move i than its position changes by D_i:

P_{t+1} = P_t + D_i

The robot can make any of the dance moves as many times as he wants and in any order.

Let a k-dance be defined as a sequence of k dance moves.

Clearly there are m^k possible k-dances.

We are interested to know the set of possible end positions of a k-dance, and for each end position, how many k-dances end at that location.

One way to do this is as follows:

P0 = (0, 0, ..., 0);

S[0][P0] = 1

for I in 1 to k
    for J in 1 to m
        for P in S[I-1]
            S[I][P + D_J] += S[I][P]

Now S[k][Q] will tell you how many k-dances end at position Q

Assume that n, m, |D_i| are small (less than 5) and k is less than 40.

Is there a faster way? Can we calculate S[k][Q] "directly" somehow with some sort of linear algebra related trick? or some other approach?

Answer 1

You could create an adjacency matrix that would contain dance-move transitions in your space (the part of it that's reachable in k moves, otherwise it would be infinite). Then, the P_0 row of n-th power of this matrix contains the S[k] values.

The matrix in question quickly gets enormous, something like (k*(max(D_i_j)-min(D_i_j)))^n (every dimension can be halved if Q is close to origin), but that's true for your S matrix as well