一组0和1的发现置换，给定的索引与O（N） [英] Finding permutation of a set of 0 and 1, given index with O(N)

问题描述

我试图找到最有效的方式找到置换给定的指标一套0和1。

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

例：鉴于升= [0，0，1，1]。以升序的所有排列为{0011，0101，0110，1001，1010，1100}。这些元件是从0索引 - > 5.鉴于索引= 2，结果是0110

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.

我发现算法<一href="http://stackoverflow.com/questions/24506460/algorithm-for-finding-multiset-permutation-given-lexicographic-index">here其输入的整数多集（例如升= [1，2,2]）。他的方法是有效的（O（N ^ 2））。但是，我多集仅由0和1的，需要O（N）或更小。 N是该列表的长度

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

你能不能请您帮我。请注意，我真正的考验是很大的（LEN（L）为1024），因此互动工具库是不适合的。我想，以加快其尽可能多地（例如，使用gmpy2 ...）

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...)

href="http://stackoverflow.com/questions/24506460/algorithm-for-finding-multiset-permutation-given-lexicographic-index">1,下面是我的尝试，但它是O（N ^ 2）

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.

推荐答案

给定N个0和M 1组成的排列，我们需要找到与指标K排列

Given a permutations of N 0s and M 1s, we need to find the permutation with index K

我们知道，从0开始排列的数量等于N-1个0和M 1秒排列的数目，我们称之为K0

We know that the number of permutations starting with 0 is equal to the number of permutations of N-1 0s and M 1s, let's call it 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的正确数量

Fix the first bit and start again with K = K - K0 and the correct number of 0s and 1s.

本算法运行在O（n），其中n是位数（而不是列表的长度）

This algorithm runs in O(n) where n is the number of bits (and not the length of the list).

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

In order to simplify the calculations, we assume a 1 based index (starting at 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的情况。另外计算阶乘可能需要一段时间（并导致溢在其他语言），但它可能precompute他们。

Implementing this algorithm can be tricky, make sure to handle correctly the case where the whole list is composed of only 0s or 1s. Also computing the factorials might take sometime (and cause overflow in other languages), but it's possible to precompute them.

这篇关于一组0和1的发现置换，给定的索引与O（N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！