Add Catalan sequence (TheAlgorithms#266)

GF1977 · web-flow · commit 255ce8671d92 · 2021-10-23T12:43:38.000+03:00
diff --git a/Algorithms.Tests/Sequences/CatalanSequenceTest.cs b/Algorithms.Tests/Sequences/CatalanSequenceTest.cs
@@ -0,0 +1,22 @@
+using System.Linq;
+using System.Numerics;
+using Algorithms.Sequences;
+using FluentAssertions;
+using NUnit.Framework;
+
+namespace Algorithms.Tests.Sequences
+{
+    public class CatalanSequenceTest
+    {
+        [Test]
+        public void First30ItemsCorrect()
+        {
+            var sequence = new CatalanSequence().Sequence.Take(30);
+            sequence.SequenceEqual(new BigInteger[]     { 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
+                                                        9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020,
+                                                        91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152,
+                                                        69533550916004, 263747951750360, 1002242216651368})
+                .Should().BeTrue();
+        }
+    }
+}
diff --git a/Algorithms/Sequences/CatalanSequence.cs b/Algorithms/Sequences/CatalanSequence.cs
@@ -0,0 +1,38 @@
+using System.Collections.Generic;
+using System.Numerics;
+
+namespace Algorithms.Sequences
+{
+    /// <summary>
+    ///     <para>
+    ///         Catalan numbers: C[n+1] = (2*(2*n+1)*C[n])/(n+2).
+    ///     </para>
+    ///     <para>
+    ///         Wikipedia: https://en.wikipedia.org/wiki/Catalan_number.
+    ///     </para>
+    ///     <para>
+    ///         OEIS:http://oeis.org/A000108.
+    ///     </para>
+    /// </summary>
+    public class CatalanSequence : ISequence
+    {
+        /// <summary>
+        ///     Gets sequence of Catalan numbers.
+        /// </summary>
+        public IEnumerable<BigInteger> Sequence
+        {
+            get
+            {
+                // initialize the first element (1) and define it's enumerator (0)
+                var catalan = new BigInteger(1);
+                var n = 0;
+                while (true)
+                {
+                    yield return catalan;
+                    catalan = (2 * (2 * n + 1) * catalan) / (n + 2);
+                    n++;
+                }
+            }
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -92,6 +92,7 @@ This repository contains algorithms and data structures implemented in C# for ed
     * [A000027 Natural](./Algorithms/Sequences/NaturalSequence.cs)
     * [A000040 Primes](./Algorithms/Sequences/PrimesSequence.cs)
     * [A000045 Fibonacci](./Algorithms/Sequences/FibonacciSequence.cs)
+    * [A000108 Catalan](./Algorithms/Sequences/CatalanSequence.cs)
     * [A000142 Factorial](./Algorithms/Sequences/FactorialSequence.cs)
     * [A001462 Golomb's](./Algorithms/Sequences/GolombsSequence.cs)
     * [A005132 Recaman's](./Algorithms/Sequences/RecamansSequence.cs)
