<jupyter_start><jupyter_text>Selection sort<jupyter_code>:set -XNoMonadFailDesugaring
:l SortersM
:l Predicates<jupyter_output><empty_output><jupyter_text>It turns out, that combining the default implementation of selection sort with `coinCmp` leads to enumerating multiple times some of the sequences - we get a supermultiset of the permutation set.<jupyter_code>selectSortM coinCmp [3,2,1] :: [[Int]]<jupyter_output><empty_output><jupyter_text>The reason behind this, is the inconsistency of our predicate - during algorithm we may ask multiple times about the same pair of elements, but `coinCmp` may return different answers and thus leading to extra results. We can overcome this problem by guarding the consistency - we do that by keeping a *state* within our nondeterministic procedure, namely on every branch we keep track of the already built relation.<jupyter_code>import Control.Monad.State
evalStateT (selectSortM consistentCoinCmp [3,2,1]) noChoices :: [[Int]]<jupyter_output><empty_output><jupyter_text>To avoid using monadic tranformers and states, we can instead use Set monad.<jupyter_code>import qualified Data.Set.Monad as SetM (toList)
SetM.toList $ selectSortM coinCmp [3,2,1]<jupyter_output><empty_output><jupyter_text>However, this approach is kind of inefficient. We sieve permutations after creating them. We may try to optimize this process one level lower - while seeking for minimum.Here is the default implementation, but with inlined code of `coinCmp` and simplifications:<jupyter_code>minimumNDM :: (MonadPlus m) => [a] -> m a
minimumNDM [x] = return x
minimumNDM (x:xs) = do
    y <- minimumNDM xs
    return x `mplus` return y

minimumNDM [1,2,3] :: [Int]<jupyter_output><empty_output><jupyter_text>If we assume, that our monad is both idempotent wrt `mplus` and left distributive wrt `bind` and `mplus` we can simplify the implementation even more, avoiding calling `return x` unnecessary. As the list monad doesn't satisfy these requirements, we lose some of the results:<jupyter_code>minimumNDM :: (MonadPlus m) => [a] -> m a
minimumNDM [x] = return x
minimumNDM (x:xs) = return x `mplus` minimumNDM xs

minimumNDM [1,2,3] :: [Int]<jupyter_output><empty_output><jupyter_text>Fortunately, it is sufficient to get exactly `n!` unique permutations with inconsistent predicate (we have abandoned tracking answers).<jupyter_code>import qualified Data.List as List

selectSortNDM :: (Eq a, MonadPlus m) => [a] -> m [a]
selectSortNDM [] = return []
selectSortNDM xs = do
    x <- minimumNDM xs
    fmap (x:) (selectSortNDM (List.delete x xs))

selectSortNDM [1,2,3] :: [[Int]]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09108159392789374, 'fraction_numerical': 0.00683111954459203, 'mean_word_length': 5.992042440318302, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '338970', 'license': 'MIT', 'n_tokens_mistral': 857, 'n_tokens_neox': 814, 'n_words': 302, 'path': 'notebooks/SelectSort.ipynb', 'repo_name': 'pmikolajczyk41/all-sorts-of-permutations', 'size': '2635'}