If I wanted to find the permutations of a list, I know that the number of permutations is given by the multinomial coefficient. For example, "MISSISSIPPI" has 11 letters, 'S' appears 4 times, 'I' appears 4 times, 'P' appears twice and 'M' appears once. So the number of permutations of "MISSISSIPPI" is equal to 11!/(4!4!2!) = 34650.
If I load up GHCi and write:
ghci> import Data.List
ghci> permutations [1,2,3]
It will return
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
as expected.
But if I write
ghci> permutations [1,0,0]
it will now return
[[1,0,0],[0,1,0],[0,0,1],[0,0,1],[0,1,0],[1,0,0]]
... which is very disappointing. As there are three elements, and two of them occur twice, one would hope for there only to be 6!/2! = 3 permutations, namely
[[1,0,0],[0,1,0],[0,0,1]]
rather than the six generated by treating each element of the list as distinct.
1) Why does Haskell implement "permutations" in the way described above (i.e. treating all elements of a list as distinct?)
2) Are there any standard library functions that calculate the permutations of a list in the "true" sense of permutations?
Remember that permutations
has type
permutations :: [a] -> [[a]]
That means that it satisfies the free theorem
permutations . map f = (map . map) f . permutations
for all functions f
. Since you can change the elements of the argument list arbitrarily without affecting the structure of the result list, permutations
must really be a function on the indices of the original list, rather than the elements.
So what permutations
is really doing --- what it must do --- is calculate all permutations of the indices of the argument list, then apply each of those permutations to the list and return the results. (I.e.,
permutations xn = (map . map) (xn!!) (permutations [0..length xn - 1])
for finite xn
).
Mathematical appendix:
Since
xn = map (xn!!) (zipWith const [0..] xn)
for all xn
, any function with permutations
's type must satisfy
permutations xn
= permutations (map (xn!!) (zipWith const [0..] xn)
= (map . map) (xn!!) (permutations (zipWith const [0..] xn))
by the equation above for xn
and the free theorem for permutations
. So any function with permutations
's type must operate only on the indices of the input list[1].
[1] Technically you can violate this by using seq
. But only for input lists that contain undefined
as an element, which isn't true in your case.
It is a design question and should be studied in deep. permutation
treats the elements of the list as if they were all different from each other. You can do permutations [0, 0, 0]
and you'll yet get a list of lists of size 6.
Yes, you have the Math.Combinat.Permutations
, but you can easily create your own definition filtering the unique combinations with a complexity of O(n * log n)
using sets, taking account that nub
is known by being very slow:
module Main where
import Data.List (permutations)
import qualified Data.Set as Set
nubOrd :: (Ord a) => [a] -> [a]
nubOrd xs = go Set.empty xs where
go s (x:xs)
| x `Set.member` s = go s xs
| otherwise = x : go (Set.insert x s) xs
go _ _ = []
permutations' :: (Ord a) => [a] -> [[a]]
permutations' = nubOrd . permutations
Where permutations' [1, 0, 0]
gives [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
.
Why does Haskell implement "permutations" in the way described above (i.e. treating all elements of a list as distinct?)
Because otherwise, the type would have to be:
permutations :: Eq a => [a] -> [[a]]
and then we could permute only things that have an Eq instance. But I remember I had something like
permutations [(+), subtract, (*), (/)]
in some Project Euler code ....
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With