repeticion - permutaciones python 3
Encontrar todas las permutaciones posibles de una cadena dada en python (17)
Tengo una cadena. 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 la lista del elenco de la cadena, escogiendo 2 letras al azar y transponiéndolas para formar una nueva cadena, y sumarla para establecer el reparto de l. En función de la longitud de la cadena, estoy calculando el número de permutaciones posibles y las iteraciones continuas hasta que el tamaño del conjunto alcanza el límite. Debe haber una mejor manera de hacer esto.
¡Puedes obtener 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)
¿Por qué no 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 obtienes ningún duplicado como puedes 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]
Aquí hay otro enfoque diferente al que publicaron @Adriano y @illerucis. Esto tiene un mejor tiempo de ejecución, puedes verificarlo 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" se necesitaron 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 puedes optimizarlo.
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)
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
Aquí hay una versión del 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!
Aquí hay una versión ligeramente mejorada del illerucis de illerucis para devolver una lista de todas las permutaciones de una cadena con 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
El módulo itertools tiene un método útil llamado permutations (). La documentación dice:
itertools.permutations (iterable [, r])
Devuelve las permutaciones de longitud de r sucesivas de los elementos en iterable.
Si no se especifica r o None, r se establece de manera predeterminada en la longitud de iterable y se generan todas las permutaciones de longitud completa posibles.
Las permutaciones se emiten en orden lexicográfico. Entonces, si la entrada iterable se ordena, 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 , ''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 , ''kscta'', ''kscat'', ''ktsac'', ''ktsca'', ''ktasc'', ''ktacs'', ''ktcsa'', ''ktcas'', ''kastc'', ''kasct'', ''katsc'', ''katcs'', ''kacst'', ''kacts'', ''kcsta'', ''kcsat'', ''kctsa'', ''kctas'', ''kcast'', ''kcats'']
Si te molestan los duplicados, intenta ajustar tus datos en una estructura sin duplicados como un 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 considerábamos como un elenco de tipos, sino más bien una llamada al constructor de set() .
Este programa no elimina los duplicados, pero creo que es uno de los más eficaces:
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
Los usuarios de desbordamiento de pila 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 por el algoritmo (pseudo código):
permutations = char + permutations (string - char) para char en cadena
Espero que 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, ""))]
return permutation_list
Todo el mundo ama el olor de su propio código. Solo compartiendo el que encuentro 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
itertools.permutations es bueno, pero no trata bien con secuencias que contienen elementos repetidos. Esto se debe a que 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 itertools.permutations través de un conjunto para eliminar los duplicados, pero todavía desperdicia tiempo generando esos duplicados, y si hay varios elementos repetidos en la secuencia base habrá muchos duplicados. Además, el uso de una colección para contener los resultados desperdicia RAM, negando el beneficio de usar un iterador en primer lugar.
Afortunadamente, hay 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 sólido, ya que maneja adecuadamente 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 entregadas en una lista, puede hacer
list(lexico_permute_string(''data''))
o en versiones recientes de Python:
[*lexico_permute_string(''data'')]
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
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 manera de generar permutaciones con recursión, puede entender el código fácilmente tomando las cadenas ''a'', ''ab'' y ''abc'' como entrada.
¡Obtienes todo N! permutaciones con esto, sin duplicados.
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'')))
from itertools import permutations
perms = [''''.join(p) for p in permutations(''ABC'')]
perms = [''''.join(p) for p in permutations(''stack'')]