找到一组0和1的置换,给定索引用O(N)

Question

我试图找到一种最有效的方法来找到一组'0'和'1'给定索引的排列.

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

我在这里找到了输入整数多重集的算法(例如l = [1,2,2]).他的算法是有效的(O(N ^ 2)).但是,我的multiset只包含'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

一些如何尝试解决这个问题的想法。

这是一个打印所有排列的简单程序：

import sys

oneBits = int(sys.argv[1])
totalLen = int(sys.argv[2])

low = 2**oneBits-1
end = 2**totalLen

print 'oneBits:',oneBits
print 'totalLen:',totalLen
print 'Range:',low,'-',end
print
format = '{0:0%db}' % totalLen
index = 0
print 'Index Pattern Value'
for i in range(low,end):
    val = format.format(i)
    if val.count('1') == oneBits:
        print '%5d %s %5d' % (index,val,i)
        index += 1

正如你所看到的，它纯粹适用于位运算（好吧，我在计算位时有点作弊1:-)

当您使用各种输入运行它时，您会看到输入具有模式：

oneBits: 2
totalLen: 5
Range: 3 - 32

Index Pattern Value
    0 00011     3
    1 00101     5
    2 00110     6  <-- pure shift
    3 01001     9
    4 01010    10
    5 01100    12  <-- pure shift
    6 10001    17
    7 10010    18
    8 10100    20
    9 11000    24  <-- pure shift

因此，我的第一个方法是找出发生这些纯粹转变的索引。距离仅取决于 0 和 1 位的数量。由于总和始终为 1024，这意味着您应该能够预先计算这些点并将结果存储在包含 1024 个条目的表中。这将使您接近您想去的地方。