Buscar todas las permutaciones de lista de una cadena en Python

Question

tengo una cadena de letras que me gustaría que se dividan en todas las combinaciones posibles (el orden de las letras debe permanecer fijo), de modo que:

s = 'monkey' 

se convierte en:

combinations = [['m', 'onkey'], ['mo', 'nkey'], ['m', 'o', 'nkey'] ... etc] 

¿Alguna idea?

Answer 1

def splitter(str): 
    for i in range(1, len(str)): 
     start = str[0:i] 
     end = str[i:] 
     yield (start, end) 
     for split in splitter(end): 
      result = [start] 
      result.extend(split) 
      yield result 

combinations = list(splitter(str)) 

Tenga en cuenta que de manera predeterminada a un generador para evitar que se quede sin memoria con cadenas largas.

Answer 2

http://wordaligned.org/articles/partitioning-with-python contiene un interesante post acerca de la secuencia de partición, aquí es la aplicación que utilizan:

#!/usr/bin/env python 

# From http://wordaligned.org/articles/partitioning-with-python 

from itertools import chain, combinations 

def sliceable(xs): 
    '''Return a sliceable version of the iterable xs.''' 
    try: 
     xs[:0] 
     return xs 
    except TypeError: 
     return tuple(xs) 

def partition(iterable): 
    s = sliceable(iterable) 
    n = len(s) 
    b, mid, e = [0], list(range(1, n)), [n] 
    getslice = s.__getitem__ 
    splits = (d for i in range(n) for d in combinations(mid, i)) 
    return [[s[sl] for sl in map(slice, chain(b, d), chain(d, e))] 
      for d in splits] 

if __name__ == '__main__': 
    s = "monkey" 
    for i in partition(s): 
     print i 

Qué imprimiría:

['monkey'] 
['m', 'onkey'] 
['mo', 'nkey'] 
['mon', 'key'] 
['monk', 'ey'] 
['monke', 'y'] 
['m', 'o', 'nkey'] 
['m', 'on', 'key'] 
['m', 'onk', 'ey'] 
['m', 'onke', 'y'] 
['mo', 'n', 'key'] 
['mo', 'nk', 'ey'] 
['mo', 'nke', 'y'] 
['mon', 'k', 'ey'] 
['mon', 'ke', 'y'] 
['monk', 'e', 'y'] 
... 
['mo', 'n', 'k', 'e', 'y'] 
['m', 'o', 'n', 'k', 'e', 'y'] 

Answer 3

La idea es darse cuenta de que el permutación de un La cadena s es igual a un conjunto que contiene s, y una unión establecida de cada subcadena X de s con el permu tación de s\X. Por ejemplo, permute('key'):

1. {'key'} # 'key' itself
2. {'k', 'ey'} # substring 'k' union 1st permutation of 'ey' = {'e, 'y'}
3. {'k', 'e', 'y'} # substring 'k' union 2nd permutation of 'ey' = {'ey'}
4. {'ke', 'y'} # substring 'ke' union 1st and only permutation of 'y' = {'y'}
5. Unión de 1, 2, 3, y 4, dió todas las permutaciones de la cadena de key.

Con esto en mente, un simple algoritmo puede implementarse:

>>> def permute(s): 
    result = [[s]] 
    for i in range(1, len(s)): 
     first = [s[:i]] 
     rest = s[i:] 
     for p in permute(rest): 
      result.append(first + p) 
    return result 

>>> for p in permute('monkey'): 
     print(p)  

['monkey'] 
['m', 'onkey'] 
['m', 'o', 'nkey'] 
['m', 'o', 'n', 'key'] 
['m', 'o', 'n', 'k', 'ey'] 
['m', 'o', 'n', 'k', 'e', 'y'] 
['m', 'o', 'n', 'ke', 'y'] 
['m', 'o', 'nk', 'ey'] 
['m', 'o', 'nk', 'e', 'y'] 
['m', 'o', 'nke', 'y'] 
['m', 'on', 'key'] 
['m', 'on', 'k', 'ey'] 
['m', 'on', 'k', 'e', 'y'] 
['m', 'on', 'ke', 'y'] 
['m', 'onk', 'ey'] 
['m', 'onk', 'e', 'y'] 
['m', 'onke', 'y'] 
['mo', 'nkey'] 
['mo', 'n', 'key'] 
['mo', 'n', 'k', 'ey'] 
['mo', 'n', 'k', 'e', 'y'] 
['mo', 'n', 'ke', 'y'] 
['mo', 'nk', 'ey'] 
['mo', 'nk', 'e', 'y'] 
['mo', 'nke', 'y'] 
['mon', 'key'] 
['mon', 'k', 'ey'] 
['mon', 'k', 'e', 'y'] 
['mon', 'ke', 'y'] 
['monk', 'ey'] 
['monk', 'e', 'y'] 
['monke', 'y'] 

Answer 4

Una cadena (en contraposición a la lista) orientado enfoque es pensar en el cada par adyacente de caracteres separados por ya sea una espacio o cadena vacía.Que se pueden asignar a 1 y 0, y el número de posibles divisiones son una potencia de 2:

2^(len (s) -1)

por ejemplo, "clave" puede tener '' o '' separa 'ke' y una '', o '' separa 'ey' que conduce a 4 posibilidades:

• clave ('' entre 'k' y 'e' '', entre 'e' y ' y ')
• k ey (' 'entre' k 'y' e ',' 'entre' e 'y' y ')
• tecla (' 'entre' k 'y' e ',' 'entre 'e' e 'y')
• ke Y ('' entre la 'k' y 'e', ​​'' entre 'e' e 'y')

Un pitón ilegible un trazador de líneas que le da un generador en forma de cadena:

operator_positions = (''.join([str(a >> i & 1).replace('0', '').replace('1', ' ') + s[len(s)-1-i] for i in range(len(s)-1, -1, -1)]) for a in range(pow(2, len(s)-1))) 

una versión legible de este generador con comentarios y muestra:

s = 'monkey' 
s_length = len(s)-1 # represents the number of ' ' or '' that can split digits 

operator_positions = (
    ''.join(
     [str(a >> i & 1).replace('0', '').replace('1', ' ') + s[s_length-i] 
     for i in range(s_length, -1, -1)]) # extra digit is for blank string to always precede first digit 
    for a in range(pow(2, s_length)) # binary number loop 
) 
for i in operator_positions: 
    print i 

str (un >> i & 1) convierte una en una cadena binaria, que a su vez tiene su de 0 y 1 del reemplazada por '' y '', r espectivamente La cadena binaria tiene un dígito extra largo, de modo que el primer dígito siempre es ''. De esta forma, como el divisor de dígitos se combina con el primer carácter, siempre resulta en solo el primer carácter.