在给定索引的情况下，我试图找到在一组“0”和“1”上找到排列的最有效方法。
例如：给定l=[0,0,1,1]。升序排列的所有排列都是{0011,0101,0110,1001,1010,1100}。这些元素的索引从0-
我在这里找到了输入整数多重集的算法（例如l=[1,2,2]）。他的算法是有效的（O（N^2））。然而，我的多集仅由'0'和'1'组成，并且需要O（N）或更少。N是列表的长度
你能帮帮我吗？请注意，我的真正测试很大（len（l）是1024），所以intertools库不合适。我正在努力尽可能加快速度（例如，使用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]
提前感谢。
让我们想想：
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.
给定N个0和M个1的排列，我们需要找到索引为K的排列
我们知道以0开头的排列数等于N-1 0和M1的排列数，我们称之为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的索引（从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组成的情况。计算阶乘可能需要一些时间（并在其他语言中导致溢出），但可以预先计算它们。
一些想法，你可以尝试解决这个问题。
这是一个打印所有排列的简单程序：
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个条目的表中。这将使您接近您想要的位置。
