Memory error with string permutations

Question

I have this script that will calculate all permutations of a given string from a file:

import sys
from itertools import permutations


def find_permutations(word):
    perms = [''.join(p) for p in permutations(word)]
    return ','.join(perms)


if __name__ == '__main__':
    with open(sys.argv[1]) as data:
        for line in data.readlines():
            print(find_permutations(line.rstrip()))

However I have run into a Memory error with the following string American Pie. Is there a way I could get all the permutations of this string without running into a memory error? Or is it truly that there are so many, the system cannot handle it?

Exact error:

Traceback (most recent call last):
  File "string_perms.py", line 13, in <module>
    print(find_permutations(line.rstrip()))
  File "string_perms.py", line 7, in find_permutations
    return ','.join(perms)
MemoryError

Keep permutations as an iterator then you don't need to generate the whole list in memory — Chris_Rands, Nov 18 '16 at 16:44
@Chris_Rands I'm still new to python, can you give man example? — papasmurf, Nov 18 '16 at 16:47

Moses Koledoye · Accepted Answer · 2016-11-18T17:21:20.880

2

The one tip I think would fix this is to avoid reading the entire file into memory at once since you only need one line at a time:

with open(sys.argv[1]) as data:
    for line in data:
        for words in find_permutations(line.rstrip()):
             print(words)

And then you could skip creating the perms list entirely in your function and return a generator instead:

def find_permutations(word):
    return (''.join(p) for p in permutations(word))

On another note, I'm not sure it is of interest to include whitespaces in your permutations, otherwise you could replace all occurrences of those with an empty string.

edited Nov 18 '16 at 17:21

answered Nov 18 '16 at 16:55

Moses Koledoye

77,341
8
133
139

`"American Pie"` has 479001600 permutations. Printing out that many permutations at once is never going to work – Chris_Rands Nov 18 '16 at 17:08
1

@Chris_Rands I apparently didn't think of that initially. Good catch, updated. – Moses Koledoye Nov 18 '16 at 17:19
Ok, deleting my answer, as we're both saying the same thing now but your generator expression is neater. I think this is turning into an [XY problem](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) though – Chris_Rands Nov 18 '16 at 17:25

score 1 · Answer 2 · answered Nov 18 '16 at 17:25

Or is it truly that there are so many, the system cannot handle it?

Yup.

There will be math.factorial(len(word)) permutations of the string, and once those permutations are converted to strings and then joined with ',' into a larger string, your result is a string that's math.factorial(len(word)) * (len(word)+1) - 1 characters long. Even if each character only occupied one byte, that's 6227020799 bytes (6+ gigs) for the string 'American Pie'. Furthermore, you're starting from a list of permutations, so double that to get a rough estimate of the minimum memory allocated during that function call.

The real question is what exactly do you need to do with each of those perms? If you only need to use one at a time, take advantage of the fact that permutations is a lazy generator to begin with.

with open(sys.argv[1]) as data:
    for line in data:
        for perm in permutations(line):
            permstr = ''.join(perm)
            print(permstr, end=',')
            #do what you need with perm here

If you need to access a permutation at will, you'll have to think of something more involved like only computing some permutations in chunks and saving the data to disk to be accessed later.

what I need to do is output them in this format, for example `the,teh,het,..` — papasmurf, Nov 18 '16 at 18:16

Memory error with string permutations

2 Answers2