python - 查找一组 0 和 1 的排列，给定索引为 O(N)

Question

我正在尝试找到最有效的方法来查找给定索引的一组“0”和“1”的排列。

例如:给定 l = [0, 0, 1, 1]。所有升序排列都是{0011, 0101, 0110, 1001, 1010, 1100}。这些元素的索引从 0 -> 5。给定索引 = 2，结果为 0110。

我找到了算法 here输入整数多重集(例如 l = [1, 2, 2])。他的算法是高效的 (O(N^2))。但是，我的多重集仅包含“0”和“1”并且需要 O(N) 或更少。 N是列表的长度

你能帮帮我吗？请注意，我的真实测试很大(len(l) 是 1024)，因此 intertool 库不适合。我正在尝试尽可能加快它的速度(例如，使用 gmpy2...)

基于 1 ，以下是我的尝试，但它是 O(N^2)

from collections import Counter
from math import factorial
import gmpy2   

def permutation(l, index):
    if not index:
        return l

    counter = Counter(l)
    total_count = gmpy2.comb(len(l), counter['1'])
    acc = 0
    for i, v in enumerate(l):
        if i > 0 and v == l[i-1]:
            continue
        count = total_count * counter[v] / len(l)

        if acc + count > index:
            return [l[i]] + permutation(l[:i] + l[i + 1:], index - acc)
        acc += count

    raise ValueError("Not enough permutations")

l = ['0', '0', '1', '1']
index = 2
print (l, index)
   --> result = [0, 1, 1, 0]

提前致谢。

Answer 1

让我们想想:

For n bits with k ones there are n choose k anagrams.

For each position, p, that the i`th left-most set-bit can occupy there are 
p choose (k-i) anagrams, for example:

n = 4, k = 2, i = 1 (left-most set-bit), position 1 => 001x => 1 choose 1 = 1
n = 4, k = 2, i = 1 (left-most set-bit), position 2 => 01xx => 2 choose 1 = 2

Given index 3 (non zero-based), we calculate the position of the 
left-most set-bit:

position 1, 1 choose (2-1) = 1 anagram, index 1
position 2, 2 choose (2-1) = 2 anagrams, index 2-3

We now know the left-most set-bit must be on position 2 and we know there 
are 2 anagrams possible. 

We look at the next set-bit (i = 2):
position 0, 0 choose (2-2) = 1 anagram, index 2
position 1, 1 choose (2-2) = 1 anagram, index 3

Therefore the second set-bit is in position 1 => 0110

I think this might be O(n*k) - I hope someone can understand/explain the
complexity better and perhaps improve/optimize this algorithm idea.