在给定索引的情况下以O(N)找到0和1的排列

Question

我正在寻找一种高效的方法，根据给定的索引找到一组'0'和'1'的排列。

举个例子：给定 l = [0, 0, 1, 1]。所有的排列按升序排列是 {0011, 0101, 0110, 1001, 1010, 1100}。这些元素的索引从 0 到 5。假设给定索引是 2，那么结果就是 0110。

我在这里找到了一个算法，它可以处理整数多重集合（比如 l = [1, 2, 2]）。这个算法效率还不错（O(N^2)），但是我的多重集合只包含'0'和'1'，我希望能达到 O(N) 或更低的效率。N 是列表的长度。

能否请你帮我一下？请注意，我的实际测试数据很大（len(l) 是 1024），所以使用现成的库不太合适。我想尽可能加快速度（比如，使用 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

根据Samy Arous的想法，我对他的算法做了一些修改：

if K >= K0 => The permutation starts with 1, K = K - K0
if K < K0  => The permutation starts with 0, K remains the same

下面是我的代码：

import gmpy2

def find_permutation (lst, K, numberbit1, numberbit0):
    l = lst
    N = numberbit0
    M = numberbit1

    if N == len(l):
        return '1' * N
    if M == len(l):
        return '1' * M

    result = ''    
    for i in range (0, len(lst)-1):
        K0 = gmpy2.comb(len(l)-1, M)
        if (K < K0):
            result += '0'
            l.remove ('0')
        else:
            result += '1'
            l.remove ('1')
            M -=1
            K = K - K0
    result += l[0]
    return result

lst = ['0','1','1', '1']
K = 1
numberbit1 = 3
numberbit0 = 1
print find_permutation (lst, K, numberbit1, numberbit0)
        --> result = '1011'

谢谢你。虽然这个算法的复杂度是O(n)乘以gmpy2.comb的复杂度，但比我问题中的算法要好。

Answer 2

这里有一些想法，可以帮助你解决这个问题。

下面是一个简单的程序，用来打印所有的排列组合：

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个条目的表格里。这样你就能更接近你想要的位置。

Answer 3

给定N个0和M个1的排列，我们需要找到第K个排列。

我们知道，以0开头的排列数量等于剩下的N-1个0和M个1的排列数量，我们把这个数量叫做K0。

if K > K0 =>  The permutation starts with 1, K remains the same
if k <= K0 => The permutation starts with 0, remove K0 from K

固定第一个数字，然后重新开始，K的值变成K - K0，同时更新0和1的数量。

这个算法的运行时间是O(n)，这里的n是指位数，而不是列表的长度。

为了简化计算，我们假设索引是从1开始的。

举个例子：

n = xxxx
l = [0, 0, 1, 1]
K = 2 => 3
Number of permutations starting with 0: K0 = 3! / (2! * 1!) = 3
K <= K0 => first bit is a 0

n = 0xxx
l = [0, 1, 1]
K = K = 3
Number of permutations starting with 0: K0 = 2! / (2! * 0!) = 1
K > K0 => first bit is a 1

n = 01xx
l = [0, 1]
K = K - K0 = 2
Number of permutations starting with 0: K0 = 1! / (1! * 0!) = 1
K > K0 => first bit is a 1

n = 011x
l = [0]
K = K - K0 = 1
Number of permutations starting with 0: K0 = 1! / (0! * 0!) = 1
K <= K0 => first bit is a 0

n = 0110 Which is verified in your example.

实现这个算法可能会有点复杂，要确保正确处理整个列表只有0或只有1的情况。此外，计算阶乘可能需要一些时间（在其他语言中可能会导致溢出），但可以提前计算好。

Answer 4

让我们来想一想：

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.