Все возможные способы чередования двух строк

Ответ 1

Идея

Пусть две строки, которые вы хотите чередовать, - s и t. Мы будем использовать рекурсию для генерации всех возможных способов чередования этих двух строк.

Если в любой момент времени мы чередовали первые i символы s и первые j символы t, чтобы создать некоторую строку res, тогда у нас есть два способа их чередования для следующий шаг -

• Добавить символ i+1 th от s до res
• Добавить j+1 -го символа t в res

Мы продолжаем эту рекурсию до тех пор, пока не будут использованы все символы обеих строк, а затем мы сохраним этот результат в списке строк lis, как в приведенном ниже коде.

Код

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

Выход

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

Эта реализация настолько эффективна, насколько мы можем получить (по крайней мере, асимптотически), поскольку мы никогда не генерируем одну и ту же строку дважды.

Ответ 2

Несколько других решений уже опубликованы, но большинство из них генерирует полный список чередующихся строк (или что-то эквивалентное ему) в памяти, что увеличивает их использование памяти в зависимости от длины ввода. Конечно, должен быть лучший способ.

Перечисление всех способов чередования двух последовательностей, длина a и b соответственно, в основном такое же, как перечисление всех целых чисел a + b с установленными бит b бит. Каждое такое целое число соответствует четкому способу чередования последовательностей, полученных путем замены каждого 0-бит на элемент первой последовательности и каждый 1 бит элементом второй последовательности.

Удобно, есть умный и эффективный способ рассчитать следующее целое число с таким же количеством бит, установленным, которое мы можем использовать для генерации всех такие целые числа. Итак, сделайте это первым:

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

Теперь мы можем использовать этот генератор для генерации всех способов чередования любых двух последовательностей:

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

Обратите внимание, что для того, чтобы попытаться быть как можно более общим, этот код принимает произвольные типы последовательностей и списки возврата. Строки - это последовательности в Python, поэтому вы можете передать их в порядке; для преобразования сгенерированных списков в строки, вы можете объединить их элементы, например. с "".join(), например:

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

Здесь мы идем: полностью нерекурсивное эффективное генераторное решение, которое использует очень мало памяти даже для длинных входов, и только генерирует каждый выход один раз (что не требует неэффективного этапа устранения дубликатов). И он работает даже в Python 2 и 3.

Ответ 3

Очень неэффективен, но работает:

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

Ответ 4

Вам нужно сравнить индекс a с b и c до d, затем отфильтровать те элементы, где индекс a больше индекса b и индекс c > больше индекса 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')]]

Демо:

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

Ответ 5

Только для спорта

решение без явных условий или предикатов

(т.е. без каких-либо if ключевых слов):

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)

Для этого нам нужна вспомогательная функция:

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

Если число неповторяющихся перестановок велико, это, вероятно, довольно неэффективно из-за вызова sorted. Для альтернатив получения уникальных перестановок неединственных значений см. Переходы с с уникальными значениями.

TL;? DR

Нет проблем. Мы можем довести этот подход до этой мерзости:

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

(Использование определения набора для результата вместо того, чтобы обеспечить уникальность ранее.)