Перемешать все буквы в строке во всех возможных вариацих

Question

Пользователь вводит строку, нужно перемешать буквы в ней во всех возможных вариациях и вывести их в списке, и удалить дубликаты, если они есть, например:

('a');  ['a']

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

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

я написал такой код, но он работает только при маленькой длине строки, а при большой ответы не совпадают с нужными.

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)

пожалуйста, объясните решение задачи, вопрос взял отсюда: https://www.codewars.com/kata/5254ca2719453dcc0b00027d/train/python

Answer 1

Предлагаю два варианта:

1) С помощью модуля itertools.

from itertools import permutations as perm

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

2) Рекурсивный.

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, '')))

Объяснение

Имеем набор из трёх букв abc. Начинаем собирать все возможные перестановки:

Первой буквой может быть любая из набора, соответственно строка может иметь три разных начала: a, b, c. Выбирая какую-либо букву, мы должны удалить её из набора, так как она уже использована.
Вторую букву выбираем из оставшихся в наборе, в данном случае их две. Добавляем её к уже имеющейся строке (аккумулятору) и удаляем её из набора.
Третья буква автоматом идёт в аккумулятор, так как последняя в наборе.

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

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

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

Для удаления дубликатов все полученные перестановки прогоняем через set() .

БЛОГ НА HUSL

Перемешать все буквы в строке во всех возможных вариацих

Ответы (1 шт):