-
Notifications
You must be signed in to change notification settings - Fork 5
/
catalan.ex
95 lines (73 loc) · 2.37 KB
/
catalan.ex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
defmodule ExAlgo.Number.Catalan do
@moduledoc """
Catalan numbers are a sequence of natural numbers that occurs in many interesting
counting problems like counting the number of expressions containing n pairs
of parentheses that are correctly matched, the number of possible Binary Search
Trees with n keys, the number of full binary trees etc.
Here we present multiple ways to get Catalan numbers.
The first few Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
To see a list of Catalan numbers to aid in testing, visit:
https://www.mymathtables.com/numbers/first-hundred-catalan-number-table.html
"""
@doc """
Recursive implementation of catalan number.
NOTE: This is SLOW.
## Example
iex> 0..10 |> Enum.map(&Catalan.nth_recur/1)
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
"""
@spec nth_recur(non_neg_integer()) :: non_neg_integer()
def nth_recur(n) when n <= 1, do: 1
def nth_recur(n) when n > 1, do: do_recur(n, 0, 0)
defp do_recur(n, n, catalan), do: catalan
defp do_recur(n, iter, catalan) do
do_recur(
n,
iter + 1,
catalan + nth_recur(iter) * nth_recur(n - iter - 1)
)
end
@doc """
DP based implementation of catalan numbers.
## Example
iex> 0..10 |> Enum.map(&Catalan.nth_dp/1)
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
iex> Catalan.nth_dp(100)
896_519_947_090_131_496_687_170_070_074_100_632_420_837_521_538_745_909_320
"""
@spec nth_dp(non_neg_integer()) :: non_neg_integer()
def nth_dp(n), do: n |> as_map() |> Map.get(n)
@doc """
Dynamic programming implementation of catalan numbers that returns a list of
catalan numbers until `n`.
## Example
iex> Catalan.as_map(10)
%{
0 => 1,
1 => 1,
2 => 2,
3 => 5,
4 => 14,
5 => 42,
6 => 132,
7 => 429,
8 => 1430,
9 => 4862,
10 => 16796
}
"""
@spec as_map(non_neg_integer()) :: map()
def as_map(n) when n <= 1, do: %{n => 1}
def as_map(n) when n > 1 do
2..n
|> Enum.flat_map(fn i -> Enum.map(0..(i - 1), &{i, &1}) end)
|> Enum.reduce(init_catalans(n), fn {i, j}, acc ->
%{acc | i => acc[i] + acc[j] * acc[i - j - 1]}
end)
end
defp init_catalans(limit) do
0..limit
|> Enum.map(fn value -> {value, (value > 1 && 0) || 1} end)
|> Map.new()
end
end