Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

migrated from stackoverflow.com Jan 30 '12 at 21:27

This question came from our site for professional and enthusiast programmers.

    
you may refer stackoverflow.com/questions/58306/… –  qiao Jan 29 '12 at 5:56
    
Do you want the number of paths, or all possible total paths? –  templatetypedef Jan 29 '12 at 6:03
    
I edited your question because by your example seems you looking for pair of points. –  Saeed Jan 29 '12 at 10:26
    
If you start at (0,0), I get that you have 15 possible paths to (4,2), and 7 possible paths to (6,1) or have I misunderstood the question...? –  Pedery Jan 29 '12 at 10:28
2  
This shouldnt be allowed ! its Facebook Hacker Cup Q1) Checkpoint... and the contest in not over yet ! –  Pheonix Jan 29 '12 at 13:42

2 Answers 2

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);
            }
        }
    }
}
share|improve this answer
    
What value of MAX are you using here? How does it pertain to the choice of the value of k? Also, is there a method that's more efficient than this O(k^2) approach? –  templatetypedef Jan 29 '12 at 7:18
    
But this method looks promising.. If there is any other method with less complexity it would be better. But if you make a Pascal Matrix out of it then the coordinates are just the (row,column) number of the matrix. en.wikipedia.org/wiki/Pascal_matrix –  Android Decoded Jan 29 '12 at 7:25
    
But if suppose the distinct path is given as 100000 or so.. then it would be difficult to go by this method –  Android Decoded Jan 29 '12 at 7:29
    
Yes, MAX can't exceed k (cause any cells that is up-righter that specific cell have more variants to be achieved). Complexity is actually O(K^1.5), cause every next line we can build not till j = k, but we can stop if we got value more than k (in this case values right to those cell will be bigger), so we'll stop at row ceil(sqrt(k)) due to symmetry. –  OleGG Jan 29 '12 at 7:47
    
So, complexity O(k^1.5) will be still good until one million. We have good constant in O notation - cause we only sum up some integers. –  OleGG Jan 29 '12 at 7:52

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 :)

share|improve this answer
    
But here you don't know where you're trying to go... That's the point of the problem. –  templatetypedef Jan 29 '12 at 8:57
    
Sure you do! Between (x,y) and (x+3,y+3) there are exactly 3 'U's and 3 'R's. Any (new) combination of R, R, R, U, U and U will give a new path. –  Pedery Jan 29 '12 at 9:23
    
But in the OP's question you don't know the destination; you're trying to find all feasible destinations reachable in exactly some number of steps. –  templatetypedef Jan 29 '12 at 9:43
    
Expanded the solution based on your comments. –  Pedery Jan 29 '12 at 10:55
1  
Did you read my entire answer? If there are R right moves and U up moves between two points, then all paths leading between them will number C(R+U, R) (using binomial notation). Thus one will need to iterate over i and j to find all of them that result in i!/((i-j)!j!)=n. From there one can use my proposition in the second last paragraph to calculate the actual paths, given that you now know the steps that can take you there (but not the order). –  Pedery Jan 29 '12 at 13:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.