仅生成唯一排列

Question

我正在使用 Combinatorics 库中的 permutations 列表，其中包含许多重复值。我的问题是 permutations 正在创建 all 排列，导致溢出，即使 many 排列相同。

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 应该总是 return all 排列的论点，无论是否唯一，但是有没有办法生成只有独特的排列所以我不会运行内存不足？

Answer 1

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

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)) 的此操作不会以任何合理的大小终止。

Answer 2

包里有个multiset_permutationCombinatorics:

julia> for p in multiset_permutations([1,1,2,2],4) p|>println end
[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]

Answer 3

我运行也遇到过这个问题，并使用 IterTools 的 distinct:

using IterTools, Combinatorics

distinct(permutations([1, 1, 2, 2], 4))

仅生成唯一排列

Generating only unique permutations

permutation

combinatorics

julia