Finding all possible permutations of a given string in python

I have a string. I want to generate all permutations from that string, by changing the order of characters in it. For example, say:

x='stack'

what I want is a list like this,

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

Currently I am iterating on the list cast of the string, picking 2 letters randomly and transposing them to form a new string, and adding it to set cast of l. Based on the length of the string, I am calculating the number of permutations possible and continuing iterations till set size reaches the limit. There must be a better way to do this.

233710 次浏览
小开

参见 itertools.combinations或 itertools.permutations。

小开
最佳答案

Itertools 模块有一个非常有用的方法，叫做置换():

排列(iterable [ ，r ])

返回迭代中元素的连续 r 长度排列。

如果没有指定 r 或者没有，则 r 默认为 生成可迭代的和所有可能的全长排列。

Permutations are emitted in lexicographic sort order. So, if the input 迭代被排序，置换元组将在排序中产生 秩序。

You'll have to join your permuted letters as strings though.

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

[‘ stack’，‘ stakc’，‘ stcak’，‘ stcka’，‘ stkac’，‘ stkca’，‘ satck’, ‘ satkc’，‘ sack’，‘ sack’，‘ saktc’，‘ sakct’，‘ sctak’，‘ sctka’, 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', “ skact”“ skcta”“ skcat”“ tsack”“ tsakc”“ tsak”“ tscka” “ tskac”“ tskca”“ taskc”“ taskc”“ tacks”“ tacks”“ taksc” ‘ takcs’，‘ tcsak’，‘ tcska’，‘ tcask’，‘ tcaks’，‘ tcksa’，‘ tckas’, ‘ tksac’，‘ tksca’，‘ tkasc’，‘ tkacs’，‘ tkcsa’，‘ tkcas’，‘ astck’, ‘ astkc’，‘ askk’，‘ askt’，‘ 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’，‘ kats’，‘ kstac’，‘ kstca’, ‘ ksatc’，‘ ksact’，‘ kscta’，‘ kscat’，‘ ktsac’，‘ ktsca’，‘ ktasc’, “ ktcsa”“ ktcas”“ kastc”“ kastc”“ katsc”“ katcs” “ kacst”，“ kacts”，“ kcsta”，“ kcsat”，“ kctsa”，“ kctas”，“ kcast”, “猫”]

如果你发现自己被重复数据所困扰，试着将你的数据放入一个没有重复数据的结构中，比如 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)
小开

Here's a slightly improved version of Ilerucis's code for returning a list of all permutations of a string s with distinct characters (not necessarily in lexicographic sort order), without using 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
小开

why do you not simple do:

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 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
小开

这里有另一种不同于@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秒。当然，您仍然可以对其进行优化。

小开

下面是一个返回唯一排列的简单函数:

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


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


return set(recursive_perms)
小开

Here's a really simple generator version:

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)

I think it's not so bad!

小开

itertools.permutations很好，但是它不能很好地处理包含重复元素的序列。这是因为它在内部对序列索引进行排列，并忽略了序列项的值。

当然，通过一个集合来过滤 itertools.permutations的输出以消除重复是可能的，但是生成这些重复仍然浪费时间，如果在基本序列中有几个重复的元素，就会有重复的 很多。而且，使用集合来保存结果会浪费 RAM，从而抵消了首先使用迭代器的好处。

Fortunately, there are more efficient approaches. The code below uses the algorithm of the 14th century Indian mathematician Narayana Pandita, which can be found in the 关于排列的维基百科文章. This ancient algorithm is still one of the fastest known ways to generate permutations in order, and it is quite robust, in that it properly handles permutations that contain repeated elements.

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')]
小开 
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 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')))
小开 
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! 排列与此，没有重复。

小开

Stack Overflow 用户已经发布了一些强大的解决方案，但我想展示另一个解决方案。我觉得这个更直观

其思想是，对于给定的字符串: 我们可以通过算法(伪代码)递归:

置换 = char + 置换(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
小开

Everyone loves the smell of their own code. Just sharing the one I find the simplest:

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
小开

This program does not eliminate the duplicates, but I think it is one of the most efficient approaches:

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
小开

下面是另一种基于 bactracking用最小代码对字符串进行排列的方法。 我们创建一个循环然后一次交换两个字符, 在循环中，我们将使用递归。注意，我们只在索引器达到字符串长度时才打印。 例如: ABC I 作为我们的起点和递归参数 J 代表我们的循环

这里是一个视觉帮助如何工作，从左到右从上到下(是排列顺序)

enter image description here

密码:

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)
小开 
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)
小开

Yet another initiative and recursive solution. The idea is to select a letter as a pivot and then create a word.

def find_premutations(alphabet):
    

words = []
word =''
    

def premute(new_word, alphabet):
if not alphabet:
words.append(word)
else:
for i in range(len(alphabet)):
premute(new_word=word + alphabet[i], alphabet=alphabet[0:i] + alphabet[i+1:])


premute(word, alphabet)
return words




# let us try it with 'abc'
a = 'abc'
find_premutations(a)

产出:

abc
acb
bac
bca
cab
cba
小开

用递归

# 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)
小开

堆栈中所有可能的单词

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

permutations(iterable, r=None)

返回迭代中元素的连续 r 长度排列。

如果没有指定 r 或者没有指定 r，则 r 默认为迭代器的长度，并且生成所有可能的全长排列。

排列是按照字典排序顺序发出的。因此，如果输入迭代被排序，置换元组将按排序顺序生成。

根据元素的位置，而不是根据它们的值，将元素视为唯一的。因此，如果输入元素是唯一的，那么在每个排列中将没有重复值。

小开

This is a recursive solution with n! which accepts duplicate elements in the string

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 permute(word):
if len(word) == 1:
return [word]
permutations = permute(word[1:])
character = word[0]
result = []
for p in permutations:
for i in range(len(p)+1):
result.append(p[:i] + character + p[i:])
return result








running code.


>>> permute('abc')
['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
小开

标准库中的 itertools模块对此有一个函数，简称为 permutations。

import itertools


def minion_game(s):
vow ="aeiou"
lsword=[]
ta=[]
for a in range(1,len(s)+1):
t=list(itertools.permutations(s,a))
lsword.append(t)


for i in range(0,len(lsword)):
for xa in lsword[i]:
if vow.startswith(xa):
ta.append("".join(xa))


print(ta)


minion_game("banana")
小开

这个代码对我来说有意义。其逻辑是循环遍历所有字符，提取 我字符，对其他元素执行排列，并在开头附加 我字符。

如果要求我手动获取字符串 ABC 的所有排列。我会从检查元素 A 的所有组合开始:

  • AB 型
  • 公元前

然后是元素 B 的所有组合:

  • B-AC
  • B CA

然后是元素 C 的所有组合:

  • C AB 型
  • C BA
def permute(s: str):
n = len(s)
if n == 1: return [s]
if n == 2:
return [s[0]+s[1], s[1]+s[0]]


permutations = []
for i in range(0, n):
current = s[i]
others = s[:i] + s[i+1:]


otherPermutations = permute(others)
for op in otherPermutations:
permutations.append(current + op)


return permutations

提交答案