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

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

x='stack'

мне нужен такой список,

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

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

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

itertools.permutations (iterable [, r])

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

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

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

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

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

['стек', '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()конструктора.

Вы можете получить все 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)

Вот еще один способ сделать перестановку строки с минимальным кодом. Мы в основном создаем цикл, а затем продолжаем менять местами два символа за раз. Внутри цикла у нас будет рекурсия. Обратите внимание, мы печатаем только тогда, когда индексаторы достигают длины нашей строки. Пример: ABC i для нашей начальной точки и наш параметр рекурсии 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)

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

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

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, "", 1))]
    return permutation_list

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

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)

Вот еще один подход, отличный от того, что опубликовали @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 секунды для версий @ Adriano и @illerucis. Конечно, вы все еще можете его оптимизировать.

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

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

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]

def permute(seq):
    if not seq:
        yield seq
    else:
        for i in range(len(seq)):
            rest = seq[:i]+seq[i+1:]
            for x in permute(rest):
                yield seq[i:i+1]+x

print(list(permute('stack')))

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

Вот немного улучшенная версия кода 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

Еще одно инициативное и рекурсивное решение. Идея состоит в том, чтобы выбрать букву в качестве точки поворота, а затем создать слово.

# for a string with length n, there is a factorial n! permutations
alphabet = 'abc'
starting_perm = ''
# with recursion
def premuate(perm, alphabet):
    if not alphabet: # we created one word by using all letters in the alphabet
        print(perm + alphabet)
    else:
        for i in range(len(alphabet)): # iterate over all letters in the alphabet
            premuate(perm + alphabet[i], alphabet[0:i] + alphabet[i+1:]) # chose one letter from the alphabet

# call it            
premuate(starting_perm, alphabet)

Выход:

abc
acb
bac
bca
cab
cba

Вот действительно простая версия генератора:

def find_all_permutations(s, curr=[]):
    if len(s) == 0:
        yield curr
    else:
        for i, c in enumerate(s):
            for combo in find_all_permutations(s[:i]+s[i+1:], curr + [c]):
                yield "".join(combo)

Думаю, это не так уж и плохо!

def f(s):
  if len(s) == 2:
    X = [s, (s[1] + s[0])]
      return X
else:
    list1 = []
    for i in range(0, len(s)):
        Y = f(s[0:i] + s[i+1: len(s)])
        for j in Y:
            list1.append(s[i] + j)
    return list1
s = raw_input()
z = f(s)
print z

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

perms = [''.join(p) for p in permutations('stack')]

def perm(string):
   res=[]
   for j in range(0,len(string)):
       if(len(string)>1):
           for i in perm(string[1:]):
               res.append(string[0]+i)
       else:
           return [string];
       string=string[1:]+string[0];
   return res;
l=set(perm("abcde"))

Это один из способов генерации перестановок с рекурсией, вы можете легко понять код, взяв в качестве входных строки строки 'a', 'ab' и 'abc'.

Вы получите все N! перестановки с этим, без дубликатов.

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

def get_permutations(word):
    if len(word) == 1:
        yield word

    for i, letter in enumerate(word):
        for perm in get_permutations(word[:i] + word[i+1:]):
            yield letter + perm

Эта программа не устраняет дубликаты, но я думаю, что это один из самых эффективных подходов:

s=raw_input("Enter a string: ")
print "Permutations :\n",s
size=len(s)
lis=list(range(0,size))
while(True):
    k=-1
    while(k>-size and lis[k-1]>lis[k]):
        k-=1
    if k>-size:
        p=sorted(lis[k-1:])
        e=p[p.index(lis[k-1])+1]
        lis.insert(k-1,'A')
        lis.remove(e)
        lis[lis.index('A')]=e
        lis[k:]=sorted(lis[k:])
        list2=[]
        for k in lis:
                list2.append(s[k])
        print "".join(list2)
    else:
                break

def permute_all_chars(list, begin, end):

    if (begin == end):
        print(list)
        return

    for current_position in range(begin, end + 1):
        list[begin], list[current_position] = list[current_position], list[begin]
        permute_all_chars(list, begin + 1, end)
        list[begin], list[current_position] = list[current_position], list[begin]


given_str = 'ABC'
list = []
for char in given_str:
    list.append(char)
permute_all_chars(list, 0, len(list) -1)

Более простое решение с использованием перестановок.

from itertools import permutations

def stringPermutate(s1):
    length=len(s1)
    if length < 2:
        return s1

    perm = [''.join(p) for p in permutations(s1)]

    return set(perm)

Все возможные слова со стеком

from itertools import permutations
for i in permutations('stack'):
    print(''.join(i))

permutations(iterable, r=None)

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

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

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

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

Это рекурсивное решение, n!позволяющее принимать повторяющиеся элементы в строке

import math

def getFactors(root,num):
    sol = []
    # return condition
    if len(num) == 1:
            return [root+num]
    # looping in next iteration
    for i in range(len(num)):  
        # Creating a substring with all remaining char but the taken in this iteration
        if i > 0:
            rem = num[:i]+num[i+1:]
        else:
            rem = num[i+1:]
        # Concatenating existing solutions with the solution of this iteration
        sol = sol + getFactors(root + num[i], rem)
    return sol

Я проверил решение с учетом двух элементов, количество комбинаций равно n!и результат не может содержать дубликатов. Так:

inpt = "1234"
results = getFactors("",inpt)

if len(results) == math.factorial(len(inpt)) | len(results) != len(set(results)):
    print("Wrong approach")
else:
    print("Correct Approach")

Вот простая и понятная рекурсивная реализация;

def stringPermutations(s):
    if len(s) < 2:
        yield s
        return
    for pos in range(0, len(s)):
        char = s[pos]
        permForRemaining = list(stringPermutations(s[0:pos] + s[pos+1:]))
        for perm in permForRemaining:
            yield char + perm

С рекурсией

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# recursive function 
def _permute(p, s, permutes):
    if p >= len(s) - 1:
        permutes.append(s)
        return

    for i in range(p, len(s)):
        _permute(p + 1, swap(s, p, i), permutes)


# helper function
def permute(s):
    permutes = []
    _permute(0, s, permutes)
    return permutes


# TEST IT
s = "1234"
all_permute = permute(s)
print(all_permute)

С итерационным подходом (с использованием стека)

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# iterative function
def permute_using_stack(s):
    stk = [(0, s)]

    permutes = []

    while len(stk) > 0:
        p, s = stk.pop(0)

        if p >= len(s) - 1:
            permutes.append(s)
            continue

        for i in range(p, len(s)):
            stk.append((p + 1, swap(s, p, i)))

    return permutes


# TEST IT
s = "1234"
all_permute = permute_using_stack(s)
print(all_permute)

С лексикографически отсортированными

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# finds next lexicographic string if exist otherwise returns -1
def next_lexicographical(s):
    for i in range(len(s) - 2, -1, -1):
        if s[i] < s[i + 1]:
            m = s[i + 1]
            swap_pos = i + 1

            for j in range(i + 1, len(s)):
                if m > s[j] > s[i]:
                    m = s[j]
                    swap_pos = j

            if swap_pos != -1:
                s = swap(s, i, swap_pos)
                s = s[:i + 1] + ''.join(sorted(s[i + 1:]))
                return s

    return -1


# helper function
def permute_lexicographically(s):
    s = ''.join(sorted(s))
    permutes = []
    while True:
        permutes.append(s)
        s = next_lexicographical(s)
        if s == -1:
            break
    return permutes


# TEST IT
s = "1234"
all_permute = permute_lexicographically(s)
print(all_permute)