Найти все перестановки в списке разбиения строки в Python

Question

У меня есть строка букв, которую я хотел бы разбить на все возможные комбинации (порядок букв должен оставаться фиксированным), так что:

s = 'monkey'

становится:

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

Есть идеи?

Answer 1

http://wordaligned.org/articles/partitioning-with-python содержит интересный пост о разбиении последовательностей, вот реализация, которую они используют:

#!/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

Что будет печатать:

['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 2

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

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

Answer 3

Идея состоит в том, чтобы понять, что перестановка строки s равна набору, содержащему s, и объединению каждой подстроки X из sперестановка s\X.Например, 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. Объединение 1, 2, 3 и 4 дает все перестановки строки key.

Учитывая это, простой алгоритм может быть реализован:

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

Рассмотрим more_itertools.partitions:

Учитывая

import more_itertools as mit


s = "monkey"

Демо

As-is:

list(mit.partitions(s))
#[[['m', 'o', 'n', 'k', 'e', 'y']],
# [['m'], ['o', 'n', 'k', 'e', 'y']],
# [['m', 'o'], ['n', 'k', 'e', 'y']],
# [['m', 'o', 'n'], ['k', 'e', 'y']],
# [['m', 'o', 'n', 'k'], ['e', 'y']],
# [['m', 'o', 'n', 'k', 'e'], ['y']],
# ...]

После объединения строк:

[list(map("".join, x)) for x in mit.partitions(s)]

Выход

[['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'],
 ['m', 'o', 'n', 'key'],
 ['m', 'o', 'nk', 'ey'],
 ['m', 'o', 'nke', 'y'],
 ['m', 'on', 'k', 'ey'],
 ['m', 'on', 'ke', 'y'],
 ['m', 'onk', 'e', 'y'],
 ['mo', 'n', 'k', 'ey'],
 ['mo', 'n', 'ke', 'y'],
 ['mo', 'nk', 'e', 'y'],
 ['mon', 'k', 'e', 'y'],
 ['m', 'o', 'n', 'k', 'ey'],
 ['m', 'o', 'n', 'ke', 'y'],
 ['m', 'o', 'nk', 'e', 'y'],
 ['m', 'on', 'k', 'e', 'y'],
 ['mo', 'n', 'k', 'e', 'y'],
 ['m', 'o', 'n', 'k', 'e', 'y']]

Установка через > pip install more_itertools.

Answer 5

Подход, ориентированный на строку (в отличие от списка), заключается в том, чтобы каждая соседняя пара символов разделялась пробелом или пустой строкой. Это может быть сопоставлено с 1 и 0, и число возможных разбиений является степенью 2:

2 ^ (len (s) -1)

например, «ключ» может иметь «» или «», разделяющий «ке», и «или», «разделяющий» эй, что приводит к 4 возможностям:

• клавиша ('' между 'k' и 'e', ​​'' между 'e' и 'y')
• k ey ('' между 'k' и 'e', ​​'' между 'e' и 'y')
• k e y ('между' k 'и' e ',' 'между' e 'и' y ')
• ke y ('между' k 'и' e ',' 'между' e 'и' y ')

Нечитаемый вкладыш Python one, который дает вам генератор в виде строки:

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

Читаемая версия этого генератора с комментариями и примером:

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 (a >> i & 1) преобразует a в двоичную строку, которая затем заменяет 0 и 1 на '' и '' соответственно. Двоичная строка представляет собой лишнюю цифру, поэтому первая цифра всегда ''. Таким образом, поскольку разделитель цифр объединяется с первым символом, он всегда приводит только к первому символу.

Answer 6

Мое решение позволяет вам также установить порог для минимального размера подстроки

Это мой код:

def split_string (s, min_str_length = 2, root_string=[], results=[] ):
    """
    :param s: word to split, string
    :param min_str_length: the minimum character for a sub string
    :param root_string:  leave empty
    :param results: leave empty
    :return: nested list of all possible combinations of word split according to the minimum substring length
    """
    for i in range(min_str_length,len(s)):
        if i == min_str_length:
            primary_root_string=root_string
        else:
            root_string = primary_root_string
        if len(s[i:])>= min_str_length :
            results.append(list(chain(*[root_string,[s[:i]],[s[i:]]])))
            root_string = list(chain(*[root_string,[s[:i]]]))
            split_string(s[i:], min_str_length, root_string, results)
    return results

Примеры использования:

Input: split_string ('monkey', min_str_length = 1, root_string=[], results=[] )
Output: 
[['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']]

или

Input: split_string ('monkey', min_str_length = 2, root_string=[], results=[] )
Output: [['mo', 'nkey'], ['mo', 'nk', 'ey'], ['mon', 'key'], ['monk', 'ey']]