0

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?

Vladislav
  • 13
  • 2

3 Answers3

1

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

Alain T.
  • 40,517
  • 4
  • 31
  • 51
0

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.

Serge Ballesta
  • 143,923
  • 11
  • 122
  • 252
  • Hmm. I realy didn't know about broken Decimal. I'll keep it in mind. Thank you. Unfortunately, it is still doesn't work in testing system. – Vladislav Dec 03 '20 at 08:06
  • @Vladislav: then you should give the input, expected output and obtained output, because Fraction rational arithmetics is expected to be exact. – Serge Ballesta Dec 03 '20 at 08:09
  • That's the key problem, that I can't see extended result. I can only see is my answer Correct / Incorrect. – Vladislav Dec 03 '20 at 08:11
  • @Vladislav: do you at least know one value for which the code using fractions fails? – Serge Ballesta Dec 03 '20 at 08:13
  • @Vladislav I looked again at the Wikipedia page on Catalan numbers, and simplified your formula. It should be good now. – Serge Ballesta Dec 03 '20 at 09:30
  • In what way is the integer intermediate results path more complex or less robust ? I would argue that Python's infinite size integers provide a lot more robustness for large values of `n` and there would be exactly the same number of lines in the solution's code (and fewer iterations as well). – Alain T. Dec 04 '20 at 00:17
  • @AlainT. What I mean is that finding an algo that only uses integers is harder than simply using the one from Wikipedia. But that latter uses rational numbers (fractions). – Serge Ballesta Dec 04 '20 at 00:39
0

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) )
Tim Roberts
  • 48,973
  • 4
  • 21
  • 30
  • I use this formula https://e-maxx.ru/tex2png/cache/10ec54fa210d7eb7fcf78a25824015c3.png , then calculate C(n)(2n) in for loop. And Decimal I use because of 2 reasons. It's faster to calculate (at least in my case), I'm not trust to float (because of possible errors). https://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics - That's why I use Catalan numbers for solving. – Vladislav Dec 03 '20 at 08:25