在 julia 中计算排列的最佳方法

Question

考虑一个列表[1,1,1,...,1,0,0,...,0]（零和一的任意列表）。我们想要这个数组中所有可能的排列，会有binomial(l,k)排列（l代表列表的长度和列表k中的数量）。

现在，我已经测试了三种不同的算法来生成整个可能的排列，一种使用循环函数，一种通过计算区间数[1,...,1,0,0,...,0] 来计算排列[0,0,...0,1,1,...,1]（因为这可以看作是一个二进制数区间），还有一种使用字典顺序计算排列。

到目前为止，当排列大约为 时，前两种方法的性能失败。32. 词典编排技术仍然很好（只需几毫秒即可完成）。

我的问题是，特别是对于 julia，哪种是我之前描述的计算排列的最佳方法？我对组合学不太了解，但我认为下降基准是从总数中生成所有排列binomial(l,l/2)

Answer 1

正如您在评论中提到的那样，l >> k绝对需要这种情况。在这种情况下，我们可以通过不处理长度向量来显着提高性能l在真正需要之前的索引列表。

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

但是请注意，每次从索引组合生成位向量时，都会产生 的开销O(l)，其中您还将拥有 的下限（对于所有组合）Omega(l*binom(l,k))，并且内存使用量增加到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

例子

然后，您可以按如下方式迭代所有组合：

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

请注意此算法是如何可恢复的：您可以随时停止迭代，然后再次继续：

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那么你可以做例如

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

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