better performing `isPermutationOf`

[lue-bird]

isPermutationOf is implemented as

isPermutationOf permut xs =
    member permut (permutations xs)

It first calculates all n! permutations, then looks if the given list matches any. This makes isPermutationOf a very heavy operation: ellie

We can do the same job in O(n^2) time:

isPermutationOf permut xs =
    (length permut == length xs)
        && (permut |> all (\a -> xs |> member a))

You could also remove elements you already checked from the second list but in effect, both implementations perform equally as good. ellie

The PR also adds tests and examples for the new isPermutationOf and fixes a spelling mistake (applyed) in the allDifferentBy doc.

[Chadtech]

Awesome. That is a huge increase! Thank you

[gampleman]

This is indeed much faster, unfortunately it is also incorrect.

> isPermutationOf [1,1,1] [1,2,3]
True : Bool

I would suggest reverting this.

---

Also, there is an easy oracle based test that can be used for any new implementation:

fuzz2 (list int) (list int) "works the same as sorting" <|
 \(a b) ->
    isPermutationOf a b
       |> Expect.equal (List.sort a == List.sort b)

[lue-bird]

Sorry for the trouble! Thanks @gampleman for noticing this! A version that works (hopefully) and has the same performance:

isPermutationOf : List a -> List a -> Bool
isPermutationOf permut xs =
    let
        removeOneMember : a -> List a -> { foundAny : Bool, without : List a }
        removeOneMember culprit =
            removeOneMemberHelp culprit []

        removeOneMemberHelp culprit before list =
            case list of
                [] ->
                    { foundAny = False, without = [] }

                head :: after ->
                    if head == culprit then
                        { foundAny = True, without = before ++ after }

                    else
                        removeOneMemberHelp culprit (head :: before) after
    in
    case ( permut, xs ) of
        ( [], [] ) ->
            True

        ( [], _ :: _ ) ->
            False

        ( _ :: _, [] ) ->
            False

        ( _ :: _, x :: after ) ->
            let
                { foundAny, without } =
                    removeOneMember x permut
            in
            if foundAny then
                isPermutationOf without after

            else
                False

[Chadtech]

Thanks all for catching this so quickly. I plan on circling back to this tonight and releasing a new version.

[Chadtech]

Okay. I released 8.5.1 with your new implementation @lue-bird . It passed the tests, passed a new test that [1,1,1] is not a permutation of [1,2,3], and I added @gampleman 's fuzz test.

Thanks again!