permutations is much slower than it needs to be

[FedericoStra]

Julia is orders of magnitude slower than Python (well... C actually):

Julia benchmark

~/Code/julia/Combinatorics.jl on  master is 📦 v1.0.3 via ஃ v1.11.5
❯ julia --project
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.11.5 (2025-04-14)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> using BenchmarkTools, Combinatorics

julia> @time length(collect(permutations(1:7)))
  0.029035 seconds (10.09 k allocations: 590.836 KiB)
5040

julia> @time length(collect(permutations(1:8)))
  0.588430 seconds (80.65 k allocations: 5.230 MiB)
40320

julia> @time length(collect(permutations(1:9)))
 14.055716 seconds (725.77 k allocations: 47.067 MiB, 0.23% gc time)
362880

julia> @time length(collect(permutations(1:10)))
377.505824 seconds (7.26 M allocations: 526.028 MiB, 0.14% gc time)
3628800

Python benchmark

~/Code/julia/Combinatorics.jl on  master is 📦 v1.0.3 via ஃ v1.11.5
❯ ipython
Python 3.13.3 (main, Apr 22 2025, 00:00:00) [GCC 15.0.1 20250418 (Red Hat 15.0.1-0)]
IPython 9.2.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: from itertools import permutations

In [2]: %timeit len(list(permutations(range(7))))
205 μs ± 2.9 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [3]: %timeit len(list(permutations(range(8))))
2.28 ms ± 37.6 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [4]: %timeit len(list(permutations(range(9))))
33.5 ms ± 398 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [5]: %timeit len(list(permutations(range(10))))
392 ms ± 5.95 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Ok, now that I've got your attention, let's see why. The main reason is that the algorithm currently used in Combinatorics.jl to enumerate permutations is asymptotically suboptimal: the function increment! walks 1-by-1 through all $n^n$ possible states, and after each increment the function has_repeats (which has quadratic complexity) checks whether to skip this state. Overall, the function iterate(::Permutations, ...) has order $O(n^{n+2})$, and at least $n^n$ disregarding has_repeats. As de Moivre and Stirling taught us, this is exponentially more work than the number of permutations, which is $n! \asymp e^{-n}n^{n+1/2}$.

This state of affairs is completely unnecessary, as even Wikipedia points to several more efficient algorithms, such as:

• Steinhaus–Johnson–Trotter algorithm

  Each two adjacent permutations in the resulting sequence differ by swapping two adjacent permuted elements. A version of the algorithm can be implemented in such a way that the average time per permutation is constant. As well as being simple and computationally efficient, this algorithm has the advantage that subsequent computations on the generated permutations may be sped up by taking advantage of the similarity between consecutive permutations.

• Heap's algorithm

  The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

• Pandit's algorithm

  One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence.

Among these three, only Pandit's algorithm generates permutations in lexicographic order, as iterate(::Permutations, ...) currently does, so this would be the recommended choice if we want to preserve this property.

These base algorithms only deal with the case of enumerating all permutations, so they are not directly suitable for the generalized function permutations(a, t::Integer); one would have to adapt them to this problem, or decipher the C implementation used by Python's itertools.permutations which is already capable of doing this.

Additionally, it could be nice to implement several argorithms (since they generate permutations in different orders) and have a way to select them such as

permutations(1:10; algo=SJT())
permutations(1:10; algo=Heap())
permutations(1:10; algo=Pandit()) # or Lexicographic()

[FedericoStra]

Yesterday I proposed #184, a low-effort optimization that provides approximately a 5× speed-up without changing the underlying algorithm. While it's easy to review, it's not intended as a long-term solution, more of a consolation prize.

[FedericoStra]

Regarding Pandit's algorithm, Wikipedia says that

It can handle repeated values, for which case it generates each distinct multiset permutation once.

It might be interesting to check whether it's possible to improve also multiset_permutations. I haven't investigated in detail, but we already know from #151 that, strangely, the more general multiset_permutations function is faster than the dedicated permutations, so that doesn't seem a priority right now.

---

In a comment to #151 I also suggest to temporarily implement permutations via multiset_permutations as

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

to exploit the efficiency of the latter.

I've created #186 that implements this change.