时间戳

首页 > 解决方案 > 仅生成唯一排列

julia - 仅生成唯一排列

问题描述

我正在permutations从Combinatorics库中使用具有许多重复值的列表。我的问题是permutations创建所有排列，导致溢出，即使许多排列是相同的。

julia> collect(permutations([1, 1, 2, 2], 4))
24-element Array{Array{Int64,1},1}:
 [1, 1, 2, 2]
 [1, 1, 2, 2]
 [1, 2, 1, 2]
 [1, 2, 2, 1]
 [1, 2, 1, 2]
 [1, 2, 2, 1]
 [1, 1, 2, 2]
 [1, 1, 2, 2]
 [1, 2, 1, 2]
 [1, 2, 2, 1]
 [1, 2, 1, 2]
 [1, 2, 2, 1]
 [2, 1, 1, 2]
 [2, 1, 2, 1]
 [2, 1, 1, 2]
 [2, 1, 2, 1]
 [2, 2, 1, 1]
 [2, 2, 1, 1]
 [2, 1, 1, 2]
 [2, 1, 2, 1]
 [2, 1, 1, 2]
 [2, 1, 2, 1]
 [2, 2, 1, 1]
 [2, 2, 1, 1]

很多相同的值。我真正想要的只是唯一的排列，而不需要首先生成所有排列：

julia> unique(collect(permutations([1, 1, 2, 2], 4)))
6-element Array{Array{Int64,1},1}:
 [1, 1, 2, 2]
 [1, 2, 1, 2]
 [1, 2, 2, 1]
 [2, 1, 1, 2]
 [2, 1, 2, 1]
 [2, 2, 1, 1]

我可以看到permutations应该始终返回所有排列的论点，无论是否唯一，但是有没有办法只生成唯一的排列，这样我就不会耗尽内存？

标签： juliapermutationcombinatorics

解决方案

unique即使对于尺寸相对较小的向量（例如，我认为 14 已经有问题），通过也可能令人望而却步。在这种情况下，您可以考虑这样的事情：

using Combinatorics, StatsBase

function trans(x, v::Dict{T, Int}, l) where T
    z = collect(1:l)
    idxs = Vector{Int}[]
    for k in x
        push!(idxs, z[k])
        deleteat!(z, k)
    end
    res = Vector{T}(undef, l)
    for (j, k) in enumerate(keys(v))
        for i in idxs[j]
            res[i] = k
        end
    end
    res
end

function myperms(x)
    v = countmap(x)
    s = Int[length(x)]
    for (k,y) in v
        l = s[end]-y
        l > 0 && push!(s, l)
    end
    iter = Iterators.product((combinations(1:s[i], vv) for (i, vv) in enumerate(values(v)))...)
    (trans(z, v, length(x)) for z in iter)
end

（这是一篇快速的文章，所以代码质量不是生产级的——就风格和最大限度地发挥性能而言，但我希望它能让您了解如何实现这一点）

这为您提供了一个考虑重复项的唯一排列生成器。它相当快：

julia> x = [fill(1, 7); fill(2, 7)]
14-element Array{Int64,1}:
 1
 1
 1
 1
 1
 1
 1
 2
 2
 2
 2
 2
 2
 2

julia> @time length(collect(myperms(x)))
  0.002902 seconds (48.08 k allocations: 4.166 MiB)
3432

虽然此操作unique(permutations(x))不会以任何合理的大小终止。

推荐阅读