生成唯一排列

Question

我正在使用Combinatorics库中的permutations函数处理一个含有多个重复值的列表。我的问题在于，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 应该始终返回所有排列，无论是否唯一，但有没有一种方法只生成唯一的排列，这样我就不会耗尽内存?

- Engineero

---

permutations returns an iterator, so there should be no problem with memory, unless you collect it. Do you really need to do that? Did you try unique(permutations( - DNF

unique(permutations(...))? - DNF

Answer 1

在组合数学包中有一个multiset_permutation函数：

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]

- Czylabson Asa

Answer 2

即使对于相对较小的向量（例如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

这是一个关于IT技术的快速书写，所以代码质量不是生产级别的——在样式和挤出最大性能方面，但我希望它能让您了解如何处理。

这给出了一种考虑重复项的唯一排列生成器。它速度合理：

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)) 的操作，在任何合理的大小下都不会停止。

- Bogumił Kamiński

---

我认为这确实可以解决问题，但我仍然在耗尽内存。我可能必须巧妙地解决问题，并避免排列组合。 - Engineero

你不需要使用 collect。我的解决方案可以在不实例化的情况下进行迭代。我只是在小范围内使用 collect 来展示它的正确性。 - Bogumił Kamiński

Answer 3

我也遇到了这个问题，使用 IterTools 库的 distinct 方法解决：

using IterTools, Combinatorics

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

- Jake Ireland