Encontrar todas las permutaciones posibles de una cadena determinada en Python [duplicado]
Tengo una cuerda. Quiero generar todas las permutaciones a partir de esa cadena, cambiando el orden de los caracteres que contiene. Por ejemplo, diga:
x='stack'
lo que quiero es una lista como esta,
l=['stack','satck','sackt'.......]
Actualmente estoy iterando en la lista de conversión de la cadena, eligiendo 2 letras al azar y transponiéndolas para formar una nueva cadena, y agregándola al conjunto de conversión de l. En función de la longitud de la cadena, estoy calculando el número de permutaciones posibles y continúo las iteraciones hasta que el tamaño establecido alcance el límite. Debe haber una mejor manera de hacer esto.
El módulo itertools tiene un método útil llamado permutaciones(). La documentación dice:
itertools.permutaciones(iterable[, r])
Devuelve permutaciones sucesivas de longitud r de elementos en el iterable.
Si r no se especifica o es Ninguno, entonces r tiene por defecto la longitud del iterable y se generan todas las permutaciones posibles de longitud completa.
Las permutaciones se emiten en orden lexicográfico. Entonces, si el iterable de entrada está ordenado, las tuplas de permutación se producirán en orden.
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', 'tachuelas', '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']
Si le preocupan 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 consideraríamos una conversión de tipos, sino más bien una llamada al set()constructor.
¡Puedes conseguir todos los 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)
