【python】求一个字符串所有的排列？

题目:设计一个程序，当输入一个字符串时，要求输出这个字符串的所有排列。例如输入字符串abc，要求输出由字符串a，b，c所能排列出来的所有的字符串：abc，acb，bac，bca，cba，cab。

分析：递归法。以字符串abc为例子介绍对字符串进行全排列的方法。

（1）首先固定第一个字符a，然后对后面两个字符b与c进行全排列。

（2）交换第一个字符与后面的字符，即交换a与b，然后固定第一个字符b，接着对后面的两个字符a与c进行全排列。

（3）由于第（2）步交换了a和b破坏了字符串原来的顺序，因此，需要再次交换a和b使其恢复到原来的顺序，然后交换第一个字符和第三个字符（交换a和c），接着固定第一个字符c，对后面的两个字符a与b求全排列。

注：在使用递归方法求解的时候，需要注意以下两个问题：（1）逐渐缩小问题的规模，并且可以用同样的方法来求解子问题。（2）递归一定要有结束，否则会导致程序陷入死循环。

code：

# 交换字符数组下标为i和j对应的字符

def swap(str, i, j):

    temp = str[i]

    str[i] = str[j]

    str[j] = temp

# 对字符串中的字符串进行全排列

# str为待排序的字符串，start为待排序的子字符串的首字符下标

def Permutation(str, start):

    if str is None or len(str) < 0:

        return

    # 完成完全排列后输出当前排列的字符串

    if start == len(str) - 1:

        print("".join(str))

    else:

        i = start

        while i < len(str):

            # 交换start与i所在位置的字符

            swap(str, start, i)

            # 固定第一个字符，对剩余的字符进行全排列

            Permutation(str, start + 1)

            # 还原start与i所在位置的字符

            swap(str, start, i)

            i += 1

def Permutation_transe(s):

    str = list(s)

    Permutation(str, 0)

if __name__ == "__main__":

    s = 'abc'

    Permutation_transe(s)

程序运行结果：

abc

acb

bac

bca

cba

cab