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

Question

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

x='stack'

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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)

Answer 7

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

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)

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

Answer 8

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

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

Answer 9

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

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)

Answer 10

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