CODEWITHSUNDEEP
pythonoptimization
steinou
steinou

Reputation: 43

Running into 'MemoryError' when running this Python code

I understand my code probably contains quite a few redundancies but I'm really struggling with optimizing it.

from itertools import permutations
n = 2
new = ['(',')'] * n
paren = list(permutations(new,(n*2)))
def matched(str):
    count = 0
    for i in str:
        if i == "(":
            count += 1  
        elif i == ")":
            count -= 1
        if count < 0:
            return False
    return count == 0
z = []
for d in paren:
    true = ''.join(d)
    if matched(true) == True:
        z.append(d)
f2 = set(z)
r = []
for i in f2:
    stru = ''.join(i)
    r.append(stru)
print(r)

My objective with this program is to provide with all possible n pairs of balanced parenthesis. The final results should be a list with various strings containing the parenthesis Ex: for n = 2 [ '()()', '(())' ]. Unfortunately this code only works when n < 6, otherwise the program runs into a memory issue.

File "real.py", line 4, in paren = list(permutations(new,(n*2))) MemoryError

Thank you in advance!

Upvotes: 0

Views: 51

Answers (2)

Karl Knechtel
Karl Knechtel

Reputation: 61635

Let's actually diagnose the contents of paren, using small n:

# As before...
from itertools import permutations
n = 2
new = ['(',')'] * n
paren = list(permutations(new,(n*2)))

def display(elements):
    for item in elements:
        print(''.join(item))

display(sorted(paren))

You'll notice quite a bit of repetition.

But itertools.combinations doesn't work directly, either - there's only one unique combination with all the elements, because of how order is considered.

We have multiple identical elements, and we want their order to matter, but not between identical elements.

The trick, instead, is to choose the positions where the (s will go (and put )s in the other positions). For this purpose, we can simply use a range(n*2) for the position candidates, and choose combinations of n of those. Then it's simply a matter of constructing the corresponding strings.

(Perhaps you can think of a way to check directly whether a given combination of ( positions corresponds to a valid string of matched parentheses. Hint: what does the difference between two adjacent ( positions tell you about the )s?)

Upvotes: 0

a_guest
a_guest

Reputation: 36309

You can use a recursive generator for that purpose:

def parens(s, max_len, n_open):
    if len(s) + n_open == max_len:
        yield s + n_open*')'
    elif n_open == 0:
        yield from parens(s + '(', max_len, n_open + 1)
    else:
        yield from parens(s + '(', max_len, n_open + 1)
        yield from parens(s + ')', max_len, n_open - 1)

Then you can iterate over the result like this:

n = 3
for s in parens('(', max_len=2*n, n_open=1):
    print(s)

Example output for n=3:

((()))
(()())
(())()
()(())
()()()

Upvotes: 2

Related Questions