在 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中，下面的算法会让你遍历spaceO(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 是所需的位向量长度。

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

Optimal way to compute permutations in julia

algorithm

combinatorics

julia

算法

例子