Skip to main content
Mathematics

Return to Answer

added 27 characters in body
Source Link
architectpianist
architectpianist
  • 1k
  • 8
  • 8

Suppose $(x_1,y_1)$ and $(x_2,y_2)$ represent the two points on a plane of size $m\times n$. You didn't specify restrictions on the paths, but I'll assume they must fall on gridlines.

Any path connecting these two points must have a net offset of $(x_2-x_1,y_2-y_1)$, so to find all the shortest paths you would just have to arrange $h=x_2-x_1$ horizontal and $v=y_2-y_1$ vertical steps starting from the first point. For example, with R = right and U = up, the move RRRRRUUURRUUUUUUURRR will take you from (0,0) to (10,10).

Now to find all possible paths (including those that overlap and cross earlier parts of the path), you could also insert backwards movements to create offsets like this: $(h+1)-1$, $(h+2)-2$,...,$(h+(m-h))-(m-h)$. Doing the same procedure for vertical motion, you can generate all possible paths by creating random sequences of left, right, up, and down motions in which the number of each motion is on that list.

In your example, you could not only move 10 right and 10 up, but also 11 right, 1 left, 12 up, and 2 down. For instance, RRRUUUUDLURRRDUUUUURRRRRUU is a valid path that would be generated by this algorithm.

Suppose $(x_1,y_1)$ and $(x_2,y_2)$ represent the two points on a plane of size $m\times n$. You didn't specify restrictions on the paths, but I'll assume they must fall on gridlines.

Any path connecting these two points must have a net offset of $(x_2-x_1,y_2-y_1)$, so to find all the shortest paths you would just have to arrange $h=x_2-x_1$ horizontal and $v=y_2-y_1$ vertical steps starting from the first point. For example, the move RRRRRUUURRUUUUUUURRR will take you from (0,0) to (10,10).

Now to find all possible paths (including those that overlap and cross earlier parts of the path), you could also insert backwards movements to create offsets like this: $(h+1)-1$, $(h+2)-2$,...,$(h+(m-h))-(m-h)$. Doing the same procedure for vertical motion, you can generate all possible paths by creating random sequences of left, right, up, and down motions in which the number of each motion is on that list.

In your example, you could not only move 10 right and 10 up, but also 11 right, 1 left, 12 up, and 2 down. For instance, RRRUUUUDLURRRDUUUUURRRRRUU is a valid path that would be generated by this algorithm.

Suppose $(x_1,y_1)$ and $(x_2,y_2)$ represent the two points on a plane of size $m\times n$. You didn't specify restrictions on the paths, but I'll assume they must fall on gridlines.

Any path connecting these two points must have a net offset of $(x_2-x_1,y_2-y_1)$, so to find all the shortest paths you would just have to arrange $h=x_2-x_1$ horizontal and $v=y_2-y_1$ vertical steps starting from the first point. For example, with R = right and U = up, the move RRRRRUUURRUUUUUUURRR will take you from (0,0) to (10,10).

Now to find all possible paths (including those that overlap and cross earlier parts of the path), you could also insert backwards movements to create offsets like this: $(h+1)-1$, $(h+2)-2$,...,$(h+(m-h))-(m-h)$. Doing the same procedure for vertical motion, you can generate all possible paths by creating random sequences of left, right, up, and down motions in which the number of each motion is on that list.

In your example, you could not only move 10 right and 10 up, but also 11 right, 1 left, 12 up, and 2 down. For instance, RRRUUUUDLURRRDUUUUURRRRRUU is a valid path that would be generated by this algorithm.

Source Link
architectpianist
architectpianist
  • 1k
  • 8
  • 8

Suppose $(x_1,y_1)$ and $(x_2,y_2)$ represent the two points on a plane of size $m\times n$. You didn't specify restrictions on the paths, but I'll assume they must fall on gridlines.

Any path connecting these two points must have a net offset of $(x_2-x_1,y_2-y_1)$, so to find all the shortest paths you would just have to arrange $h=x_2-x_1$ horizontal and $v=y_2-y_1$ vertical steps starting from the first point. For example, the move RRRRRUUURRUUUUUUURRR will take you from (0,0) to (10,10).

Now to find all possible paths (including those that overlap and cross earlier parts of the path), you could also insert backwards movements to create offsets like this: $(h+1)-1$, $(h+2)-2$,...,$(h+(m-h))-(m-h)$. Doing the same procedure for vertical motion, you can generate all possible paths by creating random sequences of left, right, up, and down motions in which the number of each motion is on that list.

In your example, you could not only move 10 right and 10 up, but also 11 right, 1 left, 12 up, and 2 down. For instance, RRRUUUUDLURRRDUUUUURRRRRUU is a valid path that would be generated by this algorithm.