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

user_13634293 0
Viewed 498

Let's say, I have a vector x = [0, 0, 1, 1] I want to generate all different permutations. However, the current permutations function in Julia does not recognize the presence of duplicates in the vector. Therefore in this case, it will output the exact same permutation three times (this one, one where both zeros are swapped and one where the ones are swapped).

Does anybody know a workaround? Because in larger system I end up with an out of bounds error...

Many thanks in advance! :)

julia permutation combinatorics
2 Answers

permutations returns an iterator and hence running it through unique could be quite efficient with regard to memory usage.

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]
user_99577100

I found this answer that I adapted. It expects a sorted vector (or at least repeated values should be together in the list).


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)
user_141833430
Related