2

I'm new to Python. This is a homework problem, but it is tough as I only have a little experience in Java. The code is supposed to print the first Catalan-numbers using its recursive definition:

C(n + 1) = C(n) * (4n + 2) / (n + 2)

EDIT:

My current code looks like this, and the only remaining problem is to put all the C(n) numbers I get by this code in a txt using the savetxt() method.

import numpy

c = []
c.append(1)
for i in xrange(0,1000000000):
    c.append((4*i+2)*c[i]/(i+2))
    print (c[i])
    if c[i]>= 1000000000:
        break


numpy.savetxt("catalan",numpy.c_[i, c[i]])

After this last problem is solved, I will try some other versions suggested in the answers (like filling up an array of zeroes first).

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
mitlabence
  • 33
  • 9
  • you dont need if statement to break loop in here – Hackaholic Mar 20 '15 at 17:44
  • 1
    You're only using `numpy` to export the data, which doesn't seem terribly effiicient! If you create an empty array beforehand (e.g. with `numpy.zeros`) you can index all of them. – jonrsharpe Mar 20 '15 at 17:46
  • I'm sorry, I forgot to add the problem: find and list n and C(n) for all C(n) which are smaller than 1.000.000.000. The range in the for loop indicates that this last C(n) number will not be the one billionth C(n). I could refine the range of the for loop (or use while, but we have not yet used it in the course, so I'd have to figure it out). – mitlabence Mar 20 '15 at 17:48
  • I will try with the empty array, jonrsharpe, thank you! – mitlabence Mar 20 '15 at 17:50

5 Answers5

2

This is almost an exact duplicate of Python:: "IndexError: list index out of range"; in there I proposed that instead of using the recurrence, one should just use the iterative formula to produce the Catalan numbers; in your case you are using the iterative approach, but are storing them to an array. My approach is quite memory efficient compared to creating an array to store all n Catalan numbers:

def catalans():
    C = 1
    n = 0
    while True:
        yield C
        C = 2 * (2 * n + 1) * C // (n + 2)
        n += 1

with open('catalan', 'w') as output:
    for n, C in enumerate(1, catalans()):
        print(n, C, file=output)
        if C >= 1000000000:
            break
Community
  • 1
  • 1
Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
  • It can well be that this problem is common in university programming courses. It is of no use, however, to write (copy) a code I don't understand: my goal is to both complete the homework, and to get familiar to the methods I've seen during the course. In the code you've written, yield, itertools, and list are unknown to me, and are not supposed to be used in solving the problem. Nevertheless thank you for answering! – mitlabence Mar 20 '15 at 18:08
1

Index out of range. Your first i is equal to 1 but c only has one element, which is index 0. So just change the range to (0,1000000000).

By the way, don't use range, use xrange, it'll be faster and take less memory. When you use range, Python creates an array of that size. An array of size 1000000000 takes a ton of memory. Instead, xrange create an iterator so it takes much less memory.

ZekeDroid
  • 7,089
  • 5
  • 33
  • 59
  • It seems to work (memory error with range, but without errors with xrange). I'm now searching for the file output, I will edit this comment and accept your answer (unfortunately, I'm not allowed to mark your answer as useful, but it is a very helpful, short answer, for which I thank you very much!). Edit: Unfortunately the file has only this line: "1.900000000000000000e+01 1.767263190000000000e+09". – mitlabence Mar 20 '15 at 17:53
  • yeah, also notice that outside the for loop, `i` takes the last value so you're only appending the last one to numpy – ZekeDroid Mar 20 '15 at 18:06
  • That's my next issue: how is it achieved that a for-stlye loop is written inside the savetxt() method? I recall something like [0: x]. – mitlabence Mar 20 '15 at 18:09
  • yup, although that will give you all values of c from 0 to x-1 since it's non-inclusive of the last value – ZekeDroid Mar 20 '15 at 18:50
1

You can get better use out of numpy by actually using an array (which also makes the code look more like I think you originally had it):

import numpy as np

def catalan(x):
    """Create an array of the first x 'Catalan numbers'."""
    c = np.zeros(x)
    c[0] = 1
    for n in xrange(x-1):
        c[n+1] = c[n] * ((4 * n) + 2) / (n + 2)
    return c

If you can come up with a non-recursive definition, you can speed this up significantly (see e.g. Is a "for" loop necessary if elements of the a numpy vector are dependant upon the previous element?). Note that these numbers get big fast, though (you can only fit the first 34 in a 64-bit integer)!

Community
  • 1
  • 1
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
  • I think you could get rid of the loop entirely by doing e.g. `a = np.arange(15)` and `(((4*a)+2)/(a+2)).cumprod()` (you may then want to cast this to an integer array). But, as you say, the numbers get big quickly and may overflow! – Alex Riley Mar 20 '15 at 18:01
  • I appreciate your answer, it really looks more familiar to me. If I'm not mistaken, I only need to finish with an np.savetxt("...",np.c_[i,catalan[i]]). Is it correct? – mitlabence Mar 20 '15 at 18:01
  • @ajcr that's not *quite* the same series (`1, 2, 4, 8, 24` vs `1, 1, 2, 5, 14`) – jonrsharpe Mar 20 '15 at 18:03
  • @MitlasóczkiBence why don't you try it and see? – jonrsharpe Mar 20 '15 at 18:06
  • Are you sure it produces that other series? `(((4*a)+2)/(a+2)).cumprod()` produced an array containing `1, 2, 5, 14, 42, 132, 429, ...` - the Catalan numbers for `n = 1, 2, 3, 4, ...` when I ran it. – Alex Riley Mar 20 '15 at 18:13
  • @ajcr oddly, I just retried it, copied and pasted from your comment, and got 1, 2, 4, 8... – jonrsharpe Mar 20 '15 at 20:10
  • @jonrsharpe: Ah - I know what's happening! You have an older NumPy version where `/` does integer division and doesn't produce an array of floats. My division in 1.9.2 produces an array of floats which leads to the Catalan numbers. – Alex Riley Mar 20 '15 at 20:55
  • @ajcr I was using `numpy` 1.9.2 but you're on the right lines: it's an integer division issue, I'm running it on Python 2.7.9. Adding `dtype=float` fixed it. I feel suitably ashamed. Thanks! – jonrsharpe Mar 20 '15 at 20:57
0
for i in range(0, 1000000000):

This should work.

On your first iteration, you are trying to use c[1], but it doesn't exist. You only have a value for c[0], so the list index is out of range.

Kxxvc
  • 1
  • Thank you for clearing it up! There are more problems with the code, though (see my other comments on the other answers). – mitlabence Mar 20 '15 at 18:03
0

Wouldn't be easy if you use while?

C1,C2 = 1.0, 1.0
n=0
while C1<=1000000000:
    print(C1)
    C1,C2 = (((4*n+2)/(n+2)) * (C1)), C1
    n+=1
An3
  • 1