How to Avoid MemoryError About Permutations in Python

Question

I'm writing a simple rar/zip cracking program. For cracking their passwords, I prepared a permutation command. But when I run these codes:

>>> import itertools
>>> o = itertools.permutations("abcdefghijklmnoprstuvyzwxq1234567890_", 10)
>>> a = list(o)

I got this error:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

There would be 1264020397516800 permutations of length 10 in your list. Storing them in memory would take over 160 TB (assuming each permutation takes up 128 bytes). — Alex Riley, Jun 06 '15 at 21:33

score 4 · Answer 1 · edited May 23 '17 at 12:03

4

UPD:

First of all, you should use product function from itertools module instead of permutations if you want to get all possible passwords from this alphabet.

Also, if you want to increase speed of execution, you should use multiprocessing module instead of threading.

You may achieve your goal this way, for example:

from itertools import product, islice
from multiprocessing import Pool

def crack(list_of_tuples):
    for letters in list_of_tuples:
        password = ''.join(letters)
        success = try_to_crack(password)
        if success:
            print('password is {}'.format(password))
            break

tuples = product('abcdefghijklmnoprstuvyzwxq1234567890_', repeat=10)

size_of_slice = 5000
number_of_processes = 8
running = True
while running:
    p = Pool(number_of_processes)
    slices = []
    for i in range(number_of_processes):
        l = list(islice(tuples, size_of_slice))
        if l:
            slices.append(l)
        else:
            running = False
    p.map(crack, slices)

See also multiprocessing-vs-threading

Original answer:

Don't create a list, just use it as it is:

permutations = itertools.permutations("abcdefghijklmnoprstuvyzwxq1234567890_", 10)
for permutation in permutations:
    password = ''.join(permutation)
    success = try_to_crack(password)
    if success:
        print('password is {}'.format(password))
        break

edited May 23 '17 at 12:03

Community

1
1

answered Jun 06 '15 at 21:29

Aleksandr Kovalev

3,508
4
34
36

I know it. But, I'm trying to use permutations as list through "a = list(o)" command. – python_pardus Jun 07 '15 at 07:58
@python_pardus Why? What do you want to do with this list? – Aleksandr Kovalev Jun 07 '15 at 08:56
In order to crack passwords fast, I must divide permutation list and send them seperate Threads. I mean that: http://pastebin.com/JYNezUaj – python_pardus Jun 07 '15 at 09:43
Thanks.. But I couldn't understand that why did you give "8" value to number_of_processes variable ? And what does the number in Pool function (Pool(number_of_processes)) change ? I mean if we give 7 value in the Pool function, what will change ? – python_pardus Jun 07 '15 at 14:48
When I tried codes, I got that error: "AttributeError: __exit_._" – python_pardus Jun 07 '15 at 15:08
@python_pardus `number_of_processes` is number of processes that you want to spawn. For example, if you have 4-core processor, change this number to `4` – Aleksandr Kovalev Jun 07 '15 at 16:00
@python_pardus give me your full code and full traceback. And, please, update your answer, as was suggested. – Aleksandr Kovalev Jun 07 '15 at 16:02
My program's codes: http://pastebin.com/uEqx3S8s The error I got: http://pastebin.com/EggkfCU8 – python_pardus Jun 07 '15 at 17:14
@python_pardus Seems like you have python2.7. I've updated my answer – Aleksandr Kovalev Jun 07 '15 at 18:26
Yes, I am using python2.7.It wrote a list but I got that error: http://pastebin.com/WkW24g1q – python_pardus Jun 07 '15 at 19:52
@python_pardus It's because you use method `self.find` as target in `pool.map`. You can't do this because of this: http://stackoverflow.com/questions/8804830/python-multiprocessing-pickling-error Use a function instead of method. – Aleksandr Kovalev Jun 07 '15 at 20:08
@python_pardus I strongly recommend you not using OOP. You are doing it wrong anyway. Use just plain function. – Aleksandr Kovalev Jun 07 '15 at 20:10
I corrected it. I used function instead of method. I didn't used OOP. But when I ran it, more than over 70 python.exe process opened and my computer got stuck. When I opened task manager, CPU was 100%. I had to restart my computer. What can I do ? – python_pardus Jun 08 '15 at 17:39

jsbueno · Answer 2 · 2020-02-28T16:12:50.987

2

Don't create a "list" of the permutations. The "permutations" call is a special construct tat will generate one permutation at a time - the idea is that you consume it, and then retrieve the next value.

When you do

>>> a = list(o)

You want to record all values at once in memory -which does not suffice in this case.

As a side note - if you do generate one permutation at a time in your particular example, you won run out of memory, but you, your computer, the Solar system and the Universe in general will run out of time, as the number of combinations for 10 elements out of 30 or so is beyond astronomical.

edited Feb 28 '20 at 16:12

answered Jun 06 '15 at 21:30

jsbueno

99,910
10
151
209

1

If I'm not mistaken, at one million passwords per second it's just 40 years. I hope the universe will still be around then. – Stefan Pochmann Jun 06 '15 at 21:42
@jsbueno I'm trying to use permutations as list through "a = list(o)" command. I must use it through "a = list(o)" command. – python_pardus Jun 07 '15 at 08:01
And why do you think you have to use them as a list? The whole idea of iterators in Python - and they are around for more than a decade now, is exactly to avoid having to have all elements in memory at once. Second: This number of permutations won't fit in memory - we are talking about 922393263052800 combinations here - if each would take just one byte that is nearly 1 milliion gigabytes. Again - if you do use the `permutations` as a generator, you won have the memory problem, but still, my joke about universe duration apart, it would take decades for you to check them all. – jsbueno Jun 08 '15 at 01:47

How to Avoid MemoryError About Permutations in Python

2 Answers2