Johnson Trotter algorithm

Each permutation in the Johnson Trotter algorithm differs from the previous one by swapping two adjacent elements of the sequence.

The main benefit of this is that it can calculate and return one permutation at a time, instead of requiring all permutations to be found at once.

This means that you can analyse the permutations it creates one at a time, which in turn means that you can stop calculating more permutations when you are done, which in turn means that you can analyse lists of any size without causing a stack overflow.

The Step type represents the next permutation, if there is one.

type Step a
    = Done
    | Next (State a) (List a)

State is an opaque type, so to create the first Step you have to call first.

The next function returns the next Step in the sequence. It requires a State, which getState returns. The getPermutation helper function returns the permutation.

    JohnsonTrotter.first [ "a", "b", "c" ]
        |> JohnsonTrotter.getState
        |> Maybe.map JohnsonTrotter.next
        |> Maybe.andThen JohnsonTrotter.getPermutation
    -- [ "a", "c", "b" ]