CODEWITHSUNDEEP
pythoncatalan
user11032131
user11032131

Reputation:

How to find number of correctly matched parentheses using Catalan numbers?

I have a task to find number of expressions containing n parentheses which are correctly matched. So, I decided to use Catalan number. Here is a python code.

from decimal import Decimal

n = int(input())

res = Decimal(1)

k = n//2

for i in range(1,  k+1):
    res = Decimal(res*(n-k+i)/i)

res = int(res)

print(int(res//(k+1)))

After testing it in testing system, I have only 2 correct answers of 100. When: n = 2 (answer: 1) ans n = 4 (answer: 2). I can't look at other testing examples. Can you, please, help me? Where am I wrong?

Upvotes: 0

Views: 302

Answers (3)

Alain T.
Alain T.

Reputation: 42133

Since the value of C(2n,n) is always going to be an integer and can be computed with only integer intermediate results, you can use integer arithmetics without any risk of running into number representation issues:

def catalan(n):
    c = 1
    for p in range(n+1,2*n+1):
        c = c * p // (p-n)
    return c // (n+1)

for n in range(10): print(catalan(n))
    
1
1
2
5
14
42
132
429
1430
4862

This is based on the definition of Catalan numbers found here: https://en.wikipedia.org/wiki/Catalan_number

Python 3.8 now has a combination function in the math module which would make this even easier:

def catalan(n): return math.comb(2*n,n)//(n+1)

For prior versions of Python, you could make your own comb() function:

def comb(n,r):
    if n-r > r: return comb(n,n-r)
    result = 1
    for i in range(r+1,n+1):
        result = result * i // (i-r)
    return result

Note that the first catalan function above uses a streamlined version of this

Upvotes: 1

Serge Ballesta
Serge Ballesta

Reputation: 149085

You are probably trying to use Decimal numbers because your know that floating point arithmetic is broken. Unfortunately Decimal arithmetic is broken too and for the same underlying reason: rational numbers can only be exactly represented if the denominator of the reduced fraction only contains factors dividing 10 in that numeration system.

In base 2 (common floating point) only 1/2**n fractions can be represented, so 0.2 (1/5) can only be represented as an approximation. But in base 10, 0.1 can indeed be represented but 1/3 is the infinite 0.33333... that will be an approximation in a finite computer.

As you use rational numbers that by construction will finally give integer values, you have two possible paths:

  • the efficient but complex path: as the result will be integer, there must exist a computational path using only integers intermediary result. Is you use that path, you only use integer arithmetics and will suffer no approximation error
  • the direct and robust path using fractions.Fraction: a Fraction keeps separatedly its numerator and denominator parts. So all rational arithmetics give an exact representation (as a Fraction but neither as a floating point or Decimal)

TL/DR: just replace Decimal with Fraction if you want exact rational arithmetics

But you formule looks weird. According to Wikipedia, it should be Prod(n-k/k) for 2<=k<=n:

from fractions import Fraction

n = int(input())

res = 1

for k in range(2, n+1):
    res = res * Fraction(n-k, k)

res = int(res)

print(int(res//(k+1)))

I can confirm that this formula gives the first 10 Catalan numbers.

Upvotes: 0

Tim Roberts
Tim Roberts

Reputation: 54733

I'm not sure where you got your Catalan formula, nor why you think this is related to finding parentheses, nor why you used the Decimal type at all. The following program prints the Nth Catalan number:

n = int(input())

res = 1
for k in range(2,n+1):
    res = res * (n+k) / k

print( int(res) )

Upvotes: 0

Related Questions