python - 如何在python中使用递归打印字符串的排序排列

Question

我想以排序的方式打印字符串的排列。并且我不允许使用 itertools，我必须使用递归。

这是我为此目的创建的代码，但它非常慢，因为 10 个字符需要 200 秒才能打印所有答案!我想让它更快地在 10 秒内完成。有帮助吗？

n = int(input()) # n is the number of characters

1 <= n <= 10

elements0 = str(input()) # it will be in this format : A B C D E F G

elements = elements0.split()

def translate(elements) :
    i = 0
    while i < n :
        elements[i] = int(i)
        i = i + 1
    return elements

elements = translate(elements)

def factor(elements,i):
    elements = elements[:]
    if i == len(elements) - 1:
        list.append(elements)
        return elements
    else:
        for j in range(i,len(elements)):
            elements[i], elements[j] = elements[j], elements[i]
            factor(elements, i + 1)
            elements[i], elements[j] = elements[j], elements[i]

list = []

factor(elements,0)

list = sorted(list)

def untranslate(list,n) :
    from math import factorial
    i = 0
    while i < factorial(n) :
        k = 0
        while k < n :
            if list[i][k] == 0 :
                list[i][k] = elements0[0]
            if list[i][k] == 1 :
                list[i][k] = elements0[2]
            if list[i][k] == 2 :
                list[i][k] = elements0[4]
            if list[i][k] == 3 :
                list[i][k] = elements0[6]
            if list[i][k] == 4 :
                list[i][k] = elements0[8]
            if list[i][k] == 5 :
                list[i][k] = elements0[10]
            if list[i][k] == 6 :
                list[i][k] = elements0[12]
            if list[i][k] == 7 :
                list[i][k] = elements0[14]
            if list[i][k] == 8 :
                list[i][k] = elements0[16]
            if list[i][k] == 9 :
                list[i][k] = elements0[18]
            k = k + 1
        i = i + 1
    return list

list = untranslate(list,n)



while True :
    if list == [] : break
    else:
        i=0
        row = str()
        while i < n :
            row = row + str(list[0][i])
            i = i + 1
        list.pop(0)

        print(row) # This should be in this format : ABCDEFG

还有一点:我想要排序的方式不是 A B C D ...(字母)。角色的值与它们在 elements0 中出现的一样。例如，如果 elements0 是 B A ，则必须打印 BA AB 。

Answer 1

好吧，既然这是家庭作业，我可以给你一个与你想要实现的略有不同的版本。

记住在递归中，你需要两件事:

1. 基本案例
2. 相信您的函数可以解决基本情况以外的所有问题。

这是代码

def getPermutations(string):
    if len(string) == 1: # Base Case
        return [string]
    else:                # Not base case
        result = []
        for i in range(len(string)):
            candidate = string[i]
            remaining = string[0:i] + string[i+1:]
            babies = getPermutations(remaining)  # Faith!
            for word in babies:
                result.append(candidate + word)
        return result

“ABCD”绝对不需要 200 秒。代码是自记录的，因此您应该能够弄清楚这里做了什么。

这是一个示例运行。

>>> myPerms = sorted( getPermutations("ABC") )
>>> for p in myPerms: print p
... 
ABC
ACB
BAC
BCA
CAB
CBA

请注意，如果字符串有重复的条目(例如“AABC”)，这将不起作用。祝你作业顺利!