algorithm - 将序列转换为 lex 顺序

Question

我有一个函数可以生成具有固定数量的 1（其余为 0）的二进制序列。我需要一个函数，它接受一个序列并按字典顺序返回该序列的位置。例如，10 个长度为 5 和 3 个 1 的序列是

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

我需要一个函数，例如0 1 1 0 1并返回3，因为它是列表中的第三个。

我能想到的唯一一件效率太低的事情是生成所有序列（简单），存储它们（占用太多空间），然后在列表中搜索给定序列（太慢），然后返回它的位置。有没有更快的方法来做到这一点？一些我看不到的简单技巧？

Answer 1

n我们称这组长度为k1 的序列binseq(n,k)。然后可以递归地解决这个问题，如下所示：

1. 基本情况：如果S长度为 1，则位于位置 1。
2. 如果S以 0 开头，则其位置与 中的tail(S)(S删除第一个元素)的位置相同binseq(n-1, k)。
3. 如果S以 1 开头，则其位置等于tail(S)in的位置binseq(n-1, k-1)加上 中的序列数binseq(n-1, k)。

在python代码中：

#!/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:])

或迭代版本，如 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