permutations is less efficient than multiset_permutations

[FedericoStra]

I noticed that permutations is much less efficient than the more general multiset_permutations when they are both applied to a collection with unique elements:

julia> collect(permutations(1:8)) == collect(multiset_permutations(1:8, 8))
true

julia> @benchmark permutations(1:8) |> collect |> length
BenchmarkTools.Trial: 8 samples with 1 evaluation.
 Range (min … max):  614.237 ms … 656.276 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     626.957 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   632.481 ms ±  15.159 ms  ┊ GC (mean ± σ):  0.04% ± 0.12%

  █        █     ██   █          █                         █  █
  █▁▁▁▁▁▁▁▁█▁▁▁▁▁██▁▁▁█▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁█ ▁
  614 ms           Histogram: frequency by time          656 ms <

 Memory estimate: 6.46 MiB, allocs estimate: 80643.

julia> @benchmark multiset_permutations(1:8, 8) |> collect |> length
BenchmarkTools.Trial: 1080 samples with 1 evaluation.
 Range (min … max):  3.769 ms … 10.225 ms  ┊ GC (min … max):  0.00% … 28.42%
 Time  (median):     4.049 ms              ┊ GC (median):     0.00%
 Time  (mean ± σ):   4.624 ms ±  1.031 ms  ┊ GC (mean ± σ):  11.09% ± 14.36%

   ▄█▆▅▄▃▁        ▁       ▁▁    ▁
  █████████▆▇▆▁▆▆▇█▇▇█▇████████▇█▇▇█▇▇▆█████▇▆▇█▅▅▄▁▄▆▄▅▁▁▅▆ █
  3.77 ms      Histogram: log(frequency) by time     7.77 ms <

 Memory estimate: 11.38 MiB, allocs estimate: 120991.

I haven't investigated the reason behind this, but I believe that it is indicative of the fact that the implementation of permutations is not optimal.

Update

Yes, the algorithm is indeed not optimal, see #185.

[FedericoStra]

As a temporary workaround, we can define permutations via multiset_permutations as follows

permutations_trick(a, t::Integer=length(a)) =
    Iterators.map(
        indices -> [a[i] for i in indices],
        multiset_permutations(eachindex(a), t))

to gain a lot

julia> @time permutations(1:9) |> collect |> length
 14.273756 seconds (725.77 k allocations: 47.066 MiB)
362880

julia> @btime permutations_trick(1:9) |> collect |> length
  38.640 ms (2177340 allocations: 135.66 MiB)
362880