2
$\begingroup$

Suppose that we begin at (0, 0) and are allowed to take two types of steps - steps one unit up and steps one unit to the right. For example, a legal path might be (0, 0) → (1, 0) → (2, 0) → (2, 1) → (3, 1).

Now, suppose that you are given a number k. Is there an efficient algorithm to list of all points (x, y) with exactly k paths to them? For example, given the number 6, we would list (1, 5), (5, 1) and (2, 2), since these points have exactly six paths to them.

Thanks!

  • 0
    This boils down to finding all $x,y$ such that the binomial coefficient $(x+y)$-choose-$x$ equals $k$. That question (or a close relative) has come up on this site two or three times in the last day or so. See http://math.stackexchange.com/questions/103506/what-is-the-maximum-point-for-which-number-of-way-to-reach-is-given and the links there to other questions.2012-01-30

2 Answers 2

3

We can use dynamic programming to find those paths. Note, that all points (X, 0) and (0, Y) have only one path to achieve them, because we must go only up or only right to came to this point. Also, if we know number of paths to (I-1, J) and (I, J-1) we can assume that value for (I, J) will be sum of this values - we can make last step to the right, or to the up.

for (int i = 0; i <= MAX; ++i) {     paths[i][0] = paths[0][i] = 1; } for (int i = 1; i <= MAX; ++i) {     for (int j = 1; j <= MAX; ++j) {         paths[i][j] = paths[i-1][j] + paths[i][j-1];     } } 

If you print out values in this table, you can find that this is Pascal's triangle, so you can try to find efficient algorithm to finding those numbers in this construction.

Note that you don't need all table paths[][], but only previous and current rows. Also, due to symmetry, you can count values only when I < J, so if (I, J) is accessible in k number of ways, same number of ways will stay for (J, I).

EDIT: new solution with optimized speed and memory consumption:

int MAX = 10000000; int[] pathPrev = new int[MAX + 1]; int[] pathCurr = new int[MAX + 1];  for (int i = 0; i <= MAX; ++i) {     pathCurr[i] = 1; }  for (int i = 1; i * i <= MAX; ++i) {     int[] temp = pathPrev;     pathPrev = pathCurr;     pathCurr = temp;     pathCurr[0] = 1;     for (int j = 1; pathCurr[j-1] < MAX; ++j) {         pathCurr[j] = pathCurr[j-1] + pathPrev[j];         if (pathCurr[j] == MAX && i <= j) {             System.out.println(i + " " + j);             if (i != j) {                 System.out.println(j + " " + i);             }         }     } } 
  • 0
    I've rewritten my solution for using symmetry and utilising less memory (only for two last rows), and it works little more than second at my Core 2 Duo. I'm using Java, so if you'll use C or C++ this can be even faster.2012-01-29
1

This sounds to me like a combinatorial problem.

Say you start in (x, y) and want to go to (x+3, y+3). If we represent all "up" movements by 'U' and all "right" movements by 'R', such a path could be UUURRR. The total number of possible paths would be all possible permutations of UUURRR, namely 6!/(3!3!) = 20.

An algorithm finding all these paths could be to put all 'U's and 'R's in a pool and select one from the pool. This will be your first move. Then find all permutations involving the rest of the pool. Finally swap your first choice (i.e. an 'U') for the opposite choice (this time an 'R') and do it again. Recursively you'll now have found all possible paths between the two points.

Updating the answer reflecting templatetypedef's comments below:

If you want the number of paths reachable within k number of steps, the solution is still feasible and similar. Perhaps even simpler. Choose a 'U' then calculate the number of paths using (k-1) steps from there to the destination. After this is complete, choose an 'R' and calculate the number of paths using (k-1) steps from there to the destination. These two numbers added together will be your answer. Use recursion on the (k-1) subpath-steps.

If you want the points with exactly n subpaths leading to them, it gets trickier. One way could be to go by binomial numbers. Find all i and j such as i!/((i-j)!j!)=n. This will take O(n) time since i+j<=n. Then you can use my proposition above for finding the number of paths reachable within k number of steps. OleGG's solution below might be cleaner though. I leave it to you to benchmark :)

  • 0
    @templatetypedef is completely correct; your algorithm is $O(n^2)$ and also doesn't work... -12016-12-31