## All sorts of permutations (Functional Pearl)

Published: 2016-09-17 (last updated: 2016-09-22)

This is about writing non-deterministic algorithms, then concatenating all possibilities to get all solutions.

First we will talk about a slightly simpler problem - computing sublists. Computing a sublist non-deterministically is filtering it with a predicate that non-deterministically returns true or false (like a coin flip). Every possible non-deterministic value will then give every possible sublist.

Now we replace the predicate with a non-deterministic comparison function instead. So it's actually a sorting algorithm. This computes a non-deterministic permutation. So all possibilities gives all permutations. However, different sorting algorithms have different behaviour when concatenating all possible results.

**Insertion sort** - This gives exactly all possibilities.

**Selection sort** - Gives some duplicate results. This is because some comparisons are made multiple times, and as it is non-deterministic it can give a different result each time. We want *consistency* - if we make a decision, we should have the same decision later on in the decision tree, by keeping some state about all made choices in our comparison function. This gets rid of the duplicates.

**Bubble sort** - This again gives duplicates. Applying consistency only gets rid of some of them. This is because the relationship we are using should be total (e.g. if comparing 2 and 3 is true then comparing 3 and 2 should be false). So we must make our comparison function smarter by also computing the total closures of all choices we've made.

**Quicksort** - Requires just consistency to get rid of duplicates.

**Patience sort** - Seems to be unique in that it not only needs consistency and totality (like in bubble sort), but also transitivity.

In the paper:

- Non-deterministic versions of pure functions via monadic generalisation.
- Analysis of different sorting algorithms.
- Inlining of predicates to gain permutations enumeration function.
- Proof that each permutation is enumerated.

Working on proof for exact permutations.

### Questions

Q: You're generating all sublists and permutations, would there be a function that could generate all possible partitions?

A: Some sort of non-deterministic group.

Q: Could you memoize the comparison function instead of keeping the past state?

A: Something to think about but we didn't do it. Doesn't give you transitivity?

Q: What if a stupid sorting algorithm is comparing elements to themselves?

A: Then the comparison function would need to understand reflexivity as well.