时间戳

首页 > 解决方案 > 在没有其他模块的基础python中创建堆算法以输出所有排列的列表

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

问题描述

我正在尝试构建一种算法，该算法将输出输入字符串的所有排列列表，但我非常迷茫，尤其是在堆算法方面。我试图复制维基百科页面上列出的代码无济于事。我想要一个基础 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

标签： pythonpython-3.xlistfor-loopheapsort

解决方案

您可以通过使用递归来做到这一点。在这里，我将为您添加 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”包含两次。该程序的输出将是：

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

为了摆脱这种情况，我们可以使用一个列表，在打印之前，我们将在该列表上搜索该元素是否存在于列表中。如果不存在，那么我们将打印它并将其存储在列表中。

程式：

def heaps_func(a,size,listofwords):
    if size ==1:
        a = ''.join(a)
        #print(a)
        if listofwords.count(a)==0:
            print(a)
            listofwords.append(a)
        return
    for i in range(size):
        heaps_func(a,size-1,listofwords)
        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]

listofwords=[]
heaps_func(list('arr'),len('arr'),listofwords)

详情请阅读以下链接。但那里是用 C/C++ 描述的。

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

推荐阅读