在python中查找给定字符串的所有可能排列

Question

我有一个字符串.我想通过改变字符串中的字符顺序从该字符串生成所有排列.例如,说:

x='stack'

我想要的是这样的列表,

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

目前我正在迭代字符串的列表转换,随机挑选2个字母并转置它们以形成一个新字符串,并将其添加到l的设置转换.根据字符串的长度,我计算可能的排列数,并继续迭代,直到设置大小达到限制.必须有更好的方法来做到这一点.

Answer 1

itertools模块有一个名为permutations()的有用方法.文件说:

itertools.permutations(iterable [,r])

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

如果未指定r或为None,则r默认为iterable的长度,并生成所有可能的全长排列.

排列以字典排序顺序发出.因此,如果输入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',' 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()构造函数的调用.

Answer 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's index will begin with step + 1)
        permutations(string_copy, step + 1)

Answer 3

这是用最少的代码完成字符串置换的另一种方法。我们基本上创建了一个循环，然后每次都交换两个字符，在循环内，我们将进行递归操作。注意，我们仅在索引器达到字符串长度时才打印。示例：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)

Answer 4

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

当然，可以itertools.permutations通过一组过滤输出来消除重复项，但生成这些重复项仍然会浪费时间，并且如果基本序列中有多个重复元素，则会有大量重复项。此外，使用集合来保存结果会浪费 RAM，从而否定了使用迭代器的好处。

幸运的是，还有更有效的方法。下面的代码使用了 14 世纪印度数学家 Narayana Pandita 的算法，该算法可以在维基百科关于排列的文章中找到。这种古老的算法仍然是已知最快的按顺序生成排列的方法之一，并且它非常强大，因为它可以正确处理包含重复元素的排列。

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

Answer 5

堆栈溢出用户已经发布了一些强大的解决方案,但我想展示另一种解决方案.这个我发现更直观

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

permutations =字符串中char的char + permutations(string - 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

Answer 6

这是另一种不同于@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秒.当然你仍然可以优化它.

Answer 7

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

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)