`permutations` iteration regression in version 1.0.3

[Drvi]

Hi! We noticed that the iterating permutations got significantly slower in 1.0.3 for large-ish inputs: 1.0.2

julia> ps = Combinatorics.permutations([i for i in 1:11])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 11)

julia> @time iterate(ps)
  0.000008 seconds (4 allocations: 464 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10])

julia> ps = Combinatorics.permutations([i for i in 1:12])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 12)

julia> @time iterate(ps)
  0.000005 seconds (4 allocations: 512 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11])

1.0.3

julia> ps = Combinatorics.permutations([i for i in 1:11])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 11)

julia> @time iterate(ps)
  7.115521 seconds (3 allocations: 320 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])

julia> ps = Combinatorics.permutations([i for i in 1:12])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], 12)

julia> @time iterate(ps)
184.690355 seconds (3 allocations: 352 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

It would be great to have a permutations iterator that is as fast as the 1.0.2 version for larger inputs. Thank you!

[inkydragon]

Hope pr #186 will fix this regression. Or revert #122

v1.0.2

julia> ps = Combinatorics.permutations([i for i in 1:11])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 11)

julia> @time iterate(ps)
  0.041737 seconds (107.14 k allocations: 5.476 MiB, 99.92% compilation time)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10])

julia> @time iterate(ps)
  0.000005 seconds (7 allocations: 464 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10])

julia> @time iterate(ps)
  0.000005 seconds (7 allocations: 464 bytes)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10])

master

julia> ps = Combinatorics.permutations([i for i in 1:11])
Combinatorics.Permutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 11)

julia> @time iterate(ps)
  0.140973 seconds (435.32 k allocations: 22.173 MiB, 99.89% compilation time)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], (mp = Combinatorics.MultiSetPermutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 11, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]), mp_state = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10]))

julia> @time iterate(ps)
  0.000012 seconds (47 allocations: 3.188 KiB)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], (mp = Combinatorics.MultiSetPermutations{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 11, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]), mp_state = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10]))

[Bumblebee00]

any updates?