# Slow permutations?

I have a an array of strings, of length ~2,000. I would like to produce all permutations of lengths 1 to `n` (`n` is always going to be less than or equal to 2).

The problem: this is taking much longer than I think it should. Am I missing an obvious optimization?

My current attempt is

``````import Combinatorics

"Return all permutations of sizes 1:`max_length`"
function power_permutations(iterable, max_length)
Iterators.flatten(Combinatorics.permutations(iterable, r) for r in 1:max_length)
end
``````

and simply running through it we get

``````using BenchmarkTools

@benchmark foreach(identity, power_permutations(collect(1:2_000), 2))

BenchmarkTools.Trial:
memory estimate:  60.80 GiB
allocs estimate:  20000015
--------------
minimum time:     17.592 s (36.62% GC)
median time:      17.592 s (36.62% GC)
mean time:        17.592 s (36.62% GC)
maximum time:     17.592 s (36.62% GC)
--------------
samples:          1
evals/sample:     1
``````

Woah, that is a lot of memory.

Let’s compare this to a similar version in Python.

``````import itertools

def power_permutations(iterable, max_length):
"Return all permutations of sizes 1:`max_length`"
for r in range(max_length + 1):
yield from itertools.permutations(iterable, r)

%timeit len(list(power_permutations(list(range(2000)), 2)))
484 ms ± 8.73 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
``````

hmmm, much faster than the Julia version.

Let’s try again with arrays of strings. In Julia:

``````@benchmark foreach(identity, power_permutations(collect(Iterators.repeated("hello",2_000)), 2))
BenchmarkTools.Trial:
memory estimate:  60.80 GiB
allocs estimate:  20000015
--------------
minimum time:     17.404 s (36.79% GC)
median time:      17.404 s (36.79% GC)
mean time:        17.404 s (36.79% GC)
maximum time:     17.404 s (36.79% GC)
--------------
samples:          1
evals/sample:     1
``````

And in Python:

``````%timeit len(list(power_permutations(["hello"]*2000, 2)))
473 ms ± 3.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
``````

We see more or less the same performance.

Am I missing something obvious here? Is this a shortcoming of the `permutations()` function in JuliaMath/Combinatorics?

I thought making it a bit more type safe (without checking if it was type safe in first place) and provide a size hint for the output vector would make a big difference, but I only got it down from 18 seconds to 12 seconds, which means the allocations are clearly coming from `Combinatorics.permutations`:

``````function power_permutations(iterable, max_length)
out = Vector{Vector{eltype(iterable)}}()
sizehint!(out, length(out)^max_length)
for r ∈ 1:max_length
for permutation ∈ Combinatorics.permutations(iterable, r)
push!(out, permutation)
end
end
out
end
``````
``````julia> @benchmark foreach(identity, power_permutations(collect(1:2_000), 2))
BenchmarkTools.Trial:
memory estimate:  60.83 GiB
allocs estimate:  20000027
--------------
minimum time:     12.716 s (12.95% GC)
median time:      12.716 s (12.95% GC)
mean time:        12.716 s (12.95% GC)
maximum time:     12.716 s (12.95% GC)
--------------
samples:          1
evals/sample:     1
``````

It looks like `Combinatorics` uses a pretty inefficient algorithm for generating permutations. There’s allocations every iteration here and here.

It’s probably much better to use Heap’s algorithm; I have an unpackaged version here.

2 Likes

I looked at the code for `permutations` in Combinatorics.jl, and I don’t completely understand what it’s doing. So here’s a pretty simple implementation that seems to perform well for small numbers of permutations. It’ll probably scale badly as the number of permutations increases, but it seems to be reasonably fast on your example:

``````struct PermutationIterator{T}
data::T
length::Int
end

function has_repeats(state)
for outer in 1:length(state)
for inner in (outer + 1):length(state)
if state[outer] == state[inner]
return true
end
end
end
return false
end

function increment!(state, max)
state[end] += 1
for i in length(state):-1:2
if state[i] > max
state[i] = 1
state[i - 1] += 1
end
end
end

function next_permutation!(state, max)
while true
increment!(state, max)
if !has_repeats(state)
break
end
end
end

function Base.iterate(p::PermutationIterator, state = ones(Int, p.length))
next_permutation!(state, length(p.data))
if state > length(p.data)
return nothing
end
[p.data[i] for i in state], state
end

Base.length(p::PermutationIterator) = Int(div(factorial(big(length(p.data))), factorial(big(length(p.data) - p.length))))
Base.eltype(p::PermutationIterator) = Vector{eltype(p.data)}

permutations(x, length) = PermutationIterator(x, length)
``````

Compared with `Combinatorics.permutations`, it’s about 40x faster:

``````julia> @btime foreach(identity, permutations(1:2000, 2))
230.554 ms (11994001 allocations: 671.05 MiB)

julia> @btime foreach(identity, Combinatorics.permutations(1:2000, 2))
9.889 s (19990001 allocations: 60.77 GiB)
``````

It should be possible to do a lot better than what I’ve posted here, particularly if we switch from an iterator producing `Vector` elements to one that produces `Tuple` elements

6 Likes

Would be great to at least open an issue on Combinatorics about the slowness. Even if it’s relatively easy to write a bespoke permutation generator, having a fast one in Combinatorics by default would be much better than the current state.

13 Likes
2 Likes