Finden aller möglichen Permutationen einer bestimmten Zeichenfolge in Python

Ich habe eine Schnur. Ich möchte alle Permutationen aus dieser Zeichenfolge generieren, indem ich die Reihenfolge der Zeichen darin ändere. Sagen Sie zum Beispiel:

x='stack'

Was ich will, ist eine Liste wie diese,

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

Momentan iteriere ich in der Liste der Zeichenfolgen, wähle 2 Buchstaben zufällig aus und transponiere sie, um eine neue Zeichenfolge zu bilden, und füge sie hinzu, um die Besetzung von l festzulegen. Basierend auf der Länge der Zeichenfolge berechne ich die Anzahl der möglichen Permutationen und setze die Iterationen fort, bis die eingestellte Größe die Grenze erreicht. Es muss einen besseren Weg geben, dies zu tun.

Das itertools-Modul verfügt über eine nützliche Methode namens permutations (). Die Dokumentation sagt:

itertools.permutations (iterable [, r])

Gibt aufeinanderfolgende r-Längenpermutationen von Elementen in der Iterable zurück.

Wenn r nicht angegeben ist oder None ist, wird r standardmäßig auf die Länge der iterierbaren Datei gesetzt und alle möglichen Permutationen in voller Länge werden generiert.

Permutationen werden in lexikografischer Sortierreihenfolge ausgegeben. Wenn also die iterierbare Eingabe sortiert ist, werden die Permutationstupel in sortierter Reihenfolge erzeugt.

Sie müssen Ihre permutierten Buchstaben jedoch als Zeichenfolgen verbinden.

>>> 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 ',' cat ' , '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 ']

Wenn Sie Probleme mit Duplikaten haben, versuchen Sie, Ihre Daten in eine Struktur ohne Duplikate wie set:

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

Vielen Dank an @pst für den Hinweis, dass dies nicht das ist, was wir traditionell als Typumwandlung betrachten, sondern eher als Aufruf an den set()Konstruktor.

Sie können alle N bekommen! Permutationen ohne viel Code

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)

Hier ist eine andere Möglichkeit, die Permutation von Zeichenfolgen mit minimalem Code durchzuführen. Wir erstellen im Grunde eine Schleife und tauschen dann immer wieder zwei Zeichen gleichzeitig aus. Innerhalb der Schleife haben wir die Rekursion. Beachten Sie, dass wir nur drucken, wenn Indexer die Länge unserer Zeichenfolge erreichen. Beispiel: ABC i für unseren Startpunkt und unser Rekursionsparameter j für unsere Schleife

Hier ist eine visuelle Hilfe, wie es von links nach rechts von oben nach unten funktioniert (ist die Reihenfolge der Permutation)

der Code :

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)

Stack Overflow-Benutzer haben bereits einige starke Lösungen veröffentlicht, aber ich wollte noch eine andere Lösung zeigen. Dieses finde ich intuitiver

Die Idee ist, dass für eine gegebene Zeichenfolge: wir können durch den Algorithmus (Pseudocode) rekursieren:

permutations = char + permutations (string - char) für char in string

Ich hoffe es hilft jemandem!

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

Hier ist eine einfache Funktion, um eindeutige Permutationen zurückzugeben:

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)

Hier ist ein anderer Ansatz als bei @Adriano und @illerucis. Dies hat eine bessere Laufzeit, Sie können dies selbst überprüfen, indem Sie die Zeit messen:

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

Für eine beliebige Zeichenfolge "dadffddxcf" dauerte die Permutationsbibliothek 1,1336 Sekunden, für diese Implementierung 9,125 Sekunden und für die Version von @ Adriano und @illerucis 16,357 Sekunden. Natürlich können Sie es trotzdem optimieren.

itertools.permutationsist gut, aber es geht nicht gut mit Sequenzen um, die wiederholte Elemente enthalten. Dies liegt daran, dass es intern die Sequenzindizes permutiert und die Sequenzelementwerte nicht berücksichtigt.

Sicher, es ist möglich, die Ausgabe itertools.permutationsdurch einen Satz zu filtern , um die Duplikate zu eliminieren, aber es verschwendet immer noch Zeit, diese Duplikate zu generieren, und wenn die Basissequenz mehrere wiederholte Elemente enthält, gibt es viele Duplikate. Die Verwendung einer Sammlung zum Speichern der Ergebnisse verschwendet außerdem RAM, wodurch der Vorteil der Verwendung eines Iterators in erster Linie zunichte gemacht wird.

Glücklicherweise gibt es effizientere Ansätze. Der folgende Code verwendet den Algorithmus des indischen Mathematikers Narayana Pandita aus dem 14. Jahrhundert, der im Wikipedia-Artikel über Permutation zu finden ist . Dieser alte Algorithmus ist immer noch eine der schnellsten bekannten Methoden, um Permutationen in der richtigen Reihenfolge zu generieren, und er ist ziemlich robust, da er Permutationen, die wiederholte Elemente enthalten, ordnungsgemäß verarbeitet.

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)

Ausgabe

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

Wenn Sie die erhaltenen Zeichenfolgen in einer Liste sammeln möchten, können Sie dies natürlich tun

list(lexico_permute_string('data'))

oder in neueren Python-Versionen:

[*lexico_permute_string('data')]

warum machst du nicht einfach:

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))

Sie erhalten kein Duplikat, wie Sie sehen können:

 ['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]

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')))

Siehe itertools.combinationsoder itertools.permutations.

Hier ist eine leicht verbesserte Version von illerucis 'Code zum Zurückgeben einer Liste aller Permutationen einer Zeichenfolge smit unterschiedlichen Zeichen (nicht unbedingt in lexikografischer Sortierreihenfolge), ohne itertools zu verwenden:

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

Hier ist eine wirklich einfache Generatorversion:

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)

Ich denke es ist nicht so schlimm!

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

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

perms = [''.join(p) for p in permutations('stack')]

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"))

Dies ist eine Möglichkeit, Permutationen mit Rekursion zu generieren. Sie können den Code leicht verstehen, indem Sie die Zeichenfolgen 'a', 'ab' und 'abc' als Eingabe verwenden.

Du bekommst alle N! Permutationen damit, ohne Duplikate.

Jeder liebt den Geruch seines eigenen Codes. Ich teile nur die, die ich am einfachsten finde:

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

Dieses Programm beseitigt die Duplikate nicht, aber ich denke, es ist einer der effizientesten Ansätze:

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

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)

Einfachere Lösung mit Permutationen.

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)

Noch eine Initiative und rekursive Lösung. Die Idee ist, einen Buchstaben als Drehpunkt auszuwählen und dann ein Wort zu erstellen.

# 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)

Ausgabe:

abc
acb
bac
bca
cab
cba

Alles mögliche Wort mit Stapel

from itertools import permutations
for i in permutations('stack'):
    print(''.join(i))

permutations(iterable, r=None)

Gibt aufeinanderfolgende r-Längenpermutationen von Elementen in der Iterable zurück.

Wenn r nicht angegeben ist oder None ist, wird r standardmäßig auf die Länge der iterierbaren Datei gesetzt und alle möglichen Permutationen in voller Länge werden generiert.

Permutationen werden in lexikografischer Sortierreihenfolge ausgegeben. Wenn also die iterierbare Eingabe sortiert ist, werden die Permutationstupel in sortierter Reihenfolge erzeugt.

Elemente werden aufgrund ihrer Position und nicht aufgrund ihres Werts als eindeutig behandelt. Wenn die Eingabeelemente eindeutig sind, gibt es in jeder Permutation keine Wiederholungswerte.

Dies ist eine rekursive Lösung, mit n!der doppelte Elemente in der Zeichenfolge akzeptiert werden

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

Ich habe die Lösung unter Berücksichtigung von zwei Elementen validiert, die Anzahl der Kombinationen ist n!und das Ergebnis darf keine Duplikate enthalten. So:

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

if len(results) == math.factorial(len(inpt)) | len(results) != len(set(results)):
    print("Wrong approach")
else:
    print("Correct Approach")

Hier ist eine einfache und unkomplizierte rekursive Implementierung.

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

Mit Rekursion

# 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)

Mit iterativem Ansatz (Using Stack)

# 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)

Mit lexikographisch sortiert

# 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)