Нахождение всех возможных перестановок данной строки в Python

Question

У меня есть строка. Я хочу сгенерировать все перестановки из этой строки, изменив порядок символов в ней. Например, скажите:

x='stack'

я хочу вот такой список,

l=['stack','satck','sackt'.......]

В настоящее время я выполняю итерацию в списке типов строки, выбирая 2 буквы случайным образом и транспонирую их, чтобы сформировать новую строку, и добавляю их в набор значений l. Основываясь на длине строки, я вычисляю количество возможных перестановок и продолжаю итерации, пока заданный размер не достигнет предела. Должен быть лучший способ сделать это.

Answer 1

Модуль itertools имеет полезный метод, называемый permutations (). В документации написано:

itertools.permutations (iterable [, r])

Вернуть последовательные перестановки длины r элементов в итерируемом.

Если r не указано или равно None, то по умолчанию r соответствует длине итерируемые и все возможные перестановки полной длины генерируются.

Перестановки выводятся в лексикографическом порядке сортировки. Итак, если вход итерируемый отсортирован, перестановочные кортежи будут производиться в отсортированном заказ.

Вы должны присоединить свои переставленные буквы в виде строк.

>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms

['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']

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

>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360

Спасибо @pst за то, что он указал, что это не то, о чем мы обычно думаем как приведение типов, а скорее вызов конструктора set().

Answer 2

Вы можете получить все N! перестановки без большого кода

def permutations(string, step = 0):

    # if we've gotten to the end, print the permutation
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):

        # copy the string (store as array)
        string_copy = [character for character in string]

        # swap the current index with the step
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]

        # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
        permutations(string_copy, step + 1)

Answer 3

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

Идея состоит в том, что для данной строки: мы можем выполнить рекурсивный алгоритм (псевдокод):

permutations = char + permutations (string- char) для char в строке

Надеюсь, это кому-нибудь поможет!

def permutations(string):
    """Create all permutations of a string with non-repeating characters
    """
    permutation_list = []
    if len(string) == 1:
        return [string]
    else:
        for char in string:
            [permutation_list.append(char + a) for a in permutations(string.replace(char, ""))]
    return permutation_list

Answer 4

Вот простая функция для возврата уникальных перестановок:

def permutations(string):
    if len(string) == 1:
        return string

    recursive_perms = []
    for c in string:
        for perm in permutations(string.replace(c,'',1)):
            revursive_perms.append(c+perm)

    return set(revursive_perms)

Answer 5

Вот другой подход, отличный от того, что опубликовали @Adriano и @illerucis.Это обеспечивает лучшее время выполнения, вы можете проверить это самостоятельно, измерив время:

def removeCharFromStr(str, index):
    endIndex = index if index == len(str) else index + 1
    return str[:index] + str[endIndex:]

# 'ab' -> a + 'b', b + 'a'
# 'abc' ->  a + bc, b + ac, c + ab
#           a + cb, b + ca, c + ba
def perm(str):
    if len(str) <= 1:
        return {str}
    permSet = set()
    for i, c in enumerate(str):
        newStr = removeCharFromStr(str, i)
        retSet = perm(newStr)
        for elem in retSet:
            permSet.add(c + elem)
    return permSet

Для произвольной строки "dadffddxcf" потребовалось 1,1336 секунды для библиотеки перестановок, 9,125 секунды для этой реализации и 16,357 секунды для@ Версия Адриано и @illerucis.Конечно, вы все еще можете оптимизировать его.

Answer 6

Вот еще один способ перестановки строки с минимальным кодом. Мы в основном создаем цикл, а затем продолжаем менять два символа за раз, Внутри цикла у нас будет рекурсия. Обратите внимание, мы печатаем только тогда, когда индексаторы достигают длины нашей строки. Пример: азбука я для нашей отправной точки и нашего параметра рекурсии J для нашего цикла

Вот визуальная справка, как это работает слева направо сверху вниз (это порядок перестановки)

код:

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)

Answer 7

itertools.permutations это хорошо, но это не очень хорошо с последовательностями, которые содержат повторяющиеся элементы. Это потому, что внутри он переставляет индексы последовательности и не обращает внимания на значения элементов последовательности.

Конечно, можно отфильтровать выходные данные itertools.permutations через набор, чтобы устранить дубликаты, но это все же тратит время на создание этих дубликатов, и если в базовой последовательности есть несколько повторяющихся элементов, то будет лотов дубликатов. Кроме того, использование коллекции для хранения результатов приводит к неэффективному использованию ОЗУ, что сводит на нет преимущества использования итератора.

К счастью, есть более эффективные подходы. В приведенном ниже коде используется алгоритм индийского математика 14-го века Нараяны Пандиты, который можно найти в статье Википедии о перестановке . Этот древний алгоритм по-прежнему является одним из самых быстрых известных способов генерации перестановок по порядку, и он достаточно надежен в том смысле, что он правильно обрабатывает перестановки, содержащие повторяющиеся элементы.

def lexico_permute_string(s):
    ''' Generate all permutations in lexicographic order of string `s`

        This algorithm, due to Narayana Pandita, is from
        https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

        To produce the next permutation in lexicographic order of sequence `a`

        1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
        the permutation is the last permutation.
        2. Find the largest index k greater than j such that a[j] < a[k].
        3. Swap the value of a[j] with that of a[k].
        4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
    '''

    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)

        #1. Find the largest index j such that a[j] < a[j + 1]
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return

        #2. Find the largest index k greater than j such that a[j] < a[k]
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break

        #3. Swap the value of a[j] with that of a[k].
        a[j], a[k] = a[k], a[j]

        #4. Reverse the tail of the sequence
        a[j+1:] = a[j+1:][::-1]

for s in lexico_permute_string('data'):
    print(s)

выход

aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa

Конечно, если вы хотите собрать полученные строки в список, вы можете сделать

list(lexico_permute_string('data'))

или в последних версиях Python:

[*lexico_permute_string('data')]

Answer 8

почему вы не просто делаете:

from itertools import permutations
perms = [''.join(p) for p in permutations(['s','t','a','c','k'])]
print perms
print len(perms)
print len(set(perms))

вы не получите дубликата, как видите:

 ['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 
'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta',
 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 
'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 
'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 
'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 
'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 
'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 
'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 
'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 
'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 
'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 
'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']
    120
    120
    [Finished in 0.3s]

Answer 9

См. itertools.combinations или itertools.permutations.

Answer 10

Вот немного улучшенная версия кода illerucis для возврата списка всех перестановок строки s с различными символами (необязательно в лексикографическом порядке сортировки) без использования itertools:

def get_perms(s, i=0):
    """
    Returns a list of all (len(s) - i)! permutations t of s where t[:i] = s[:i].
    """
    # To avoid memory allocations for intermediate strings, use a list of chars.
    if isinstance(s, str):
        s = list(s)

    # Base Case: 0! = 1! = 1.
    # Store the only permutation as an immutable string, not a mutable list.
    if i >= len(s) - 1:
        return ["".join(s)]

    # Inductive Step: (len(s) - i)! = (len(s) - i) * (len(s) - i - 1)!
    # Swap in each suffix character to be at the beginning of the suffix.
    perms = get_perms(s, i + 1)
    for j in range(i + 1, len(s)):
        s[i], s[j] = s[j], s[i]
        perms.extend(get_perms(s, i + 1))
        s[i], s[j] = s[j], s[i]
    return perms