por - reemplazar caracteres en python

Todas las formas posibles de intercalar dos cadenas

Question

Estoy tratando de generar todas las formas posibles de intercalar dos cadenas arbitrarias en Python.

Por ejemplo: si las dos cadenas son ''ab'' y ''cd'' , la salida que deseo obtener es:

[''abcd'', ''acbd'', ''acdb'', ''cabd'', ''cadb'', ''cdab'']

Ver a es siempre antes de b (y c antes de d ). Estoy luchando para encontrar una solución a esto. Lo he probado como se muestra a continuación:

import itertools

def shuffle(s,t):
    string = s+t
    for i in itertools.permutations(string):
        print(''''.join(i))

shuffle(''ab'',''cd'')

Pero como se esperaba, esto devuelve todas las permutaciones posibles sin tener en cuenta el orden de a y b ( c y d ).

Answer 1

La idea

Deje que las dos cadenas que desea intercalar sean s y t . Usaremos la recursión para generar todas las formas posibles de intercalar estas dos cadenas.

Si en algún momento del tiempo hemos intercalado los primeros i caracteres de s los primeros j caracteres de t para crear algunos res cadena, entonces tenemos dos formas de intercalarlos para el siguiente paso:

1. Añade el i+1 carácter de s a res
2. Añade el j+1 carácter de t a res

Continuamos esta recursión hasta que todos los caracteres de ambas cadenas se hayan utilizado y luego almacenamos este resultado en una lista de cadenas de caracteres como en el código a continuación.

El código

def interleave(s, t, res, i, j, lis):
    if i == len(s) and j == len(t):
        lis.append(res)
        return
    if i < len(s):
        interleave(s, t, res + s[i], i + 1, j, lis)
    if j < len(t):
        interleave(s, t, res + t[j], i, j + 1, lis)

l = []
s = "ab"
t = "cd"
interleave(s, t, "", 0, 0, l)
print l

Salida

[''abcd'', ''acbd'', ''acdb'', ''cabd'', ''cadb'', ''cdab'']

Esta implementación es tan eficiente como podemos obtener (al menos asintóticamente) ya que nunca generamos la misma cadena dos veces.

Answer 2

Muy ineficiente pero funcionando:

def shuffle(s,t):
    if s=="":
        return [t]
    elif t=="":
        return [s]
    else:
        leftShuffle=[s[0]+val for val in shuffle(s[1:],t)]
        rightShuffle=[t[0]+val for val in shuffle(s,t[1:])]
        leftShuffle.extend(rightShuffle)
        return leftShuffle

print(shuffle("ab","cd"))

Answer 3

Solo necesita comparar el índice de a con b y c con d luego filtre los elementos en los que el índice de a es mayor que el índice de b y el índice de c es mayor que el índice de d .

def interleave(s, t):
    mystring = s + t
    return [el for el in [''''.join(item) for item in permutations(mystring) if  item.index(''a'') < item.index(''b'') and item.index(''c'') < item.index(''d'')]]

Manifestación:

>>> from itertools import permutations
>>> s = ''ab''
>>> t = ''cd''
>>> [el for  el in [''''.join(item) for item in permutations(s+t) if item.index(''a'') < item.index(''b'') and item.index(''c'') < item.index(''d'')]]
[''abcd'', ''acbd'', ''acdb'', ''cabd'', ''cadb'', ''cdab'']

Answer 4

Solo para los deportes

Una solución sin condicionales o predicados explícitos.

(Es decir, sin ninguna if clave):

from itertools import chain, repeat, permutations
from copy import deepcopy


def shuffle(*strings):
    # Treat the strings as pools from which to draw elements in order.
    # Convert the strings to lists, so that drawn items can be removed:
    pools = (list(string) for string in strings)

    # From each pool, we have to draw as many times as it has items:
    pools_to_draw_from = chain.from_iterable(
        repeat(pool, len(pool)) for pool in pools
    )

    # Because itertools.permutations treats elements as unique based on their
    # position, not on their value and because pools_to_draw_from has repeated
    # repeated items, we would get repeated permutations, if we would not
    # filter them out with `unique`.
    possible_drawing_orders = unique(permutations(pools_to_draw_from))

    # For each drawing order, we want to draw (and thus remove) items from our
    # pools. Subsequent draws within the same drawing order should get the
    # respective next item in the pool, i.e., see the modified pool. But we don''t
    # want the pools to be exhausted after processing the first drawing ordering.
    #
    # Deepcopy preserves internal repetition and thus does exactly what we need.
    possible_drawing_orders = (deepcopy(pdo) for pdo in possible_drawing_orders)

    # Draw from the pools for each possible order,
    # build strings and return them in a list:
    return [''''.join(_draw(p)) for p in possible_drawing_orders]


def _draw(drawing_order):
    return (pool_to_draw_from.pop(0) for pool_to_draw_from in drawing_order)

Necesitamos una función de ayuda para esto:

from operator import itemgetter
from itertools import groupby

def unique(iterable, key=None):
    # Other than unique_everseen from
    # https://docs.python.org/3/library/itertools.html#itertools-recipes, this
    # works for iterables of non-hashable elements, too.
    return unique_justseen(sorted(iterable, key=key), key)


def unique_justseen(iterable, key=None):
    """
    List unique elements, preserving order. Remember only the element just seen.
    """
    # from https://docs.python.org/3/library/itertools.html#itertools-recipes
    return map(next, map(itemgetter(1), groupby(iterable, key)))

Si el número de permutaciones no únicas es grande, esto es probablemente bastante ineficaz, debido a la llamada a sorted . Para obtener alternativas para obtener permutaciones únicas de valores no únicos, consulte permutaciones con valores únicos .

TL; DR?

No hay problema. Podemos reducir este enfoque a esta abominación:

from itertools import chain, repeat, permutations
from copy import deepcopy

def shuffle(*strings):
    return list({''''.join(l.pop(0) for l in deepcopy(p)) for p in permutations(chain.from_iterable(repeat(list(s), len(s)) for s in strings))})

(Usar una comprensión de conjunto en el resultado en lugar de asegurar la singularidad anterior).

Answer 5

Ya se han publicado varias otras soluciones, pero la mayoría genera la lista completa de cadenas intercaladas (o algo equivalente a ella) en la memoria, haciendo que su uso de memoria crezca exponencialmente como una función de la longitud de entrada. Seguramente debe haber una mejor manera.

Enumerar todas las formas de intercalar dos secuencias, de longitud a y b respectivamente, es básicamente lo mismo que enumerar todos los enteros de bits a + b con el conjunto de b bits de exably. Cada uno de estos enteros corresponde a una forma distinta de intercalar las secuencias, que se obtiene al reemplazar cada bit 0 con un elemento de la primera secuencia, y cada bit 1 con un elemento de la segunda secuencia.

Convenientemente, hay una forma inteligente y eficiente de calcular el siguiente entero con el mismo número de bits establecido , que podemos utilizar para generar todos estos enteros. Así que hagamos eso primero

def bit_patterns(m, n):
    """Generate all m-bit numbers with exactly n bits set, in ascending order.
    See http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/
    """
    patt = (1 << int(n)) - 1
    if patt == 0: yield 0; return  # loop below assumes patt has at least one bit set!
    while (patt >> m) == 0:
        yield patt
        lowb = patt & -patt  # extract the lowest bit of the pattern
        incr = patt + lowb   # increment the lowest bit
        diff = patt ^ incr   # extract the bits flipped by the increment
        patt = incr + ((diff // lowb) >> 2)  # restore bit count after increment

Ahora podemos usar este generador para generar todas las formas de intercalar dos secuencias:

def interleave(a, b):
    """Generate all possible ways to interleave two sequences."""
    m = len(a) + len(b)
    n = len(a)
    for pattern in bit_patterns(m, n):
        seq = []
        i = j = 0
        for k in range(m):
            bit = pattern & 1
            pattern >>= 1
            seq.append(a[i] if bit else b[j])
            i += bit
            j += 1-bit
        yield seq

Tenga en cuenta que, para intentar ser lo más genérico posible, este código toma tipos de secuencia arbitrarios y devuelve listas. Las cadenas son secuencias en Python, por lo que puedes pasarlas muy bien; para volver a convertir las listas generadas en cadenas, puede concatenar sus elementos, por ejemplo, con "".join() , como esto:

foo = "ABCD"
bar = "1234"
for seq in interleave(foo, bar):
    print("".join(seq))

Ahí vamos: una solución basada en generadores totalmente eficiente y no recursiva que usa muy poca memoria incluso para entradas largas, y solo genera cada salida una vez (por lo tanto, no requiere un paso de eliminación de duplicados ineficiente). E incluso funciona tanto en Python 2 como en 3.