-- | List permutation functions.
module Music.Theory.Permutations.List where

import Data.List {- base -}

import qualified Math.Combinatorics.Multiset as C {- multiset-comb -}

import qualified Music.Theory.Permutations as P {- hmt-base -}

-- | Generate all permutations.
--
-- > permutations_l [0,3] == [[0,3],[3,0]]
-- > length (permutations_l [1..5]) == P.n_permutations 5
permutations_l :: [a] -> [[a]]
permutations_l :: forall a. [a] -> [[a]]
permutations_l [a]
i =
    let f :: Permutation -> [a]
f Permutation
p = forall t. Permutation -> [t] -> [t]
P.apply_permutation Permutation
p [a]
i
    in forall a b. (a -> b) -> [a] -> [b]
map Permutation -> [a]
f (Int -> [Permutation]
P.permutations_n (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
i))

-- | /k/-element permutations of a set of /n/-elements.
--
-- > permutations_nk_l 3 2 "abc" == ["ab","ac","ba","bc","ca","cb"]
permutations_nk_l :: Eq e => Int -> Int -> [e] -> [[e]]
permutations_nk_l :: forall e. Eq e => Int -> Int -> [e] -> [[e]]
permutations_nk_l Int
n Int
k [e]
e =
  if forall (t :: * -> *) a. Foldable t => t a -> Int
length [e]
e forall a. Eq a => a -> a -> Bool
/= Int
n
  then forall a. HasCallStack => [Char] -> a
error [Char]
"permutations_nk_l"
  else forall a. Eq a => [a] -> [a]
nub (forall a b. (a -> b) -> [a] -> [b]
map (forall a. Int -> [a] -> [a]
take Int
k) (forall a. [a] -> [[a]]
permutations_l [e]
e))

-- | Generate all distinct permutations of a multi-set.
--
-- > multiset_permutations [0,1,1] == [[0,1,1],[1,1,0],[1,0,1]]
multiset_permutations :: Ord a => [a] -> [[a]]
multiset_permutations :: forall a. Ord a => [a] -> [[a]]
multiset_permutations = forall a. Multiset a -> [[a]]
C.permutations forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> Multiset a
C.fromList

-- | Calculate number of permutations of a multiset.
--
-- > let r = P.factorial 11 `div` product (map P.factorial [1,4,4,2])
-- > multiset_permutations_n "MISSISSIPPI" == r
--
-- > multiset_permutations_n "MISSISSIPPI" == 34650
-- > length (multiset_permutations "MISSISSIPPI") == 34650
multiset_permutations_n :: Ord a => [a] -> Int
multiset_permutations_n :: forall a. Ord a => [a] -> Int
multiset_permutations_n [a]
x =
    let occ :: [a] -> Permutation
occ = forall a b. (a -> b) -> [a] -> [b]
map forall (t :: * -> *) a. Foldable t => t a -> Int
length forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Eq a => [a] -> [[a]]
group forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => [a] -> [a]
sort
        n :: Int
n = forall n. Integral n => n -> n
P.factorial (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
x)
        d :: Int
d = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map forall n. Integral n => n -> n
P.factorial forall a b. (a -> b) -> a -> b
$ [a] -> Permutation
occ [a]
x
    in Int
n forall a. Integral a => a -> a -> a
`div` Int
d