Finding permutation of a set of 0 and 1, given index with O(N)

Question

I am trying to find the most efficient way to find permutation on a set of '0' and '1' given an index.

Ex: Given l = [0, 0, 1, 1]. All permutations in an ascending order is {0011, 0101, 0110, 1001, 1010, 1100}. These elements are indexed from 0 -> 5. Given index = 2, the result is 0110.

I found the algorithm here which inputs an integer multiset (e.g. l = [1, 2, 2]). His algorithm is efficient (O(N^2)). However, my multiset only consists of '0' and '1' and requires O(N) or less. N is the length of the list

Could you please kindly help me. Note that my real test is big (len(l) is 1024), so intertool library is not suitable. I am trying to speed up it as much as possible (e.g, using gmpy2...)

Based on 1, the following is my try but it is 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]

Thanks in advance.

Answer 1

Let's think:

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.