Filter a Set for Matching String Permutations

Question

I am trying to use itertools.permutations() to return all the permutations of the string and return only the ones which are members of a set of words.

import itertools

def permutations_in_dict(string, words): 
    '''
    Parameters
    ----------
    string : {str}
    words : {set}

    Returns
    -------
    list : {list} of {str}    

    Example
    -------
    >>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
    ['act', 'cat']
    '''

My current solution works fine in terminal but somehow couldn't pass the test case...

return list(set([''.join(p) for p in itertools.permutations(string)]) & words)

Any help will be appreciated.

Answer 1

You can simply use collections.Counter() to compare the words to the string without creating all permutations (this explodes with length of string):

from collections import Counter

def permutations_in_dict(string, words):
    c = Counter(string)
    return [w for w in words if c == Counter(w)]

>>> permutations_in_dict('act', {'cat', 'rat', 'dog', 'act'})
['cat', 'act']

Note: sets are unordered so if you need a specific order you may need to sort the result, e.g. return sorted(...)