converting sequences to lex order

Question

I have a function that generates binary sequences with a fixed number of 1's (the rest are 0's). I need a function that takes a sequences and returns the position of that sequence in lexicographic order. For example, the 10 sequences of length 5 with 3 1's are

0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0

I need a function that takes, for example 0 1 1 0 1 and returns 3 since it's the third in the list.

The only thing I can think of, which is way too inefficient, is to generate all of the sequences (easy), store them (takes too much space), then search for the given sequence in the list (too slow), and return its position. Is there a faster way to do this? Some easy trick that I don't see?

Answer 1

We call the set of sequences of length n with k 1's binseq(n,k). This problem can then be solved recursively, as follows:

1. Base case: If S has length 1, it's in position 1.
2. If S starts with a 0, its position is the same as the position of tail(S) (S with the first element removed) in binseq(n-1, k).
3. If S starts with a 1, its position is equal to the position of tail(S) in binseq(n-1, k-1) plus the number of sequences in binseq(n-1, k).

In python code:

#!/usr/bin/env python

def binom(n, k):
    result = 1
    for i in range(1, k+1):
        result = result * (n-i+1) / i
    return result

def lexpos(seq):
    if len(seq) == 1:
        return 1
    elif seq[0] == 0:
        return lexpos(seq[1:])
    else:
        return binom(len(seq)-1, seq.count(1)) + lexpos(seq[1:])

Or the iterative version, as suggested by Abhishek Bansal:

def lexpos_iter(seq):
    pos = 1
    for i in xrange(len(seq)):
        if seq[i] == 1:
            pos += binom(len(seq)-i-1, seq[i:].count(1))
    return pos