Znajdowanie wszystkich możliwych permutacji danego ciągu w Pythonie

89

Mam sznurek. Chcę wygenerować wszystkie permutacje z tego ciągu, zmieniając kolejność znaków w nim. Na przykład powiedz:

x='stack'

chcę mieć taką listę,

l=['stack','satck','sackt'.......]

Obecnie wykonuję iterację na liście rzutowania ciągu, wybierając losowo 2 litery i transponując je do nowego ciągu i dodając go do zestawu rzutów l. Na podstawie długości łańcucha obliczam liczbę możliwych permutacji i kontynuuję iteracje, aż ustalony rozmiar osiągnie limit. Musi być lepszy sposób na zrobienie tego.

Nihar Sarangi
źródło

Odpowiedzi:

143

Moduł itertools ma przydatną metodę zwaną permutations (). Dokumentacja mówi:

itertools.permutations (iterowalne [, r])

Zwraca kolejne permutacje długości r elementów w iterowalnej.

Jeśli r nie jest określony lub ma wartość Brak, to r przyjmuje domyślnie długość elementu iterowalnego i generowane są wszystkie możliwe permutacje o pełnej długości.

Permutacje są emitowane w porządku leksykograficznym. Tak więc, jeśli iterowalne wejście jest posortowane, krotki permutacji zostaną utworzone w kolejności posortowanej.

Musisz jednak połączyć swoje permutowane litery jako ciągi znaków.

>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms

[„stack”, „stakc”, „stcak”, „stcka”, „stkac”, „stkca”, „satck”, „satkc”, „sactk”, „sackt”, „saktc”, „sakct”, „ sctak ”,„ sctka ”,„ scatk ”,„ scakt ”,„ sckta ”,„ sckat ”,„ sktac ”,„ sktca ”,„ skatc ”,„ skact ”,„ skcta ”,„ skcat ”,„ tsack ” , „tsakc”, „tscak”, „tscka”, „tskac”, „tskca”, „tasck”, „taskc”, „tacsk”, „tacks”, „taksc”, „takcs”, „tcsak”, „ tcska ”,„ tcask ”,„ tcaks ”,„ tcksa ”,„ tckas ”,„ tksac ”,„ tksca ”,„ tkasc ”,„ tkacs ”,„ tkcsa ”,„ tkcas ”,„ astck ”,„astkc ”,„ asctk ”,„ asckt ”,„ asktc ”,„ askct ”,„ atsck ”,„ atskc ”,„ atcsk ”,„ atcks ”,„ atksc ”,„ atkcs ”,„ acstk ”,„ acskt ” , „actsk”, „actks”, „ACKst”, „Ackts”, „akstc”, „aksct”, „aktsc”, „aktcs”, „akcst”, „akcts”, „cstak”, „cstka”, „ csatk ”,„ csakt ”,„ cskta ”,„ cskat ”,„ ctsak ”,„ ctska ”,„ ctask ”,„ ctaks ”,„ ctksa ”,„ ctkas ”,„ castk ”,„ caskt ”,„ catsk ” , „catks”, „cakst”, „cakts”, „cksta”, „cksat”, „cktsa”, „cktas”, „ckast”, „ckats”, „kstac”, „kstca”, „ksatc”,„ksact”, „kscta”, „kscat”, „ktsac”, „ktsca”, „ktasc”, „ktacs”, „ktcsa”, „ktcas”, „kastc”, „kasct”, „katsc”, „katcs „,„ kacst ”,„ kacts ”,„ kcsta ”,„ kcsat ”,„ kctsa ”,„ kctas ”,„ kcast ”,„ kcats ”]

Jeśli masz problem z duplikatami, spróbuj dopasować dane do struktury bez duplikatów, takich jak set:

>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360

Podziękowania dla @pst za wskazanie, że to nie jest to, co tradycyjnie myślelibyśmy o rzutowaniu typu, ale raczej o wywołaniu set()konstruktora.

tęsknota za maszyną
źródło
3
Nit: set(...)nie "rzuca". Raczej generuje (i zwraca) zbiór reprezentujący kolekcję wejściową: raz wygenerowany nie ma powiązania z kolekcją wejściową (i jest innym obiektem, a nie tylko innym widokiem).
@pst: Hmm, zwykle się nie zgadzam. Wiem u Ada lub Pascala, że ​​rzut jest po prostu nowym widokiem typu na tych samych bitach. Jednak przynajmniej z punktu widzenia języka C rzutowanie jest odpowiednim terminem niezależnie od tego, czy zmieniasz podstawową strukturę danych. Po prostu odnosi się do jawnej konwersji typu. Proszę, wyjaśnij moje nieporozumienie, jeśli możesz.
maszyna tęskni
1
Typowanie . Chociaż, jak zauważyłeś, może to być coś innego niż zwykły pogląd, lubię starać się oddzielić koncepcje, aby uniknąć nieporozumień. Powinienem był wyraźnie wspomnieć o „przymusie” w moim pierwszym komentarzu, chociaż rozważałbym po prostu ustawienie funkcji: lista -> zestaw.
1
Ja go zobaczyć, booljest to funkcja, która ocenia do bool (prawda / fałsz) w zależności od sygnału wejściowego. Uważam, że użycie słowa „cast” jest fałszywe i wprowadzające w błąd ...
1
Jako interesująca aktualizacja, dokumentacja została od tamtego czasu zmieniona, mówiąc : Wbudowana funkcja bool () może być używana do konwersji dowolnej wartości na wartość logiczną , a konkretnie do konwersji zamiast rzutowania. Stało się to w kolejnym wydaniu tej dyskusji, co doprowadziło mnie do przekonania, że ​​ta dyskusja doprowadziła do zmiany w dokumentacji!
maszyna tęskni
45

Możesz zdobyć wszystkie N! permutacje bez dużej ilości kodu

def permutations(string, step = 0):

    # if we've gotten to the end, print the permutation
    if step == len(string):
        print "".join(string)

    # everything to the right of step has not been swapped yet
    for i in range(step, len(string)):

        # copy the string (store as array)
        string_copy = [character for character in string]

        # swap the current index with the step
        string_copy[step], string_copy[i] = string_copy[i], string_copy[step]

        # recurse on the portion of the string that has not been swapped yet (now it's index will begin with step + 1)
        permutations(string_copy, step + 1)
illerucis
źródło
niezłe. Działa idealnie
kishorer747
1
Po prostu nieznacznie go zmodyfikowałem, nie musimy zamieniać zmiennych, jeśli i == step
siraj
4
Środowisko wykonawcze wynosi O (n!), Ponieważ jest n! permutacje.
Aspen
Dlaczego używasz step == len(string)zamiast step == len(string) - 1?
tulians
Ponieważ wtedy ostatnie 2 elementy nigdy nie zostałyby zamienione. Wypróbuj „abc”, aż b i c zostaną zamienione.
Roman Riesen
14

Oto inny sposób przeprowadzania permutacji łańcucha przy minimalnym kodzie. Zasadniczo tworzymy pętlę, a następnie wymieniamy dwa znaki na raz. Wewnątrz pętli będziemy mieć rekursję. Zauważ, że drukujemy tylko wtedy, gdy indeksatory osiągną długość naszego ciągu. Przykład: ABC i jako punkt początkowy i parametr j rekursji dla naszej pętli

oto pomoc wizualna, jak to działa od lewej do prawej od góry do dołu (jest to kolejność permutacji)

wprowadź opis obrazu tutaj

kod :

def permute(data, i, length): 
    if i==length: 
        print(''.join(data) )
    else: 
        for j in range(i,length): 
            #swap
            data[i], data[j] = data[j], data[i] 
            permute(data, i+1, length) 
            data[i], data[j] = data[j], data[i]  


string = "ABC"
n = len(string) 
data = list(string) 
permute(data, 0, n)
grepit
źródło
5
Warto wspomnieć, że jest to podstawa paradygmatu bakcyla .
AruniRC
Więcej informacji, te same / podobne kody: geeksforgeeks.org/… Twój przykład bardziej mi się podoba z przykładem graficznym;)
CTS_AE
8

Użytkownicy Stack Overflow opublikowali już kilka mocnych rozwiązań, ale chciałem pokazać jeszcze inne. Ten uważam za bardziej intuicyjny

Chodzi o to, że dla danego ciągu: możemy powtórzyć algorytm (pseudokod):

permutacje = znak + permutacje (ciąg - znak) dla znaku w ciągu

Mam nadzieję, że to komuś pomoże!

def permutations(string):
    """
    Create all permutations of a string with non-repeating characters
    """
    permutation_list = []
    if len(string) == 1:
        return [string]
    else:
        for char in string:
            [permutation_list.append(char + a) for a in permutations(string.replace(char, "", 1))]
    return permutation_list
BushMinusZero
źródło
4
To nie zadziała w przypadkach, w których występują powtarzające się znaki (str.replace). Np .: rqqx
sanjay
Użyj: [permutation_list.append (char + a) for a in permutations (string.replace (char, "", 1))]
user3761855
7

Oto prosta funkcja zwracająca unikalne permutacje:

def permutations(string):
    if len(string) == 1:
        return string

    recursive_perms = []
    for c in string:
        for perm in permutations(string.replace(c,'',1)):
            revursive_perms.append(c+perm)

    return set(revursive_perms)
ArashkG
źródło
6
1. Masz literówkę: revursive_perms-> recursive_perms. 2. Oszczędziłoby to pamięć RAM i czas, gdyby recursive_permsbył to zestaw, a nie lista, którą konwertujesz na zestaw w instrukcji return. 3. Bardziej wydajne byłoby użycie cięcia ciągów znaków zamiast .replacekonstruowania argumentu do rekurencyjnego wywołania permutations. 4. Używanie stringjako nazwy zmiennej nie jest dobrym pomysłem, ponieważ zasłania to nazwę standardowego stringmodułu.
2:00 po południu
5

Oto inne podejście, różniące się od tego, co opublikowali @Adriano i @illerucis. Ma to lepszy czas działania, możesz to sprawdzić, mierząc czas:

def removeCharFromStr(str, index):
    endIndex = index if index == len(str) else index + 1
    return str[:index] + str[endIndex:]

# 'ab' -> a + 'b', b + 'a'
# 'abc' ->  a + bc, b + ac, c + ab
#           a + cb, b + ca, c + ba
def perm(str):
    if len(str) <= 1:
        return {str}
    permSet = set()
    for i, c in enumerate(str):
        newStr = removeCharFromStr(str, i)
        retSet = perm(newStr)
        for elem in retSet:
            permSet.add(c + elem)
    return permSet

W przypadku dowolnego ciągu znaków „dadffddxcf” zajęło to 1,1336 sek. Dla biblioteki permutacji, 9,125 sek. Dla tej implementacji i 16,357 sek. Dla wersji @ Adriano i @illerucis. Oczywiście nadal możesz to zoptymalizować.

Rooky
źródło
4

itertools.permutationsjest dobry, ale nie radzi sobie dobrze z sekwencjami zawierającymi powtarzające się elementy. Dzieje się tak, ponieważ wewnętrznie permutuje indeksy sekwencji i nie zwraca uwagi na wartości elementów sekwencji.

Jasne, możliwe jest przefiltrowanie wyjścia itertools.permutationsprzez zbiór w celu wyeliminowania duplikatów, ale nadal marnuje się czas na generowanie tych duplikatów, a jeśli w sekwencji podstawowej jest kilka powtarzających się elementów, będzie dużo duplikatów. Ponadto użycie kolekcji do przechowywania wyników marnuje pamięć RAM, co w pierwszej kolejności neguje korzyści płynące z używania iteratora.

Na szczęście istnieją bardziej wydajne podejścia. Poniższy kod wykorzystuje algorytm XIV-wiecznego indyjskiego matematyka Narayana Pandita, który można znaleźć w artykule Wikipedii na temat permutacji . Ten starożytny algorytm jest nadal jednym z najszybszych znanych sposobów generowania permutacji w kolejności i jest dość solidny, ponieważ prawidłowo obsługuje permutacje zawierające powtarzające się elementy.

def lexico_permute_string(s):
    ''' Generate all permutations in lexicographic order of string `s`

        This algorithm, due to Narayana Pandita, is from
        https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

        To produce the next permutation in lexicographic order of sequence `a`

        1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, 
        the permutation is the last permutation.
        2. Find the largest index k greater than j such that a[j] < a[k].
        3. Swap the value of a[j] with that of a[k].
        4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
    '''

    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)

        #1. Find the largest index j such that a[j] < a[j + 1]
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return

        #2. Find the largest index k greater than j such that a[j] < a[k]
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break

        #3. Swap the value of a[j] with that of a[k].
        a[j], a[k] = a[k], a[j]

        #4. Reverse the tail of the sequence
        a[j+1:] = a[j+1:][::-1]

for s in lexico_permute_string('data'):
    print(s)

wynik

aadt
aatd
adat
adta
atad
atda
daat
data
dtaa
taad
tada
tdaa

Oczywiście, jeśli chcesz zebrać otrzymane ciągi na listę, możesz to zrobić

list(lexico_permute_string('data'))

lub w ostatnich wersjach Pythona:

[*lexico_permute_string('data')]
PM 2Ring
źródło
Pięknie wyjaśnione.
lmao
2

dlaczego nie jesteś prosty:

from itertools import permutations
perms = [''.join(p) for p in permutations(['s','t','a','c','k'])]
print perms
print len(perms)
print len(set(perms))

nie otrzymujesz duplikatu, jak widzisz:

 ['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 
'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta',
 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 
'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 
'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 
'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 
'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 
'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 
'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 
'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 
'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 
'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 
'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 
'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']
    120
    120
    [Finished in 0.3s]
Vincenzo
źródło
4
Nie, zawsze otrzymujesz duplikaty (lub gorzej), jeśli masz dwie lub więcej takich samych liter. Tak było w przykładzie @ machineyearning, gdzie zamiast stosu użył słowa stosy . To znaczy: Twoje rozwiązanie działa tylko w przypadku słów zawierających unikalne znaki.
erik
2
def permute(seq):
    if not seq:
        yield seq
    else:
        for i in range(len(seq)):
            rest = seq[:i]+seq[i+1:]
            for x in permute(rest):
                yield seq[i:i+1]+x

print(list(permute('stack')))
Srivastava
źródło
2
Czy możesz wyjaśnić, dlaczego Twoje rozwiązanie jest lepsze niż te już dostarczone?
Noel Widmer
Nie powiedziałem, że moje rozwiązanie jest lepsze od innych. Właśnie podałem moje rozwiązanie, aby to zrobić.
Srivastava,
1

Widzieć itertools.combinations lub itertools.permutations.

Brian Cain
źródło
4
kombinacje nie mają znaczenia dla jego problemu. transponuje litery, co oznacza, że ​​porządek jest istotny, co oznacza tylko permutacje
tęsknota za maszyną
1

Oto nieco ulepszona wersja kodu illerucis do zwracania listy wszystkich permutacji łańcucha sz różnymi znakami (niekoniecznie w leksykograficznej kolejności sortowania), bez używania itertools:

def get_perms(s, i=0):
    """
    Returns a list of all (len(s) - i)! permutations t of s where t[:i] = s[:i].
    """
    # To avoid memory allocations for intermediate strings, use a list of chars.
    if isinstance(s, str):
        s = list(s)

    # Base Case: 0! = 1! = 1.
    # Store the only permutation as an immutable string, not a mutable list.
    if i >= len(s) - 1:
        return ["".join(s)]

    # Inductive Step: (len(s) - i)! = (len(s) - i) * (len(s) - i - 1)!
    # Swap in each suffix character to be at the beginning of the suffix.
    perms = get_perms(s, i + 1)
    for j in range(i + 1, len(s)):
        s[i], s[j] = s[j], s[i]
        perms.extend(get_perms(s, i + 1))
        s[i], s[j] = s[j], s[i]
    return perms
Adriano
źródło
1

Kolejna inicjatywa i rekurencyjne rozwiązanie. Chodzi o to, aby wybrać literę jako oś, a następnie utworzyć słowo.

# for a string with length n, there is a factorial n! permutations
alphabet = 'abc'
starting_perm = ''
# with recursion
def premuate(perm, alphabet):
    if not alphabet: # we created one word by using all letters in the alphabet
        print(perm + alphabet)
    else:
        for i in range(len(alphabet)): # iterate over all letters in the alphabet
            premuate(perm + alphabet[i], alphabet[0:i] + alphabet[i+1:]) # chose one letter from the alphabet

# call it            
premuate(starting_perm, alphabet)

Wynik:

abc
acb
bac
bca
cab
cba
Faroq AL-Tam
źródło
0

Oto naprawdę prosta wersja generatora:

def find_all_permutations(s, curr=[]):
    if len(s) == 0:
        yield curr
    else:
        for i, c in enumerate(s):
            for combo in find_all_permutations(s[:i]+s[i+1:], curr + [c]):
                yield "".join(combo)

Myślę, że nie jest tak źle!

Gritty Kitty
źródło
0
def f(s):
  if len(s) == 2:
    X = [s, (s[1] + s[0])]
      return X
else:
    list1 = []
    for i in range(0, len(s)):
        Y = f(s[0:i] + s[i+1: len(s)])
        for j in Y:
            list1.append(s[i] + j)
    return list1
s = raw_input()
z = f(s)
print z
Ritabrata Sanyal
źródło
spróbuj dodać jakiś opis.
Arun Vinoth
0
from itertools import permutations
perms = [''.join(p) for p in permutations('ABC')]

perms = [''.join(p) for p in permutations('stack')]
Satish Kumar
źródło
5
spróbuj dodać jakiś opis.
Arun Vinoth
0
def perm(string):
   res=[]
   for j in range(0,len(string)):
       if(len(string)>1):
           for i in perm(string[1:]):
               res.append(string[0]+i)
       else:
           return [string];
       string=string[1:]+string[0];
   return res;
l=set(perm("abcde"))

Jest to jeden ze sposobów generowania permutacji z rekurencją. Kod można łatwo zrozumieć, przyjmując ciągi „a”, „ab” i „abc” jako dane wejściowe.

Masz wszystkie N! permutacje z tym, bez duplikatów.

Jasser
źródło
0

Każdy kocha zapach własnego kodu. Po prostu dzielę się tym, który uważam za najprostszy:

def get_permutations(word):
    if len(word) == 1:
        yield word

    for i, letter in enumerate(word):
        for perm in get_permutations(word[:i] + word[i+1:]):
            yield letter + perm
r_2
źródło
0

Ten program nie eliminuje duplikatów, ale myślę, że jest to jedno z najbardziej wydajnych podejść:

s=raw_input("Enter a string: ")
print "Permutations :\n",s
size=len(s)
lis=list(range(0,size))
while(True):
    k=-1
    while(k>-size and lis[k-1]>lis[k]):
        k-=1
    if k>-size:
        p=sorted(lis[k-1:])
        e=p[p.index(lis[k-1])+1]
        lis.insert(k-1,'A')
        lis.remove(e)
        lis[lis.index('A')]=e
        lis[k:]=sorted(lis[k:])
        list2=[]
        for k in lis:
                list2.append(s[k])
        print "".join(list2)
    else:
                break
Nagaraju Chukkala
źródło
0
def permute_all_chars(list, begin, end):

    if (begin == end):
        print(list)
        return

    for current_position in range(begin, end + 1):
        list[begin], list[current_position] = list[current_position], list[begin]
        permute_all_chars(list, begin + 1, end)
        list[begin], list[current_position] = list[current_position], list[begin]


given_str = 'ABC'
list = []
for char in given_str:
    list.append(char)
permute_all_chars(list, 0, len(list) -1)
Chandra Sekhar Battini
źródło
spróbuj dodać jakiś opis.
Arun Vinoth
0

Prostsze rozwiązanie wykorzystujące permutacje.

from itertools import permutations

def stringPermutate(s1):
    length=len(s1)
    if length < 2:
        return s1

    perm = [''.join(p) for p in permutations(s1)]

    return set(perm)
Nelson Katale
źródło
0

Wszystkie możliwe słowa ze stosem

from itertools import permutations
for i in permutations('stack'):
    print(''.join(i))
permutations(iterable, r=None)

Zwraca kolejne permutacje długości r elementów w iterowalnej.

Jeśli r nie jest określony lub ma wartość Brak, to r przyjmuje domyślnie długość elementu iterowalnego i generowane są wszystkie możliwe permutacje o pełnej długości.

Permutacje są emitowane w porządku leksykograficznym. Tak więc, jeśli iterowalne wejście jest posortowane, krotki permutacji zostaną utworzone w kolejności posortowanej.

Elementy są traktowane jako niepowtarzalne na podstawie ich pozycji, a nie wartości. Więc jeśli elementy wejściowe są unikalne, w każdej permutacji nie będzie powtarzających się wartości.

CodePerfectPlus
źródło
0

Jest to rozwiązanie rekurencyjne, n!które akceptuje zduplikowane elementy w ciągu

import math

def getFactors(root,num):
    sol = []
    # return condition
    if len(num) == 1:
            return [root+num]
    # looping in next iteration
    for i in range(len(num)):  
        # Creating a substring with all remaining char but the taken in this iteration
        if i > 0:
            rem = num[:i]+num[i+1:]
        else:
            rem = num[i+1:]
        # Concatenating existing solutions with the solution of this iteration
        sol = sol + getFactors(root + num[i], rem)
    return sol

Rozwiązanie sprawdziłem biorąc pod uwagę dwa elementy, liczba kombinacji jest, n!a wynik nie może zawierać duplikatów. Więc:

inpt = "1234"
results = getFactors("",inpt)

if len(results) == math.factorial(len(inpt)) | len(results) != len(set(results)):
    print("Wrong approach")
else:
    print("Correct Approach")
Ignacio Alorre
źródło
-1

Oto prosta i nieskomplikowana rekurencyjna implementacja;

def stringPermutations(s):
    if len(s) < 2:
        yield s
        return
    for pos in range(0, len(s)):
        char = s[pos]
        permForRemaining = list(stringPermutations(s[0:pos] + s[pos+1:]))
        for perm in permForRemaining:
            yield char + perm
iBe
źródło
1
Powinieneś naprawić wcięcie. Nie ma potrzeby zapisywania wyników rekurencyjnego wywołania na stringPermutationsliście - możesz iterować bezpośrednio po nim, np for perm in stringPermutations(s[:pos] + s[pos+1:]):. Ponadto, można uprościć forpętlę używając enumeratezamiast range, i wyeliminować char = s[pos]zadanie: for pos, char in enumerate(s):.
2:00 po południu
-1

Z rekurencją

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# recursive function 
def _permute(p, s, permutes):
    if p >= len(s) - 1:
        permutes.append(s)
        return

    for i in range(p, len(s)):
        _permute(p + 1, swap(s, p, i), permutes)


# helper function
def permute(s):
    permutes = []
    _permute(0, s, permutes)
    return permutes


# TEST IT
s = "1234"
all_permute = permute(s)
print(all_permute)

Z podejściem iteracyjnym (przy użyciu stosu)

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# iterative function
def permute_using_stack(s):
    stk = [(0, s)]

    permutes = []

    while len(stk) > 0:
        p, s = stk.pop(0)

        if p >= len(s) - 1:
            permutes.append(s)
            continue

        for i in range(p, len(s)):
            stk.append((p + 1, swap(s, p, i)))

    return permutes


# TEST IT
s = "1234"
all_permute = permute_using_stack(s)
print(all_permute)

Z posortowaniem leksykograficznym

# swap ith and jth character of string
def swap(s, i, j):
    q = list(s)
    q[i], q[j] = q[j], q[i]
    return ''.join(q)


# finds next lexicographic string if exist otherwise returns -1
def next_lexicographical(s):
    for i in range(len(s) - 2, -1, -1):
        if s[i] < s[i + 1]:
            m = s[i + 1]
            swap_pos = i + 1

            for j in range(i + 1, len(s)):
                if m > s[j] > s[i]:
                    m = s[j]
                    swap_pos = j

            if swap_pos != -1:
                s = swap(s, i, swap_pos)
                s = s[:i + 1] + ''.join(sorted(s[i + 1:]))
                return s

    return -1


# helper function
def permute_lexicographically(s):
    s = ''.join(sorted(s))
    permutes = []
    while True:
        permutes.append(s)
        s = next_lexicographical(s)
        if s == -1:
            break
    return permutes


# TEST IT
s = "1234"
all_permute = permute_lexicographically(s)
print(all_permute)
bikram
źródło