Filter through Permutations

Question

I'm coding a project and I've realized that when I try to do long permutations, my program just takes forever to run it. The good thing is that the only permutations that I need are the ones that start with and end with a '#'. Here's a function that I am using to collect permutations:

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

permut('c#e#')

and the only permutations I would need would be if array[0] = '#' and array[len(s)-1] = '#'. I apologize if this is a similar question, but how would I filter through strings I do not need and make my code actually run and not take forever.

Answer 1

Take two # characters out of the input, generate permutations of what's left, and stick # characters on each end of the generated permutations. Note that it's quite likely that you'll still have far too many permutations to ever go through.

By the way, you don't need to write your own permutation generator. The standard library provides itertools.permutations, which is substantially faster than your code and doesn't have a few of the bugs your code does.

import itertools
def hash_on_each_end_permutations(array):
    array = list(array)
    array.remove('#')
    array.remove('#')
    for subpermutation in itertools.permutations(array):
        yield '#' + ''.join(subpermutation) + '#'