Permutations without Dups



In [1]:

    
import Data.List



In [2]:

    
permutationsWithoutDups :: String -> [String]
permutationsWithoutDups [] = [""]
permutationsWithoutDups [x] = [ [x] ]
permutationsWithoutDups (x:xs) =
    let
        wrap char left right = intercalate [char] [left, right]
        interweave char permutation = zipWith (wrap char) (inits permutation) (tails permutation)
    in
        concatMap (interweave x) $ permutationsWithoutDups xs



In [3]:

    
permutationsWithoutDups "abc"









    





["abc","bac","bca","acb","cab","cba"]



In [4]:

    
permutations "abc"









    





["abc","bac","cba","bca","cab","acb"]



In [5]:

    
import Test.QuickCheck

Test against the reference implementation:



In [6]:

    
testPermutations :: String -> Bool
testPermutations s =
    sort (permutations s) == sort (permutationsWithoutDups s)



In [7]:

    
quickCheckWith stdArgs { maxSize = 10 } testPermutations









    





+++ OK, passed 100 tests.

Test problem invariants:



In [8]:

    
import Data.Set



In [9]:

    
testPermutationsInvariants :: String -> Bool
testPermutationsInvariants s =
    let
        resultList = permutationsWithoutDups s
        resultSet = Data.Set.fromList resultList

        expectedLength = length resultList == product [1..length s]
        expectedChars = all (\x -> sort x == sort s) resultList
        -- noDuplicates = length resultList == length resultSet
    in
        expectedChars && expectedLength -- && noDuplicates



In [10]:

    
quickCheckWith stdArgs { maxSize = 10 } testPermutationsInvariants









    





+++ OK, passed 100 tests.

We need to write a custom string generator that generates strings of unique characters as defined in problem description, otherwise the test for the noDuplicates invariant will fail.