在python中查找给定string的所有可能的排列
我有一个string。 我想通过改变字符的顺序来从string中产生所有的排列。 例如，说：
x='stack' 我想要的是这样一个列表，
l=['stack','satck','sackt'.......]
目前，我正在迭代string的列表转换，随机选取2个字母，并将它们转换为一个新的string，并添加它以设置l的转换。 根据string的长度，我正在计算可能的排列数，并继续迭代，直到设置的大小达到极限。 必须有更好的方法来做到这一点。
itertools模块有一个有用的方法叫做permutations（）。 该文件说：
itertools.permutations（iterable [，r]）
返回迭代中元素的连续r长度排列。
如果r没有被指定或者是None，那么r默认为可迭代的长度，并且产生所有可能的全长排列。
排列按词典sorting顺序排列。 所以，如果input迭代被sorting，排列元组将按sorting顺序产生。
你将不得不join你排列的字母作为string。
>>> 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， tkska'，'tcask'，'tcaks'，'tcksa'，'tckas'，'tksac'，'tksca'，'tkasc'，'tkacs'，'tkcsa'，'tkcas'，'astck'，'astkc' ，askk，asckt，asktc，askct，atsck，atskc，atcsk，atksc，atkcs，acstk，acskt， actk'，actks，ackst，ackts，akstc，aksct，aktsc，aktcs，akcst，akcts，cstak，cstka，csatk， ，cskak，cskak，ctsak，ctska，ctask，ctaks，ctksa，ctkas，castk，caskt， 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']
如果您发现自己对重复项目感到困扰，请尝试将数据合并到没有重复项目的结构中：
>>> perms = [''.join(p) for p in permutations('stacks')] >>> len(perms) 720 >>> len(set(perms)) 360
感谢@pst指出，这不是我们传统上认为的types转换，而是更多的对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)
这是另一种不同于@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
对于任意string“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)): revursive_perms.append(c+perm) return set(revursive_perms)
itertools.permutations是好的，但它不能很好地处理包含重复元素的序列。 这是因为它在内部会对序列索引进行置换，而对序列项值不知情。
当然，可以通过set来过滤itertools.permutations的输出以消除重复，但是仍然会浪费时间来生成这些重复，并且如果基本序列中有多个重复的元素，将会有很多重复项。 另外，使用集合来保存结果会浪费RAM，从而否定使用迭代器的好处。
幸运的是，有更有效的方法。 下面的代码使用了14世纪的印度math家Narayana Pandita的algorithm，可以在维基百科关于排列的文章中find。 这个古老的algorithm仍然是按照顺序生成排列的最快的已知方法之一，并且它是相当健壮的，因为它正确地处理了包含重复元素的排列。
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
当然，如果你想把收集的string收集到列表中，你可以做
list(lexico_permute_string('data'))
或者在最近的Python版本中：
[*lexico_permute_string('data')]
请参阅itertools.combinations或itertools.permutations 。
这里有一个稍微改进的illerucis版本的代码，用于返回不同字符（不一定按字典顺序sorting）的strings的所有排列列表，而不使用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
你为什么不简单呢：
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]
堆栈溢出用户已经发布了一些强大的解决scheme，但我想显示另一个解决scheme。 这个我觉得更直观
这个想法是，对于给定的string：我们可以通过algorithmrecursion（伪代码）：
permutations = char + permutations（string – 字符）string中的字符
希望它可以帮助别人！
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
这是一个非常简单的生成器版本：
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 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"))
这是recursion生成排列的一种方法，通过将string'a'，'ab'和'abc'作为input，您可以轻松理解代码。
你得到所有的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
这是一个简单而直接的recursion实现;
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
