Encontrar todas las posibles permutaciones de una cadena dada en Python

89

Tengo una cuerda. Quiero generar todas las permutaciones de esa cadena, cambiando el orden de los caracteres en ella. Por ejemplo, diga:

x='stack'

lo que quiero es una lista como esta,

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

Actualmente estoy iterando en el elenco de la lista de la cadena, seleccionando 2 letras al azar y transponiéndolas para formar una nueva cadena, y agregándola al elenco de l. Según la longitud de la cadena, estoy calculando el número de permutaciones posibles y continuando las iteraciones hasta que el tamaño del conjunto alcanza el límite. Debe haber una mejor manera de hacer esto.

Nihar Sarangi
fuente

Respuestas:

143

El módulo itertools tiene un método útil llamado permutations (). La documentación dice:

itertools.permutations (iterable [, r])

Devuelve permutaciones de longitud r sucesivas de elementos en el iterable.

Si r no se especifica o es None, entonces r toma como valor predeterminado la longitud del iterable y se generan todas las posibles permutaciones de longitud completa.

Las permutaciones se emiten en orden lexicográfico. Entonces, si la entrada iterable está ordenada, las tuplas de permutación se producirán en orden ordenado.

Sin embargo, tendrás que unir tus letras permutadas como cadenas.

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

Si tiene problemas con los duplicados, intente ajustar sus datos en una estructura sin duplicados como set:

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

Gracias a @pst por señalar que esto no es lo que tradicionalmente pensaríamos como una conversión de tipos, sino más bien una llamada al set()constructor.

anhelo de máquina
fuente
3
Nit: set(...)no "lanza". Más bien, genera (y produce) el conjunto que representa la colección de entrada: una vez generado, no tiene asociación con la colección de entrada (y es un objeto diferente, no solo una vista diferente).
@pst: Mmmm, yo tendería a no estar de acuerdo. Sé en Ada o Pascal que un elenco es solo una nueva vista de tipo en los mismos bits. Sin embargo, al menos desde la perspectiva de C, la conversión es un término apropiado, ya sea que esté cambiando o no la estructura subyacente de los datos. Simplemente se refiere a la conversión de tipos explícita. Por favor, explique mi malentendido si puede.
anhelo de máquina
1
Encasillado . Si bien, como usted señala, puede ser diferente a una simple vista, me gusta intentar mantener los conceptos separados para evitar confusiones. Debería haber mencionado "coerción" explícitamente en mi primer comentario, aunque solo consideraría establecer una función: lista -> conjunto.
1
Lo veo bool, es una función que se evalúa como bool (Verdadero / Falso) dependiendo de la entrada. Encuentro que el uso de "emitir" aquí es falso y engañoso ...
1
Como actualización interesante, la documentación se ha cambiado desde entonces para decir que la función incorporada bool () se puede usar para convertir cualquier valor a un valor booleano , específicamente convertir en lugar de emitir. Esto sucedió en la publicación posterior a esta discusión, ¡lo que me llevó a creer que esta discusión condujo a un cambio en los documentos!
anhelo de máquina
45

¡Puedes conseguir todo N! permutaciones sin mucho 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)
ilerucis
fuente
Buena esa. Funciona perfectamente
kishorer747
1
Lo modifiqué ligeramente, no necesitamos intercambiar las variables si i == paso
siraj
4
El tiempo de ejecución es O (n!) Porque hay n! permutaciones.
Aspen
¿Por qué estás usando en step == len(string)lugar de step == len(string) - 1?
Tulians
Porque entonces los 2 últimos elementos nunca se intercambiarían. Intente 'abc' hasta que byc se intercambien.
Roman Riesen
14

Aquí hay otra forma de hacer la permutación de cadena con código mínimo. Básicamente creamos un bucle y luego seguimos intercambiando dos caracteres a la vez. Dentro del bucle tendremos la recursividad. Observe que solo imprimimos cuando los indexadores alcanzan la longitud de nuestra cadena. Ejemplo: ABC i para nuestro punto de partida y nuestro parámetro de recursividad j para nuestro bucle

aquí hay una ayuda visual sobre cómo funciona de izquierda a derecha de arriba a abajo (es el orden de permutación)

ingrese la descripción de la imagen aquí

el 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
fuente
5
Podría ser útil mencionar que esta es la base del paradigma de seguimiento .
AruniRC
Más información, códigos iguales / similares: geeksforgeeks.org/… Me gusta más tu ejemplo aunque con el ejemplo gráfico;)
CTS_AE
8

Los usuarios de Stack Overflow ya han publicado algunas soluciones sólidas, pero quería mostrar otra solución. Este me parece más intuitivo

La idea es que para una cadena dada: podemos recurrir mediante el algoritmo (pseudocódigo):

permutaciones = char + permutaciones (cadena - char) para char en cadena

¡Espero que esto ayude a alguien!

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
fuente
4
Esto no funcionará en los casos en los que haya caracteres repetidos (str.replace). Por ejemplo: rqqx
sanjay
Utilice: [permutation_list.append (char + a) para a in permutations (string.replace (char, "", 1))]
user3761855
7

Aquí hay una función simple para devolver permutaciones únicas:

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
fuente
6
1. Tiene un error tipográfico: revursive_perms-> recursive_perms. 2. Ahorraría RAM y tiempo si recursive_permsfuera un conjunto en lugar de una lista que se convierte en un conjunto en la declaración de retorno. 3. Sería más eficiente usar la división de cadenas en lugar de .replaceconstruir el argumento para la llamada recursiva de permutations. 4. No es una buena idea utilizarlo stringcomo nombre de variable porque oculta el nombre del stringmódulo estándar .
PM 2 Ring
5

Aquí hay otro enfoque diferente al que publicaron @Adriano y @illerucis. Esto tiene un mejor tiempo de ejecución, puede verificarlo usted mismo midiendo el tiempo:

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 una cadena arbitraria "dadffddxcf", tomó 1,1336 segundos para la biblioteca de permutación, 9,125 segundos para esta implementación y 16,357 segundos para la versión de @ Adriano y @illerucis. Por supuesto, aún puede optimizarlo.

Novato
fuente
4

itertools.permutationses bueno, pero no funciona bien con secuencias que contienen elementos repetidos. Eso es porque internamente permuta los índices de secuencia y no tiene en cuenta los valores de los elementos de la secuencia.

Claro, es posible filtrar la salida de a itertools.permutationstravés de un conjunto para eliminar los duplicados, pero aún así se pierde tiempo generando esos duplicados, y si hay varios elementos repetidos en la secuencia base, habrá muchos duplicados. Además, usar una colección para almacenar los resultados desperdicia RAM, anulando el beneficio de usar un iterador en primer lugar.

Afortunadamente, existen enfoques más eficientes. El siguiente código utiliza el algoritmo del matemático indio del siglo XIV Narayana Pandita, que se puede encontrar en el artículo de Wikipedia sobre Permutación . Este antiguo algoritmo sigue siendo una de las formas más rápidas conocidas de generar permutaciones en orden, y es bastante robusto, ya que maneja correctamente las permutaciones que contienen 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)

salida

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

Por supuesto, si desea recopilar las cadenas producidas en una lista, puede hacerlo

list(lexico_permute_string('data'))

o en versiones recientes de Python:

[*lexico_permute_string('data')]
PM 2 Anillo
fuente
Bellamente explicado.
lmao
2

por qué no lo haces simple:

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

no obtiene ningún duplicado como puede 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
fuente
4
No, siempre obtienes duplicados (o peor) si tienes dos o más letras iguales. Ese fue el caso en el ejemplo de @ machineyearning, ya que usó la palabra pilas en lugar de pila . Eso significa: Su solución solo funciona para palabras con caracteres únicos.
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
fuente
2
¿Puede explicar por qué su solución es mejor que las que ya se ofrecen?
Noel Widmer
No dije que mi solución sea mejor que las demás. Solo proporcioné mi solución para hacer eso.
Srivastava
1

Ver itertools.combinationso itertools.permutations.

Brian Cain
fuente
4
combinaciones no es relevante para su problema. está transponiendo letras, lo que significa que el orden es relevante, lo que significa solo permutaciones
anhelo de la máquina
1

Aquí hay una versión ligeramente mejorada del código de illerucis para devolver una lista de todas las permutaciones de una cadena scon caracteres distintos (no necesariamente en orden de clasificación lexicográfico), sin 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
fuente
1

Otra iniciativa más y solución recursiva. La idea es seleccionar una letra como pivote y luego crear una palabra.

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

Salida:

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

Aquí hay una versión de generador realmente simple:

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)

¡Creo que no es tan malo!

Gatito arenoso
fuente
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
fuente
por favor intente agregar alguna descripción.
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
fuente
5
por favor intente agregar alguna descripción.
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 es una forma de generar permutaciones con recursividad, puede comprender el código fácilmente tomando las cadenas 'a', 'ab' y 'abc' como entrada.

¡Obtienes todo N! permutaciones con esto, sin duplicados.

Jasser
fuente
0

Todo el mundo ama el olor de su propio código. Solo comparto el que encuentro el más simple:

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

Este programa no elimina los duplicados, pero creo que es uno de los enfoques más 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
fuente
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
fuente
por favor intente agregar alguna descripción.
Arun Vinoth
0

Solución más sencilla mediante permutaciones.

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

Toda la palabra posible con pila

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

Devuelve permutaciones de longitud r sucesivas de elementos en el iterable.

Si r no se especifica o es None, entonces r toma como valor predeterminado la longitud del iterable y se generan todas las posibles permutaciones de longitud completa.

Las permutaciones se emiten en orden lexicográfico. Entonces, si la entrada iterable está ordenada, las tuplas de permutación se producirán en orden ordenado.

Los elementos se tratan como únicos en función de su posición, no de su valor. Entonces, si los elementos de entrada son únicos, no habrá valores repetidos en cada permutación.

CodePerfectPlus
fuente
0

Esta es una solución recursiva con la n!que acepta elementos duplicados en la cadena

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

Validé la solución teniendo en cuenta dos elementos, el número de combinaciones es n!y el resultado no puede contener duplicados. Entonces:

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
fuente
-1

Aquí hay una implementación recursiva simple y directa;

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
soy
fuente
1
Deberías arreglar la sangría. No es necesario guardar los resultados de la llamada recursiva stringPermutationsen una lista; puede iterar directamente sobre ella, por ejemplo for perm in stringPermutations(s[:pos] + s[pos+1:]):. Además, se puede simplificar el forbucle utilizando enumerateen lugar de range, y eliminar la char = s[pos]asignación: for pos, char in enumerate(s):.
PM 2 Ring
-1

Con recursividad

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

Con enfoque iterativo (usando pila)

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

Con ordenado lexicográficamente

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