Создание алгоритма кучи для вывода списка всех перестановок, в базовом питоне без других модулей - PullRequest
Новая
       31

Создание алгоритма кучи для вывода списка всех перестановок, в базовом питоне без других модулей

0 голосов
/ 20 июня 2019

Я пытаюсь построить алгоритм, который будет выводить список всех перестановок введенной строки, и я очень теряюсь, особенно когда дело доходит до алгоритма кучи.Я пытался скопировать код, указанный на странице Википедии, но безрезультатно.Я хочу решение в базе 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

1 Ответ

0 голосов
/ 20 июня 2019

Вы можете сделать это с помощью рекурсии.Здесь я собираюсь добавить код 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

Чтобы избавиться от этого, мы можем использовать список, и перед печатью мы будем искать наэтот список, существует ли этот элемент в списке или нет.Если его не существует, мы распечатаем его и сохраним в списке.

Программы: 

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/

...