Разделение строки

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

Например:

input:  ["abcd"]
output: ["abcd"]
        ["abc","d"]
        ["ab","cd"]
        ["ab","c","d"]
        ["a","bc","d"]
        ["a","b","cd"]
        ["a","bcd"]
        ["a","b","c","d"]

Я немного зациклен на том, как создавать все возможные списки. Комбинации просто дают мне списки с длиной подмножества набора строк, перестановки будут давать все возможные способы заказа.

Я могу сделать все случаи с одной запятой в списке из-за итерации через срезы, но я не могу делать случаи с двумя запятыми, такими как "ab", "c", "d" и "a", "б", "CD"

Моя попытка w/slice:

test="abcd"

for x in range(len(test)):
     print test[:x],test[x:]

Ответ 1

Как насчет чего-то типа:

from itertools import combinations

def all_splits(s):
    for numsplits in range(len(s)):
        for c in combinations(range(1,len(s)), numsplits):
            split = [s[i:j] for i,j in zip((0,)+c, c+(None,))]
            yield split

после чего:

>>> for x in all_splits("abcd"):
...     print(x)
...     
['abcd']
['a', 'bcd']
['ab', 'cd']
['abc', 'd']
['a', 'b', 'cd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

Ответ 2

Вы можете использовать itertools для этого, но мне легче написать рекурсивный генератор напрямую:

def gen_commas(s):
    yield s
    for prefix_len in range(1, len(s)):
        prefix = s[:prefix_len]
        for tail in gen_commas(s[prefix_len:]):
            yield prefix + "," + tail

Тогда

print list(gen_commas("abcd"))

печатает

['abcd', 'a,bcd', 'a,b,cd', 'a,b,c,d', 'a,bc,d', 'ab,cd', 'ab,c,d', 'abc,d']

Я не уверен, почему мне это легче. Может быть, просто потому, что он мертв легко сделать это напрямую, -)

Ответ 3

Использование itertools:

import itertools
input_str =  "abcd"
for k in range(1,len(input_str)):
    for subset in itertools.combinations(range(1,len(input_str)), k): 
        s = list(input_str)
        for i,x in enumerate(subset): s.insert(x+i, ",")
        print "".join(s)

дает:

a,bcd
ab,cd
abc,d
a,b,cd
a,bc,d
ab,c,d
a,b,c,d

Также рекурсивная версия:

def commatoze(s,p=1):
    if p == len(s):
        print s
        return
    commatoze(s[:p] + ',' + s[p:], p + 2)
    commatoze(s, p + 1)

input_str =  "abcd"
commatoze(input_str)

Ответ 4

Вы можете создать набор мощностей n - 1 мест, которые вы могли бы поместить запятыми:

Каков хороший способ комбинировать с помощью набора?

а затем вставьте запятые в каждую позицию.

Ответ 5

Вы можете решить задачу целочисленную композицию и использовать композиции для руководства, где можно разбить список. Целочисленная композиция может быть решена довольно легко с небольшим количеством динамического программирования.

def composition(n):
    if n == 1: 
        return [[1]] 
    comp = composition (n - 1) 
    return [x + [1] for x in comp] + [y[:-1] + [y[-1]+1] for y in comp]

def split(lst, guide):
    ret = []
    total = 0
    for g in guide:
        ret.append(lst[total:total+g])
        total += g
    return ret

lst = list('abcd')
for guide in composition(len(lst)):
    print split(lst, guide)

Другой способ создания целочисленной композиции:

from itertools import groupby
def composition(n):
    for i in xrange(2**(n-1)):
        yield [len(list(group)) for _, group in groupby('{0:0{1}b}'.format(i, n))]

Ответ 6

Учитывая

import more_itertools as mit

код

list(mit.partitions("abcd"))

Выход

[[['a', 'b', 'c', 'd']],
 [['a'], ['b', 'c', 'd']],
 [['a', 'b'], ['c', 'd']],
 [['a', 'b', 'c'], ['d']],
 [['a'], ['b'], ['c', 'd']],
 [['a'], ['b', 'c'], ['d']],
 [['a', 'b'], ['c'], ['d']],
 [['a'], ['b'], ['c'], ['d']]]

Установите more_itertools через > pip install more-itertools.