Trouble with recursion in list

Question

Write a function word_permutations_dict() that takes a string as input and returns a dictionary where the keys are every word in the input string, and the values are lists containing strings of every permutation of letters of that word.
I have to use recursion here. Heres my code i have tried to caste my list into a set but get an unhashable list error. Any input would be greatly appreciated.

test_string = 'moths are insect teddy bears'


def word_permutations_dict(input_string):
    s2 = input_string.split(' ')
    d = {}
    v = set()
    for w in s2:
        listtemp = list(w)
        v = perms(len(listtemp), listtemp)
        d[w] = v
    return d


def perms(start, list1):
    if start == 1:
        list1.append(list1)
    else:
        for i in range(start - 1):
            perms(start - 1, list1)
            if i % 2 == 1:
                list1[0], list1[start - 1] = list1[start - 1], list1[0]
            else:
                list1[i], list1[start - 1] = list1[start - 1], list1[i]
        perms(start - 1, list1)

    return list1


perms_dict = word_permutations_dict(test_string)

for k, v in perms_dict.items():
    print('{} : {} permutations'.format(k, len(v)))

output:

moths : 125 permutations
are : 9 permutations
insect : 726 permutations
teddy : 125 permutations
bears : 125 permutations

expected:

moths : 120 permutations
are : 6 permutations
insect : 720 permutations
teddy : 60 permutations
bears : 120 permutations

Please format the code: select it and type `ctrl-k`. ... [Formatting help](https://stackoverflow.com/help/formatting) ... [more Formatting](https://stackoverflow.com/editing-help) ... [Formatting sandbox](https://meta.stackexchange.com/questions/3122/formatting-sandbox) — wwii, Nov 18 '19 at 19:50
When posting a question about code that produces an Exception, always include the complete Traceback - copy and paste it then format it as code (select it and type `ctrl-k`) — wwii, Nov 18 '19 at 19:51
Please edit the question to explain specifically what problem you are trying to solve, and explain your expected output. Also, why is this question tagged both `python-3.x` and `python-2.7`? And how are you getting your output if your code throws an error? — kaya3, Nov 18 '19 at 19:52
Please fix the indentation in `word_permutations_dict` starting at `d = {}`. — wwii, Nov 18 '19 at 20:03
Related: [Finding all possible permutations of a given string in python](Finding all possible permutations of a given string in python) ... [How to generate all permutations of a list in Python](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python) ... — wwii, Nov 18 '19 at 20:08
I am guessing this is for hw, interview, or practice but in the off chance that it isn't I recommend using [itertools permutation](https://docs.python.org/3/library/itertools.html#itertools.permutations). Its a built-in, just use `from itertools import permutations`. — Error - Syntactical Remorse, Nov 18 '19 at 20:08
For an interview, definitely don't use `itertools.permutations` - the problem is only to count the number of permutations, not generate them all; generating them all is O(n!). To count the number of permutations, use `collections.Counter` to count distinct elements, then do something like `factorial(n) / product(factorial(i) for i in counts.values())` where `product` multiplies the numbers together. This way it's O(n). — kaya3, Nov 18 '19 at 22:14

Chris Charley · Answer 1 · 2019-11-18T20:36:03.240

1

Some words with repeated letters is a multiset. The answer may be:

from collections import Counter
import math

test_string = 'moths are insect teddy bears'

for word in test_string.split():
    v = Counter(word).values()
    result = math.factorial(len(word))
    for count in v:
        result /= math.factorial(count)
    print(word, ':', result)

Output:

moths : 120.0
are : 6.0
insect : 720.0
teddy : 60.0
bears : 120.0

edited Nov 18 '19 at 20:36

answered Nov 18 '19 at 20:25

Chris Charley

6,403
2
24
26

This is the best solution because it's O(n). There is no need to generate all O(n!) permutations if you just want to count them. – kaya3 Nov 18 '19 at 22:17

score 1 · Accepted Answer · answered Nov 18 '19 at 21:17

First of all, you should name your variables better. For the sake of the code reader and yourself. It gets really confusing when you use single letters and all-lowercase names without an underscore.

You are calculating the permutations wrong, that's why the output is incorrect.

Don't initialize v = set() as it will always be overridden by your

v = perms() function call

Just a sample:

def permute(input_string):
    perms = []

    if len(input_string) == 1:
        # if one char then return it
        perms = [input_string]

    for idx, letter in enumerate(input_string):
        for perm in permute(input_string[:idx] + input_string[idx + 1:]):
            perms += [letter + perm]
    return perms

print(len(permute("moths")))

thank you for the help i should have used enumerate from the start :) — reallyjosh4real, Nov 18 '19 at 21:35
If we have repeated characters in the string then we will get same strings under different permutations. If we don't remove them it will miscalculate the total count. — Ankit Mahajan, Nov 19 '19 at 06:38

score 0 · Answer 3 · answered Nov 18 '19 at 20:12

from itertools import permutations

def word_permutations_dict(input_string):
    s2 = input_string.split(' ')
        d = {}

        v = set()
        for w in s2:
            perms = [''.join(p) for p in permutations(w)]
            v=len(set(perms))    
            d[w] = v

    return d

removing your implementation of perms with the one python already provides.

Trouble with recursion in list

3 Answers3