Slow permutations?

General Usage
4

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[1] > 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

7 Likes