algorithm - 在 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-model ，下面的算法将让你遍历空间 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 是所需的位向量长度。