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
    you may refer http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices2012-01-29
  • 0
    Do you want the *number* of paths, or all possible total paths?2012-01-29
  • 0
    I edited your question because by your example seems you looking for pair of points.2012-01-29
  • 0
    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...?2012-01-29
  • 2
    This shouldnt be allowed ! its Facebook Hacker Cup Q1) Checkpoint... and the contest in not over yet !2012-01-29
  • 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
    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?2012-01-29
  • 0
    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. http://en.wikipedia.org/wiki/Pascal_matrix2012-01-29
  • 0
    But if suppose the distinct path is given as 100000 or so.. then it would be difficult to go by this method2012-01-29
  • 0
    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.2012-01-29
  • 0
    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.2012-01-29
  • 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
    But here you don't know where you're trying to go... That's the point of the problem.2012-01-29
  • 0
    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.2012-01-29
  • 0
    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.2012-01-29
  • 0
    Expanded the solution based on your comments.2012-01-29
  • 0
    -1, this is not as easy as what you think, it's not just going from (x,y) to (x+k/2,y+k/2) So it's not just `i!/((i-j)!j!)=k` I don't know why you got upvote by such a simple assumptions.2012-01-29
  • 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).2012-01-29
  • 0
    This does not take time O(n) at all. There are O(n^2) pairs of values that you have to check.2012-01-29
  • 0
    Sigh... Please read my answer thoroughly before you answer. _Finding all i and j such as_ `i!/((i-j)!j!)=n` _will take O(n)_. It's a simple loop, from 0 to max(i, j).2012-01-30
  • 0
    @templatetypedef is completely correct; your algorithm is $O(n^2)$ and also doesn't work... -12016-12-31