Julia：用重复项生成集合中的所有非重复排列

Question

比方说，我有一个向量 x = [0, 0, 1, 1] 我想生成所有不同的排列。但是，Julia 中当前的排列函数无法识别向量中是否存在重复项。因此在这种情况下，它将输出完全相同的排列三次（这一次，一次交换两个零，一次交换一个）。

有人知道解决方法吗？因为在更大的系统中我最终会遇到越界错误...

非常感谢！ :)

Answer 1

permutations returns 一个迭代器，因此运行它到 unique 在内存使用方面可能非常有效。

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

Answer 2

我找到了 this 我改编的答案。它需要一个排序的向量（或者至少重复的值应该在列表中）。


julia> function unique_permutations(x::T, prefix=T()) where T
           if length(x) == 1
               return [[prefix; x]]
           else
               t = T[]
               for i in eachindex(x)
                   if i > firstindex(x) && x[i] == x[i-1]
                       continue
                   end
                   append!(t, unique_permutations([x[begin:i-1];x[i+1:end]], [prefix; x[i]]))
               end
               return t
           end
       end

julia> @btime unique_permutations([0,0,0,1,1,1]);
  57.100 μs (1017 allocations: 56.83 KiB)

julia> @btime unique(permutations([0,0,0,1,1,1]));
  152.400 μs (2174 allocations: 204.67 KiB)

julia> @btime unique_permutations([1;zeros(Int,100)]);
  7.047 ms (108267 allocations: 10.95 MiB)

julia> @btime unique(permutations([1;zeros(Int,8)]));
  88.355 ms (1088666 allocations: 121.82 MiB)

Julia：用重复项生成集合中的所有非重复排列

Julia: Generate all non-repeating permutations in set with duplicates

permutation

combinatorics

julia