Shuffle all the letters in the string in all possible variations

Question

Shuffle all the letters in the string in all possible variations

The user enters a string, you need to mix the letters in it in all possible variations and display them in the list, and remove duplicates, if there are any, for example:

('a');  ['a']

('ab');  ['ab', 'ba']

('aabb');  ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']

I wrote this code, but it only works with a small string length, and with a large one, the answers do not match the desired ones.

import math
import random
def permutations(string):
    lst=[]
    for i in range(0,math.factorial(len(string))):
        lst.append(''.join(random.sample(string,len(string))))
    asm=set()
    for i in lst:
        asm.add(''.join(i))
    return sorted(asm)

Please explain the solution to the problem, the question is taken from here: https://www.codewars.com/kata/5254ca2719453dcc0b00027d/train/python

1

алгоритм python функции случайные-числа

Author: MarianD, 2020-04-16

Source

1 answers

score 0 · Accepted Answer

I offer two options:

1) Using the itertools module.

from itertools import permutations as perm

def permutations(string):
    return list(''.join(tup) for tup in set(perm(string)))

2) Recursive.

def perm(string, accum):
    if len(string) == 0:
        return [accum]  

    res = []
    for i, letter in enumerate(string):
        res += perm(string[:i] + string[i + 1:], accum + letter)

    return res

def permutations(string):
    return list(set(perm(string, '')))

Explanation

We have a set of three letters abc. We begin to collect all possible permutations:

The first letter can be any of the set, respectively, the string can have three different beginnings: a, b, c. When selecting a letter, we must remove it from the set, since it is already used.
The second letter is selected from the remaining ones in the set, in this case there are two of them. Add it to an existing row (battery) and remove it from the set.
The third letter automatically goes to the battery, as the last one in the set.

'a', в наборе остаётся 'bc'.
    'ab' в наборе остаётся 'c'
        'abc', набор пустой
    'ac' в наборе остаётся 'b'
        'acb', набор пустой

'b', в наборе остаётся 'ac'.
    'ba' в наборе остаётся 'c'
        'bac', набор пустой
    'bc' в наборе остаётся 'a'
        'bca', набор пустой     

'c', в наборе остаётся 'ab'.
    'ca' в наборе остаётся 'b'
        'cab', набор пустой
    'cb' в наборе остаётся 'a'
        'cba', набор пустой

To remove duplicates, we run all the resulting permutations through set() .