Encontrar todas as permutações possíveis de uma determinada string em python

93

Eu tenho uma corda. Quero gerar todas as permutações dessa string, alterando a ordem dos caracteres nela. Por exemplo, diga:

x='stack'

o que eu quero é uma lista como esta,

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

Atualmente estou iterando no elenco de lista da string, escolhendo 2 letras aleatoriamente e transpondo-as para formar uma nova string e adicionando-a ao elenco de conjunto de l. Com base no comprimento da string, estou calculando o número de permutações possíveis e continuando as iterações até que o tamanho definido alcance o limite. Deve haver uma maneira melhor de fazer isso.

Nihar Sarangi
fonte

Respostas:

148

O módulo itertools tem um método útil chamado permutations (). A documentação diz:

itertools.permutations (iterable [, r])

Retorna sucessivas permutações de comprimento r de elementos no iterável.

Se r não for especificado ou for Nenhum, então o padrão de r será o comprimento do iterável e todas as permutações de comprimento total possíveis serão geradas.

As permutações são emitidas em ordem de classificação lexicográfica. Portanto, se o iterável de entrada for classificado, as tuplas de permutação serão produzidas em ordem classificada.

Você terá que juntar suas letras permutadas como strings.

>>> 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', 'tachas', '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 ' , 'actks', '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 ']

Se você tiver problemas com duplicatas, tente ajustar seus dados em uma estrutura sem duplicatas, como set:

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

Obrigado a @pst por apontar que isso não é o que tradicionalmente pensamos como um cast de tipo, mas mais como uma chamada para o set()construtor.

desejo de máquina
fonte
3
Nit: set(...)não "lança". Em vez disso, ele gera (e produz) o conjunto que representa a coleção de entrada: uma vez gerado, não tem nenhuma associação com a coleção de entrada (e é um objeto diferente, não apenas uma visão diferente).
@pst: Hmm, tenho tendência a discordar. Eu sei em Ada ou Pascal que um elenco é apenas um novo tipo de visão nas mesmas partes. No entanto, pelo menos de uma perspectiva C, o casting é um termo apropriado, independentemente de você estar mudando ou não a estrutura subjacente dos dados. Ele simplesmente se refere à conversão de tipo explícita. Por favor, explique meu mal-entendido, se puder.
máquina ansiando por
1
Typecasting . Embora, como você salientou, possa ser diferente de uma mera visão, gosto de tentar manter os conceitos separados para evitar confusão. Eu deveria ter mencionado "coerção" explicitamente em meu primeiro comentário, embora eu considerasse apenas definir uma função: lista -> definir.
1
Eu vejo isso, boolé uma função que avalia como um bool (True / False) dependendo da entrada. Acho que o uso de "elenco" aqui é espúrio e enganoso ...
1
Como uma atualização interessante, a documentação foi alterada para dizer A função embutida bool () pode ser usada para converter qualquer valor para um booleano , especificamente converter em vez de converter. Isso aconteceu no lançamento subsequente a esta discussão, levando-me a acreditar que essa discussão levou a uma mudança nos documentos!
máquina ansiando em
46

Você pode obter todos os N! permutações sem muito código

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
fonte
Agradável. Funciona perfeitamente
kishorer747
1
Eu apenas modifiquei ligeiramente, não precisamos trocar as variáveis ​​se i == step
work_in_progress
4
O tempo de execução é O (n!) Porque há n! permutações.
Aspen
Por que você está usando em step == len(string)vez de step == len(string) - 1?
tulians
Porque então os últimos 2 itens nunca seriam trocados. Tente 'abc' até que b e c sejam trocados.
Roman Riesen
16

Aqui está outra maneira de fazer a permutação de string com código mínimo. Basicamente, criamos um loop e continuamos trocando dois caracteres por vez. Dentro do loop, teremos a recursão. Observe, só imprimimos quando os indexadores atingem o comprimento de nossa string. Exemplo: ABC i para nosso ponto de partida e nosso parâmetro de recursão j para nosso loop

aqui está uma ajuda visual como funciona da esquerda para a direita de cima para baixo (é a ordem de permutação)

insira a descrição da imagem aqui

o código :

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
fonte
5
Pode ser útil mencionar que esta é a base do paradigma do bactracking .
AruniRC de
Mais informações, códigos iguais / semelhantes: geeksforgeeks.org/… Eu gosto mais do seu exemplo com o exemplo gráfico;)
CTS_AE
8

Os usuários do Stack Overflow já postaram algumas soluções fortes, mas eu queria mostrar mais uma solução. Este eu acho mais intuitivo

A ideia é que para uma dada string: podemos recursar pelo algoritmo (pseudo-código):

permutations = char + permutations (string - char) para char na string

Eu espero que isso ajude alguém!

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
fonte
4
Isso não funcionará para casos em que há caracteres repetidos (str.replace). Por exemplo: rqqx
sanjay
Use: [permutation_list.append (char + a) para a em permutações (string.replace (char, "", 1))]
user3761855
7

Esta é uma função simples para retornar permutações exclusivas:

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
fonte
6
1. Você cometeu um erro de digitação: revursive_perms-> recursive_perms. 2. Economizaria RAM e tempo se recursive_permsfosse um conjunto em vez de uma lista que você converte em um conjunto na instrução de retorno. 3. Seria mais eficiente usar o corte de strings em vez de .replaceconstruir o arg para a chamada recursiva de permutations. 4. Não é uma boa ideia usar stringcomo um nome de variável porque isso obscurece o nome do stringmódulo padrão .
PM 2Ring
5

Aqui está outra abordagem diferente da que @Adriano e @illerucis postaram. Este tem um melhor tempo de execução, você mesmo pode verificar medindo o tempo:

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

Para uma string arbitrária "dadffddxcf" levou 1,1336 segundos para a biblioteca de permutação, 9,125 segundos para esta implementação e 16,357 segundos para a versão de @Adriano e @illerucis. Claro que você ainda pode otimizá-lo.

Rooky
fonte
4

itertools.permutationsé bom, mas não lida bem com sequências que contêm elementos repetidos. Isso porque internamente ele permeia os índices de sequência e não se importa com os valores dos itens de sequência.

Claro, é possível filtrar a saída de itertools.permutationsatravés de um conjunto para eliminar as duplicatas, mas ainda é uma perda de tempo gerando essas duplicatas e, se houver vários elementos repetidos na sequência de base, haverá muitas duplicatas. Além disso, usar uma coleção para conter os resultados desperdiça RAM, negando o benefício de usar um iterador em primeiro lugar.

Felizmente, existem abordagens mais eficientes. O código a seguir usa o algoritmo do matemático indiano do século 14, Narayana Pandita, que pode ser encontrado no artigo da Wikipedia sobre Permutação . Esse algoritmo antigo ainda é uma das maneiras mais rápidas conhecidas de gerar permutações em ordem, e é bastante robusto, pois lida corretamente com permutações que contêm elementos repetidos.

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)

resultado

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

Claro, se você quiser coletar as strings produzidas em uma lista, você pode fazer

list(lexico_permute_string('data'))

ou em versões recentes do Python:

[*lexico_permute_string('data')]
PM 2Ring
fonte
Muito bem explicado.
lmao
2

por que você não faz simplesmente:

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

você não obtém nenhuma duplicata como pode ver:

 ['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
fonte
5
Não, você sempre obtém duplicatas (ou pior) se tiver duas ou mais letras iguais. Esse foi o caso no exemplo do @máquinayearning, pois ele usou a palavra pilhas em vez de pilha . Isso significa: sua solução só funciona para palavras com caracteres exclusivos.
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
fonte
2
Você pode explicar por que sua solução é melhor do que as já fornecidas?
Noel Widmer
Não disse que a minha solução é melhor que as outras. Acabei de fornecer minha solução para fazer isso.
Srivastava
1

Veja itertools.combinationsou itertools.permutations.

Brian Cain
fonte
4
combinações não são relevantes para o seu problema. ele está transpondo letras, o que significa que a ordem é relevante, o que significa apenas permutações
máquina ansiando
1

Aqui está uma versão ligeiramente melhorada do código de Illerucis para retornar uma lista de todas as permutações de uma string scom caracteres distintos (não necessariamente em ordem de classificação lexicográfica), sem usar 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
fonte
1

Mais uma iniciativa e solução recursiva. A ideia é selecionar uma letra como pivô e depois criar uma palavra.

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

Resultado:

abc
acb
bac
bca
cab
cba
Faroq AL-Tam
fonte
0

Aqui está uma versão do gerador realmente simples:

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)

Eu acho que não é tão ruim!

Gritty Kitty
fonte
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
fonte
por favor, tente adicionar alguma descrição.
Arun Vinoth
0

Aqui está uma implementação recursiva simples e direta;

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
fonte
1
Você deve corrigir o recuo. Não há necessidade de salvar os resultados da chamada recursiva para stringPermutationsem uma lista - você pode iterar diretamente sobre ele, por exemplo for perm in stringPermutations(s[:pos] + s[pos+1:]):. Além disso, você pode simplificar o forloop usando enumerateem vez de range, e eliminar a char = s[pos]atribuição: for pos, char in enumerate(s):.
PM 2Ring
0
from itertools import permutations
perms = [''.join(p) for p in permutations('ABC')]

perms = [''.join(p) for p in permutations('stack')]
Satish Kumar
fonte
5
por favor, tente adicionar alguma descrição.
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"))

Esta é uma maneira de gerar permutações com recursão, você pode entender o código facilmente tomando as strings 'a', 'ab' e 'abc' como entrada.

Você ganha todos os N! permutações com isso, sem duplicatas.

Jasser
fonte
0

Todo mundo adora o cheiro de seu próprio código. Apenas compartilhando o que considero mais simples:

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
fonte
0

Este programa não elimina as duplicatas, mas acho que é uma das abordagens mais eficientes:

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
fonte
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
fonte
por favor, tente adicionar alguma descrição.
Arun Vinoth
0

Solução mais simples usando permutações.

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
fonte
0

Todas as palavras possíveis com pilha

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

Retorna sucessivas permutações de comprimento r de elementos no iterável.

Se r não for especificado ou for Nenhum, então o padrão de r será o comprimento do iterável e todas as permutações de comprimento total possíveis serão geradas.

As permutações são emitidas em ordem de classificação lexicográfica. Portanto, se o iterável de entrada for classificado, as tuplas de permutação serão produzidas em ordem classificada.

Os elementos são tratados como únicos com base em sua posição, não em seu valor. Portanto, se os elementos de entrada forem únicos, não haverá valores de repetição em cada permutação.

CodePerfectPlus
fonte
0

Esta é uma solução recursiva com a n!qual aceita elementos duplicados na string

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

Validei a solução levando em consideração dois elementos, o número de combinações é n!e o resultado não pode conter duplicatas. Então:

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
fonte
0

Com abordagem recursiva.

def permute(word):
    if len(word) == 1:
        return [word]
    permutations = permute(word[1:])
    character = word[0]
    result = []
    for p in permutations:
        for i in range(len(p)+1):
            result.append(p[:i] + character + p[i:])
    return result




running code.

>>> permute('abc')
['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
Muriithi Derrick
fonte
-1

Com recursão

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

Com abordagem iterativa (usando pilha)

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

Com classificação Lexicograficamente

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