朱莉娅计算排列的最佳方法 [英] Optimal way to compute permutations in julia

问题描述

考虑一个列表[1,1,1,...,1,0,0,...,0](零和一的任意列表).我们想要此数组中的所有可能置换，将有binomial(l,k)置换(l代表列表的长度，k代表列表中的个数).

Consider a list [1,1,1,...,1,0,0,...,0] (an arbitrary list of zeros and ones). We want the whole possible permutations in this array, there'll be binomial(l,k) permutations (l stands for the length of the list and k for the number of ones in the list).

现在，我已经测试了三种不同的算法来生成整个可能的排列，一种使用递归函数，一种使用递归函数 通过计算间隔号[1,...,1,0,0,...,0]进行排列 到[0,0,...0,1,1,...,1](因为这可以看作是二进制数的间隔)，并且使用字典顺序来计算排列.

Right now, I have tested three different algorithms to generate the whole possible permutations, one that uses a recurrent function, one that calculates the permutations via calculating the interval number [1,...,1,0,0,...,0] to [0,0,...0,1,1,...,1] (since this can be seen as a binary number interval), and one that calculates the permutations using lexicographic order.

到目前为止，当排列是 大约32.词典技术仍然很不错(仅需几毫秒即可完成).

So far, the first two approaches fail in performance when the permutations are approx. 32. The lexicographic technique works still pretty nice (only a few miliseconds to finish).

我的问题是，特别是对于朱莉娅，这是计算的最佳方法 如我先前所述的排列?我对组合语言不太了解，但我认为下降的基准将是根据总binomial(l,l/2)

My question is, specifically for julia, which is the best way to calculate permutations as I described earlier? I don't know too much in combinatorics, but I think a descent benchmark would be to generate all permutations from the total binomial(l,l/2)

推荐答案

正如您在注释中提到的那样，绝对希望使用l >> k的情况.在这种情况下，我们可以通过直到真正需要它们之前才处理长度为l的向量，而是处理这些索引的列表，从而显着提高性能.

As you have mentioned yourself in the comments, the case where l >> k is definitely desired. When this is the case, we can substantially improve performance by not handling vectors of length l until we really need them, and instead handle a list of indexes of the ones.

在 RAM模型中，以下算法可让您遍历所有空间O(k^2)和时间O(k^2 * binom(l,k))

In the RAM-model, the following algorithm will let you iterate over all the combinations in space O(k^2), and time O(k^2 * binom(l,k))

但是请注意，每次从索引组合生成位向量时，都会产生O(l)的开销，在该开销中，下界(对于所有组合)还将具有Omega(l*binom(l,k))的下限，并且内存使用量增加到Omega(l+k^2).

Note however, that every time you generate a bit-vector from an index combination, you incur an overhead of O(l), in which you will also have the lower-bound (for all combinations) of Omega(l*binom(l,k)), and the memory usage grows to Omega(l+k^2).

"""
Produces all `k`-combinations of integers in `1:l` with prefix `current`, in a
lexicographical order.

# Arguments
- `current`: The current combination
- `l`: The parent set size
- `k`: The target combination size
"""
function combination_producer(l, k, current)
    if k == length(current)
        produce(current)
    else
        j = (length(current) > 0) ? (last(current)+1) : 1
        for i=j:l
            combination_producer(l, k, [current, i])
        end
    end
end

"""
Produces all combinations of size `k` from `1:l` in a lexicographical order
"""
function combination_producer(l,k)
    combination_producer(l,k, [])
end

示例

然后您可以迭代所有组合，如下所示:

Example

You can then iterate over all the combinations as follows:

for c in @task(combination_producer(l, k))
    # do something with c
end

注意该算法的可恢复性:您可以随时停止迭代，然后再次继续:

Notice how this algorithm is resumable: You can stop the iteration whenever you want, and continue again:

iter = @task(combination_producer(5, 3))
for c in iter
    println(c)
    if c[1] == 2
        break
    end
end

println("took a short break")

for c in iter
    println(c)
end

这将产生以下输出:

[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
took a short break
[2,3,5]
[2,4,5]
[3,4,5]

如果要从c中获取位向量，则可以执行例如

If you want to get a bit-vector out of c then you can do e.g.

function combination_to_bitvector(l, c)
    result = zeros(l)
    result[c] = 1
    result
end

其中l是所需的位向量长度.

where l is the desired length of the bit-vector.

这篇关于朱莉娅计算排列的最佳方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！