Home > Mobile >  Memory Safe Permutations Generator with Increasing Length Value in ThreadPoolExecutor
Memory Safe Permutations Generator with Increasing Length Value in ThreadPoolExecutor

Time:05-27

I've referenced a few answers, and the one that makes the most sense comes from here, so I'm trying to modify it for my purposes.

I'm trying to create a generator that yields all of the permutations from a length of 1 to a MAX_RECURSION_LENGTH of 3, WITHOUT using lists because that just eats up 100% RAM instantly, all while using a multithreaded function.

I've included a minimal experimental code below, it doesn't work yet, but it's well commented and I think you'll be able to see what I'm trying to do. With a list of words:

list_of_words = ["I", "like", "to", "take", "my", "dogs", "for", "a",
                 "walk", "every", "day", "after", "work"]

...I want it to generate all the permutations up to the max length of 3, such as:

# Length of 1
("I",)
("like",) 
("to",)
("take",)
("my",)
...
("after",)
("work",)

# Length of 2
("I", "like",)
("I", "to",)
("I", "take",)
...
("I", "after",)
("I", "work",)

("like", "I",)
("like", "to",)
("like", "take",)
...
("like", "after",)
("like", "work",)
...

# Length of 3
("I", "like", "to",)
("I", "like", "take",)
("I", "like", "my",)
...
("I", "like", "after",)
("I", "like", "work",)

("like", "to", "take",)
("like", "to", "my",)
("like", "to", "dogs",)
...
("like", "to", "after",)
("like", "to", "work",)

# etc. etc., ending at
("work", "I", "like",)
("work", "I", "to",)
("work", "I", "take",)
...
("work", "after", "every",)
("work", "after", "day",)

Note, I did NOT include repeats here, however I don't mind if there are repeats, like ("work", "work", "work",) as my particular use case could benefit from them if possible. Remember to keep an eye on your RAM as you run this, I don't want it reaching 100%, which is why I think using generators and avoiding list(permutations()) is the best way to go. Also note that I don't care about speed of the code, so long as it keeps memory usage down. Here's the code:

import concurrent.futures
from itertools import permutations

# Variables
MAX_ENDPOINT_PERMUTATION_LENGTH = 3
MAX_WORKERS = 6

# List of words to permutate
list_of_words = ["I", "like", "to", "take", "my", "dogs", "for", "a",
                 "walk", "every", "day", "after", "work"]

# Generator from https://code.activestate.com/recipes/252178/
def all_perms(elements, length):
    # If the permutation length right now is 1, just return
    # the list_of_words as is
    if length == 1: 
        yield elements
    # Else, if the length is >= 2...
    else:
        # Iterate over the list, starting at "I" in the list_of_words
        for i in range(len(elements)):
            # Iterate over the current length of the permutation, which starts
            # at 1, so it should be ("I", "like",), then ("I", "to",), etc.
            for p in permutations(elements[:i]   elements[i 1:], length):
                # This yield throws an error because "p" is a tuple, even if it's
                # just one value at the beginning, and you can't add a tuple to
                # a string of "I". Might need to iterate over P, adding each
                # value to elements[i]  = p[k]? But how to do this with yield?
                yield elements[i]   p

# The multithreaded function we're going to use
def do_something_with_current_perm(current_perm):
    print(current_perm)

# Iterate through the range of MAX_ENDPOINT_PERMUTATION_LENGTH (3 by default)
for j in range(MAX_ENDPOINT_PERMUTATION_LENGTH):
    with concurrent.futures.ThreadPoolExecutor(max_workers=MAX_WORKERS) as executor:
        # Trying to pass in j 1 which is 0 1=1 at the beginning, meaning the current
        # permutation depth is 1 element, then it'll be 2, then 3
        try:
            future_results = {executor.submit(do_something_with_current_perm, perm): perm for perm in next(all_perms(list_of_words, j 1))}
        except KeyboardInterrupt:
            executor._threads.clear()
            concurrent.futures.thread._threads_queues.clear()
            break

UPDATE

I was able to make this work:

  1. I took out the all_perms function entirely
  2. I changed permutations to product to ensure I got the repeats I wanted

This is the working code now:

import concurrent.futures
from itertools import permutations, product

# Variables
MAX_ENDPOINT_PERMUTATION_LENGTH = 3
MAX_WORKERS = 6

# List of words to permutate
list_of_words = ["I", "like", "to", "take", "my", "dogs", "for", "a",
                 "walk", "every", "day", "after", "work"]

# The multithreaded function we're going to use
def do_something_with_current_perm(current_perm):
    print(current_perm)

# Iterate through the range of MAX_ENDPOINT_PERMUTATION_LENGTH (3 by default)
for j in range(1, MAX_ENDPOINT_PERMUTATION_LENGTH 1):
    with concurrent.futures.ThreadPoolExecutor(max_workers=MAX_WORKERS) as executor:
        try:
            future_results = {executor.submit(do_something_with_current_perm, perm): perm for perm in product(list_of_words, repeat=j)}
        except KeyboardInterrupt:
            executor._threads.clear()
            concurrent.futures.thread._threads_queues.clear()
            break

CodePudding user response:

To generate all permutations of lenght 1 to 3 you can use next example:

from itertools import permutations

list_of_words = ["I", "like", "to", "take", "my", "dogs", "for", "a",
                 "walk", "every", "day", "after", "work"]

for i in range(1, 4):
    for p in permutations(list_of_words, i):
        print(p)

Prints:

('I',)
('like',)
('to',)
('take',)
('my',)
('dogs',)
('for',)
('a',)
('walk',)
('every',)
('day',)
('after',)
('work',)
('I', 'like')
('I', 'to')
('I', 'take')

...

('work', 'after', 'walk')
('work', 'after', 'every')
('work', 'after', 'day')
  • Related