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

Ответ 1

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

itertools.permutations(iterable [, r])

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

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

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

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

>>> 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", "actsk", "actks", "ackst", "ackts", "akstc", "aksct", "aktsc", "aktcs", "akcst", "akcts", "cstak", "cstka", "csatk", "csakt", "cskta", "cskat", "ctsak", "ctska", "ctask", "ctaks", "ctksa", "ctkas", "каст", "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().

Ответ 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 index will begin with step + 1)
        permutations(string_copy, step + 1)

Ответ 3

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

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

permutations = char + перестановки (строка - 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

Ответ 4

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

Ответ 5

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

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)

Ответ 6

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

Ответ 7

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

Ответ 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]

Ответ 9

Смотрите itertools.combinations или itertools.permutations.

Ответ 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

Ответ 11

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

Ответ 12

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

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)

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

Ответ 13

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

Ответ 14

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

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

Ответ 15

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! перестановки с этим, без дубликатов.

Ответ 16

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

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

Ответ 17

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

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

Ответ 18

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)

Ответ 19

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

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)

Ответ 20

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

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