Enumerating paths from origin to a given point As is well known, there are $\binom{n+m}{n}$ paths from $(0,0)$ to $(n,m)$.
Is there an easy way to enumerate the lexicographically ordered paths?
IOW, how to map a given sequence of $n$ ones and $m$ zeros to a number from 1 to $\binom{n+m}{n}$ (and, v.v., such a number to such a sequence) without going through paths one-by-one (i.e., in $O(n+m)$ time).
PS. E.g., there are $6=\binom42$ paths from $(0,0)$ to $(2,2)$. If we denote a horizontal move as $0$ and a vertical one as $1$, here is the order of the paths:


*

*$0011$

*$0101$

*$0110$

*$1001$

*$1010$

*$1100$
Of course, lexicographical order is the same as the numeric order if we view the paths as binary representations of numbers.
PPS. Again, iteration over paths is not a solution here, but, for reference, here is how one might approach it in Python:
def sum_binary_digits(n):
    r = 0
    while n:
        r += n & 1
        n //= 2
    return r

def print_all_paths(n,m):
    path = 0
    tot = ncr(n+m,n)
    done = 0
    while done < tot:
        if sum_binary_digits(path) == m:
            print("{done:2d} {path:0{width}b} {path:{width}d}".format(
                done=done,path=path,width=n+m))
            done += 1
        path += 1

 A: There's a fairly easy way to do it.  I'll just do an example, which will, I think make the procedure clear.  Let $m=n=4$ and suppose we want to find the index of the string $s=00101101.$  How many strings precede $s$?  Certainly any string that starts with three $0$'s does.  That leaves one $0$ and four $1$'s, so there are $\binom{5}{1}=5$ such strings.  
Now we are left with strings that start with $001$.  There are the same number of such strings preceding $s$ as there are strings with two $0$'s and three $1$'s preceding $t=01101$.  Any such string starting with $00$ precedes $t$. There is only $1$ of those, and the problem is reduced to finding the number of strings with one $0$ and two $1$ preceding $101$.  There is $1$ such string starting with $0$, and the problem is reduced to finding the number of strings with no $0$'s and one $1$ preceding $1$. Clearly, there are none.
We have found that there are $5+1+1=7$ strings preceding $s$, so that $s$ is string number $8$.
EDIT
Here's a python script that implements this method.
from math import factorial

def choose(n,m):
    if m == 0:
        return 1
    return factorial(n)//(factorial(m)*factorial(n-m))

def predecessors(s):
    zeros = s.count('0')
    ones = s.count('1')
    if zeros == 0 or zeros == len(s):
        return 0
    n = s.index('1')
    if n == zeros:
        return 0
    return choose(len(s)-n-1,zeros-n-1)+ + predecessors(s[n+1:])

def test(m, n):
    from itertools import product
    P = list(''.join(p) for p in product('01', repeat = m+n) if p.count('1')==n)
    for idx, p in enumerate(P):
        assert predecessors(p) == idx
    print('Passed')

The predecessors function computes the number of predecessors of a given string $s$.  That is, it computes the number of binary strings with the same number of $0$'s and the same number of $1$'s as $s$, that precede $s$ in lexicographic order. To get the (one-based) index of $s$, you must add $1$.  
The test function is just for testing that predecessors works.  For example, test(5,3) generates a sorted list of all strings with $5$ zeros and $3$ ones, and checks that  predecessors correctly computes the position of each string in the list.     
A: In the following PARI program, the path function will compute the k-th path from (0, 0) to (m, n) and the inv function will compute the index back:
path(m,n,k) = {
    my (p=vector(m+n));    \\ p will contain m 0's and n 1's
    for (s=1, #p,
        if (n==0, m--; p[s]=0,    \\ horizontal move
            m==0, n--; p[s]=1,    \\ vertical move
            my (c=binomial(m+n-1, n));
            if (k<=c,
                m--; p[s]=0,      \\ horizontal move
                n--; p[s]=1; k-=c \\ vertical move
            )
        )
    );
    p
}
inv(m,n,p) = {
    my (k=1);
    for (s=1, #p,
        if (p[s]==0,
                m--,
                n--;
                if (m,
                    k+=binomial(m+n,n+1)
                );
        );
    );
    k
}

m=2; n=4
for (k=1, binomial(m+n,n), print (k " " p=path(m,n,k) " " inv(m,n,p)))

The algorithm works as follows: to find the k-th path from (0,0) to (m,n):


*

*if (m,n)=(0,0), you're done (by necessity, k=1),

*else if m=0, move vertically (by necessity, k=1),

*else if n=0, move horizontally (by necessity, k=1),

*else if k <= binomial(m+n-1,n) then move horizontally and find the k-th path from (0,0) to (m-1,n),

*else move vertically and find the (k-binomial(m+n-1,n))-th path from (0,0) to (m, n-1).

