Running into 'MemoryError' when running this Python code

Question

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!

I mean, consider the case where n == 6. How many elements do you expect to be in the resulting paren? Show your reasoning. Now, how much memory do you expect that to take up? Are you surprised that your machine can't handle that? — Karl Knechtel
– Karl Knechtel, Commented Oct 25, 2020 at 19:03
For one thing, it makes no sense to expand the iterator returned by permutations into a list, forcing every single one to be stored in memory whether valid or not. It makes much more sense to iterate over it directly, consuming no memory unless a given entry passes the matched test. An even better solution would be to generate the valid strings directly, without first generating all permutations and then filtering them. — Tom Karzes
– Tom Karzes, Commented Oct 25, 2020 at 19:04
Direct generation is a bit tricky. I had at least two ideas for an algorithm that I realized would both have issues before I even started writing. However, the simple fix here is to use combinations rather than permutations. This is really a math question rather than a programming question, although reading the documentation also helps. — Karl Knechtel
– Karl Knechtel, Commented Oct 25, 2020 at 19:13

a_guest · Accepted Answer · 2020-10-25 19:16:00Z

2

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:

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

answered Oct 25, 2020 at 19:16

a_guest

36.7k15 gold badges75 silver badges137 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Karl Knechtel Over a year ago

Now that I see it written out, I realize that I was trying to be too clever when thinking about it - looking for simplifications that aren't there, while the brute force approach is actually pretty simple. Nicely done.

Karl Knechtel · Accepted Answer · 2020-10-25 19:21:45Z

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?)

Collectives™ on Stack Overflow

Running into 'MemoryError' when running this Python code

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related