This is an alternative site for discovering Elm packages. You may be looking for the official Elm package site instead.

# Combinatorics.Lists

get* functions - generate the list of all possible comb. / permut. / variat.

All functions return `Ok List` or `Err String`.

Error example: `"getVariations limitation: k >= 0, your k = -2"`

Create issue / pull requests for more effective computations, lazy loadings, etc.

# Variations

getVariationsWithReps : Int -> List a -> Result String (List (List a))

Get list of variations with repetitions.

Limitations: k >= 0, n >= 0

``````getVariationsWithReps 2 [ "a", "b" ] == Ok [["a","a"],["a","b"],["b","a"],["b","b"]]
``````
getVariations : Int -> List a -> Result String (List (List a))

Get list of variations.

Limitations: k >= 0, (List.length set) >= k

``````getVariations 2 [ "a", "b" ] == Ok [["a","b"],["b","a"]]
``````

# Permutations

getPermutationsWithReps : List ( comparable, Int ) -> Result String (List (List comparable))

Get list of permutations with repetitions.

Limitations: kx >= 0 (kx is 2nd value in tuple), a is unique (a is 1st value in tuple)

``````getPermutationsWithReps [ ( "a", 1 ), ( "b", 2 ) ] == Ok [["a","b","b"],["b","a","b"],["b","b","a"]]
``````
getPermutations : List a -> Result String (List (List a))

Get list of permutations.

``````getPermutations [ "a", "b" ] == Ok [["a","b"],["b","a"]]
``````

# Combinations

getCombinationsWithReps : Int -> List a -> Result String (List (List a))

Get list of combinations with repetitions.

Limitations: k >= 0, (List.length set) > 0

``````getCombinationsWithReps 2 [ "a", "b" ] == Ok [["a","a"],["a","b"],["b","b"]]
``````
getCombinations : Int -> List a -> Result String (List (List a))

Get list number of combinations.

Limitations: k >= 0, n >= 0, (List.length set) >= k

``````getCombinations 2 [ "a", "b", "c" ] == Ok [["a","b"],["a","c"],["b","c"]]
``````
``````module Combinatorics.Lists
exposing
( getCombinations
, getCombinationsWithReps
, getPermutations
, getPermutationsWithReps
, getVariations
, getVariationsWithReps
)

{-| **get* functions** - generate the list of all possible comb. / permut. / variat.

All functions return `Ok List` or `Err String`.

Error example: `"getVariations limitation: k >= 0, your k = -2"`

_Create issue / pull requests for more effective computations, lazy loadings, etc._

# Variations

@docs getVariationsWithReps, getVariations

# Permutations

@docs getPermutationsWithReps, getPermutations

# Combinations

@docs getCombinationsWithReps, getCombinations

-}

import List.Extra exposing (allDifferentBy)

{-| Get list of variations with repetitions.

Limitations: k >= 0, n >= 0

getVariationsWithReps 2 [ "a", "b" ] == Ok [["a","a"],["a","b"],["b","a"],["b","b"]]

-}
getVariationsWithReps : Int -> List a -> Result String (List (List a))
getVariationsWithReps k set =
if k < 0 then
Err <| "getVariationsWithReps limitation: k >= 0, your k = " ++ toString k
else
Ok (getVariationsWithReps_ k set)

getVariationsWithReps_ : Int -> List a -> List (List a)
getVariationsWithReps_ k set =
let
doGetVariationsWithReps k set depth resultItem =
if depth < k then
set
|> List.concatMap
(\setItem -> doGetVariationsWithReps k set (depth + 1) (setItem :: resultItem))
else
[ resultItem |> List.reverse ]
in
doGetVariationsWithReps k set 0 []

{-| Get list of variations.

Limitations: k >= 0, (List.length set) >= k

getVariations 2 [ "a", "b" ] == Ok [["a","b"],["b","a"]]

-}
getVariations : Int -> List a -> Result String (List (List a))
getVariations k set =
if k < 0 then
Err <| "getVariations limitation: k >= 0, your k = " ++ toString k
else if List.length set < k then
Err <|
"getVariations limitation: (List.length set) >= k, your set = "
++ toString set
++ " and your k = "
++ toString k
else
Ok (getVariations_ k set)

getVariations_ : Int -> List a -> List (List a)
getVariations_ k set =
let
doGetVariations k set depth resultItem =
if depth < k then
set
|> List.concatMap
(\setItem ->
if List.member setItem resultItem then
[]
else
doGetVariations k set (depth + 1) (setItem :: resultItem)
)
else
[ resultItem |> List.reverse ]
in
doGetVariations k set 0 []

{-| Get list of permutations with repetitions.

Limitations: kx >= 0 (kx is 2nd value in tuple), a is unique (a is 1st value in tuple)

getPermutationsWithReps [ ( "a", 1 ), ( "b", 2 ) ] == Ok [["a","b","b"],["b","a","b"],["b","b","a"]]

-}
getPermutationsWithReps : List ( comparable, Int ) -> Result String (List (List comparable))
getPermutationsWithReps setWithCounts =
if List.any ((>) 0) (setWithCounts |> List.unzip |> Tuple.second) then
Err <| "getPermutationsWithReps limitation: k >= 0, your [(a,k)] = " ++ toString setWithCounts
else if not (setWithCounts |> allDifferentBy Tuple.first) then
Err <| "getPermutationsWithReps limitation: a is unique, your [(a,k)] = " ++ toString setWithCounts
else
Ok (getPermutationsWithReps_ setWithCounts)

getPermutationsWithReps_ : List ( a, Int ) -> List (List a)
getPermutationsWithReps_ setWithCounts =
let
totalCount =
setWithCounts |> List.unzip |> Tuple.second |> List.sum

doGetPermutationsWithReps k set depth resultItem =
if depth < k then
set
|> List.concatMap
(\( setItem, count ) ->
if (resultItem |> List.filter ((==) setItem) |> List.length) == count then
[]
else
doGetPermutationsWithReps k set (depth + 1) (setItem :: resultItem)
)
else
[ resultItem |> List.reverse ]
in
doGetPermutationsWithReps totalCount setWithCounts 0 []

{-| Get list of permutations.

getPermutations [ "a", "b" ] == Ok [["a","b"],["b","a"]]

-}
getPermutations : List a -> Result String (List (List a))
getPermutations n =
Ok (getPermutations_ n)

getPermutations_ : List a -> List (List a)
getPermutations_ set =
getVariations_ (List.length set) set

{-| Get list of combinations with repetitions.

Limitations: k >= 0, (List.length set) > 0

getCombinationsWithReps 2 [ "a", "b" ] == Ok [["a","a"],["a","b"],["b","b"]]

-}
getCombinationsWithReps : Int -> List a -> Result String (List (List a))
getCombinationsWithReps k set =
if k < 0 then
Err <| "getCombinationsWithReps limitation: k >= 0, your k = " ++ toString k
else if List.length set == 0 then
Err <| "getCombinationsWithReps limitation: (List.length set) > 0, your set = " ++ toString set
else
Ok (getCombinationsWithReps_ k set)

getCombinationsWithReps_ : Int -> List a -> List (List a)
getCombinationsWithReps_ k set =
if k == 0 then
[ [] ]
else
case set of
[] ->
[]

x :: xs ->
List.map ((::) x) (getCombinationsWithReps_ (k - 1) set) ++ getCombinationsWithReps_ k xs

{-| Get list number of combinations.

Limitations: k >= 0, n >= 0, (List.length set) >= k

getCombinations 2 [ "a", "b", "c" ] == Ok [["a","b"],["a","c"],["b","c"]]

-}
getCombinations : Int -> List a -> Result String (List (List a))
getCombinations k set =
if k < 0 then
Err <| "getCombinations limitation: k >= 0, your k = " ++ toString k
else if List.length set < k then
Err <|
"getCombinations limitation: (List.length set) >= k, your set = "
++ toString set
++ " and your k = "
++ toString k
else
Ok (getCombinations_ k set)

getCombinations_ : Int -> List a -> List (List a)
getCombinations_ k set =
if k == 0 then
[ [] ]
else
case set of
[] ->
[]

x :: xs ->
List.map ((::) x) (getCombinations_ (k - 1) xs) ++ getCombinations_ k xs
```
```