在没有其他模块的基础python中创建堆算法以输出所有排列的列表

Question

我正在尝试构建一个算法，它将输出一个输入字符串的所有排列的列表，我非常迷茫，尤其是在堆算法方面。我试图复制维基百科页面上列出的代码，但没有成功。我想要一个基于Python的解决方案。在

# Desired output
heaps_func('art')  
['rta', 'tra', 'tar', 'rat', 'art', 'atr']

# Current code
def heaps_func(a):
    lst=[a]
    l=len(a)
    if len(a)==1:
        return lst
    else:
        for x in range(len(a)-1):
            if x<(l-1):
                if l%2==0:
                    k=list(a)
                    p=k[i]
                    k[i]=k[l-1]
                    k[l-1]=p
                    k=''.join(k)
                    lst.append(k)
                else:
                    k=list(a)
                    p=k[0]
                    k[0]=k[l-1]
                    k[l-1]=p
                    k=''.join(k)
                    lst.append(k)

    return lst

Answer 1

你可以用递归来完成。这里我将为您添加python代码。在

def heaps_func(a,size):

    if size ==1:
        a = ''.join(a)
        print(a)
        return
    for i in range(size):
        heaps_func(a,size-1)
        if size%2==1:
            a[0],a[size-1]=a[size-1],a[0]
        else:
            a[i], a[size - 1] = a[size - 1], a[i]


heaps_func(list('art'),3)

如果给定的字符串包含重复的字符，此程序也将打印重复的元素。例如，在字符串“arr”中，“r”包含两次。该程序的输出将是：

arr rar rar arr rra rra

为了消除这个问题，我们可以使用一个列表，在打印之前，我们将在该列表中搜索该元素是否存在于列表中。如果不存在，我们将打印并存储在列表中。在

课程：

^{pr2}$

有关详细信息，请阅读以下链接。但是在C/C++中有这样的描述。在

https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/