Возвращает все возможные комбинации строки при ее разделении на n строк.

Я сделал поиск stackoverflow по этому поводу, но не смог найти способ сделать это. Это, вероятно, связано с itertools.

Я хочу найти все возможные результаты разделения строки, скажем, строки thisisateststring на n (равной или неравной длины, не имеет значения, обе должны быть включены) строк.

Например, пусть n будет 3:

[["thisisat", "eststrin", "g"], ["th", "isisates", "tstring"], ............]

python list string chunks
person user3507230    schedule 07.04.2014    source источник
comment
Допускаются ли пустые подстроки?   -  person Sven Marnach    schedule 07.04.2014
comment
Итак, математически вы ищете все возможные суммы размера n для длины (строки), а затем переставляете их?   -  person C.B.    schedule 07.04.2014
comment
@C.B.: Из его вопроса я понимаю, что ему нужны только все возможные способы разбиения строки на n подстрок (поэтому, когда вы объединяете s1 + s2 + s3, вы возвращаете исходную строку).   -  person Paul    schedule 07.04.2014
comment
SvenMarnach, да разрешено. C.B., да, можно и так сказать, но у Павла звучит более лаконично, но, наверное, то же самое и с тем, что ты говоришь. Павел, правильно.   -  person user3507230    schedule 07.04.2014

Ответы (3)


arrow_upward
4
arrow_downward

Включение пустых строк в ваши результаты будет довольно неудобным с itertools.combinations(). Вероятно, проще всего написать собственную рекурсивную версию:

def partitions(s, k):
    if not k:
        yield [s]
        return
    for i in range(len(s) + 1):
        for tail in partitions(s[i:], k - 1):
            yield [s[:i]] + tail

Это будет работать для любого количества k желаемых разделов для любой строки s.

person Sven Marnach    schedule 07.04.2014
comment
Я знаю, что это глупый (и очень простой) вопрос, но есть ли способ вернуть список, потому что, когда я выполняю код, он возвращает: ‹разделы объектов генератора по адресу 0x1026230a0› - person user3507230; 07.04.2014
comment
Назовите это как list(partitions("abcde", 3)). - person Sven Marnach; 07.04.2014

arrow_upward
5
arrow_downward

Вы можете использовать itertools.combinations здесь. Вам просто нужно выбрать две точки разделения для создания каждой результирующей строки:

from itertools import combinations
s = "thisisateststring"
pools = range(1, len(s))
res = [[s[:p], s[p:q], s[q:]] for p, q in combinations(pools, 2)]
print res[0]
print res[-1]

Выход:

['t', 'h', 'isisateststring']
['thisisateststri', 'n', 'g']
person YS-L    schedule 07.04.2014
comment
Это не включает пустые строки, и их неудобно распространять на пустые строки. - person Sven Marnach; 07.04.2014

arrow_upward
0
arrow_downward

Вот рецепт разделения последовательности на n групп, основанный на коде Рэймонда Хеттингера:

import itertools as IT

def partition_into_n(iterable, n, chain=IT.chain, map=map):
    """
    Based on http://code.activestate.com/recipes/576795/ (Raymond Hettinger)
    Modified to include empty partitions, and restricted to partitions of length n
    """
    s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
    m = len(s)
    first, middle, last = [0], range(m + 1), [m]
    getslice = s.__getslice__
    return (map(getslice, chain(first, div), chain(div, last))
            for div in IT.combinations_with_replacement(middle, n - 1))

In [149]: list(partition_into_n(s, 3))
Out[149]: 
[['', '', 'thisisateststring'],
 ['', 't', 'hisisateststring'],
 ['', 'th', 'isisateststring'],
 ['', 'thi', 'sisateststring'],
 ...
 ['thisisateststrin', '', 'g'],
 ['thisisateststrin', 'g', ''],
 ['thisisateststring', '', '']]

Это медленнее, чем рекурсивное решение для маленьких n,

def partitions_recursive(s, n):
    if not n>1:
        yield [s]
        return
    for i in range(len(s) + 1):
        for tail in partitions_recursive(s[i:], n - 1):
            yield [s[:i]] + tail

s = "thisisateststring"
In [150]: %timeit list(partition_into_n(s, 3))
1000 loops, best of 3: 354 µs per loop

In [151]: %timeit list(partitions_recursive(s, 3))
10000 loops, best of 3: 180 µs per loop

но, как и следовало ожидать, это быстрее для больших n (по мере увеличения глубины рекурсии):

In [152]: %timeit list(partition_into_n(s, 10))
1 loops, best of 3: 9.2 s per loop

In [153]: %timeit list(partitions_recursive(s, 10))
1 loops, best of 3: 10.2 s per loop
person unutbu    schedule 15.05.2014