A program supposed to write all correct parantheses in Python

Question

I'm attempting to write a program that (For a given natural n, not greater than 50):

• Writes all possible combinations of 2n parentheses that are correct, which means that at every line of the otput there's a sequence of parentheses with those properties:

  • The sequence has n open, n closed parentheses
  • At no point there is a closing parenthesis that was not opened

I've done almost exactly the same code in Java and it works perfectly, but somehow the following code breaks:

MAX = 100;
arr = [];
for i in range(0, MAX):
        arr.append(' ');

def write(n, pos, op, cl):
        if (cl == n):
                for i in range(0, MAX):
                        if arr[i] != ' ':
                                print(arr[i]);
                        else:
                                break;
                print("\n");
        else:
                if (op > cl):
                        arr[pos] = ')';
                        write(n, pos+1, op, cl+1);
                if (op < n):
                        arr[pos] = '(';
                        write(n, pos+1, op+1, cl);

n = raw_input();

write(n, 0, 0, 0);

The idea is pretty basic, but when I'm trying to run it, I get an error stating that at some point the statement

arr[pos] = '(';

Is illegal since the variable pos is >= MAX

I'm not very acquainted with Python yet, but I can't see the reason from the algorithmic point of view.

I'd appreciate any ideas

Answer 1

I'm using Python 2.7.9, but basically your problem is that you're using raw_input(), which gets input in the form of a string.

If you just convert that to an integer using int(), your code will work:

MAX = 100;
arr = [];
for i in range(0, MAX):
        arr.append(' ')

def write(n, pos, op, cl):
        if (cl == n):
                for i in range(0, MAX):
                        if arr[i] != ' ':
                                print(arr[i]), #add a comma here
                        else:
                                break;
                print("\n")
        else:
                if (op > cl):
                        arr[pos] = ')'
                        write(n, pos+1, op, cl+1)
                if (op < n):
                        arr[pos] = '('
                        write(n, pos+1, op+1, cl)

n = int(raw_input())  #change the input to an integer

write(n, 0, 0, 0)

Also, I added a comma after your print statement, so it would output like this:

>>> 
3
( ) ( ) ( ) 

( ) ( ( ) ) 

( ( ) ) ( ) 

( ( ) ( ) ) 

( ( ( ) ) )