Создание возможных комбинаций определенного размера

Question

Строка/список, например. 'Foobar'. Мне нужно разбить его во всех возможных комбинациях, где число групп равно n, например. 3.

Это даст мне, например.

['foo', 'ba', 'r'] 
['f', 'ooba', 'r'] 
['fo', 'oo', 'bar'] 
['f', 'o', 'obar'] 

и т.д.

Каков наилучший алгоритм для создания всех возможных комбинаций?

Answer 1

Похоже, работа для itertools:

from itertools import combinations 

def compositions(s,k): 
    n = len(s) 
    for c in combinations(range(1,n),k-1): 
     yield [s[i:j] for i,j in zip((0,)+c,c+(n,))] 

Как это работает в том, что combinations Урожайность части кортежи, состоящая из возможных точек разреза. Например (s = "foobar" и k = 3) (2,4) является одним из кортежей.Разрыв по этим показателям должен давать ["fo","ob","ar"], что соответствует [s[0:2],s[2,4],s[4,6]], выражение zip((0,)+c,c+(n,)) в этом случае совпадает с zip((0,2,4),(2,4,6)), следовательно, итерация по нему приводит к повторению итерации по последовательным парам индексов для последующих фрагментов.

Например,

>>> for c in compositions("foobar",3): print(c) 

['f', 'o', 'obar'] 
['f', 'oo', 'bar'] 
['f', 'oob', 'ar'] 
['f', 'ooba', 'r'] 
['fo', 'o', 'bar'] 
['fo', 'ob', 'ar'] 
['fo', 'oba', 'r'] 
['foo', 'b', 'ar'] 
['foo', 'ba', 'r'] 
['foob', 'a', 'r'] 

Я выбрал название «композиции», так как вы в основном говорим о compositions в комбинаторике. Мой алгоритм был основан на доказательстве в связанной статье о том, что количество композиций из n элементов в k частей равно C(n-1,k-1).

Answer 2

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

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

Считая функцию с прототипом

def rec(input, n): 

это псевдо-код:

if n == 1: 
    final_set.append([input[i:]]) 
else: 
    for i in range (0, len(input) - n + 1): 
     for rec_set in rec(input[i:], n - 1): 
      final_set.append(merge(input[:i], rec_set)) 

Используя ваш пример, мы имеем:

rec('foobar', 3) 
= {['f', rec('oobar', 2)], ['fo', rec('obar', 2)], ['foo', rec('bar', 2)], ['foob', rec('ar', 2)]} 

= {['f','o', rec('obar', 1)], ['f','oo', rec('bar', 1)], ['f','oob', rec('ar', 1)], ['f','ooba', rec('r', 1)], ['fo', 'o', rec('bar', 1)], ['fo', 'ob', rec('ar', 1)], ['fo', 'oba', rec('r', 1)], ['foo', 'b', rec('ar', 1)], ['foo', 'ba', rec('r', 1)], ['foob', 'a', rec('r', 1)]} 

= {['f','o', 'obar'], ['f','oo', 'bar'], ['f','oob', 'ar'], ['f','ooba', 'r'], ['fo', 'o', 'bar'], ['fo', 'ob', 'ar'], ['fo', 'oba', 'r',], ['foo', 'b', 'ar'], ['foo', 'ba', 'r'], ['foob', 'a', 'r']} 

Важно помнить, до кэш частичные результаты во избежание r epeat делает ту же работу снова и снова. Например, если вы уже рассчитали rec('oobar', 2), сохраните результат в некотором кеше (например, словарь подходит для этого) и проверьте в начале функции, были ли вы уже рассчитаны все возможные комбинации для указанной входной строки и n. Это уменьшает временную сложность от экспоненциального до полиномиального.

Answer 3

Для этого можно использовать backtracking. Создавайте все возможные расщепления и отбрасывайте их, когда вы разделите слово на более чем три части.

Answer 4

Вот простая рекурсия

def split(s, n): 
    def rec_split(i, s, n): 
     ans = [] 

     if n == 1: 
      ans.append([s[i:]]) 
      return ans 

     for j in range(i+1, len(s)): 
      head = s[i:j] 
      tails = rec_split(j, s, n-1) 
      for tail in tails: 
       ans.append([head] + tail) 
     return ans 

    return rec_split(0, s, n) 

for e in split("foobar", 3): 
    print(e) 

# ['f', 'o', 'obar'] 
# ['f', 'oo', 'bar'] 
# ['f', 'oob', 'ar'] 
# ['f', 'ooba', 'r'] 
# ['fo', 'o', 'bar'] 
# ['fo', 'ob', 'ar'] 
# ['fo', 'oba', 'r'] 
# ['foo', 'b', 'ar'] 
# ['foo', 'ba', 'r'] 
# ['foob', 'a', 'r'] 

rec_split возвращает все разбиения s в n части из i -м индекса вперед

Answer 5

Вы можете решить рекурсивно с генератором:

def sections(s, n): 
    if n == 1: 
     yield [s] 

    if n > 1: 
     for i in range(1, len(s)): 
      for tail in section(s[i:], n - 1): 
       yield [s[0:i]] + tail 

и используйте его следующим образом:

for s in sections("foobar", 3): 
    print s