创建特定尺寸的可能组合

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)是元组之一。在这些索引处打破应该产生对应于[s[0:2],s[2,4],s[4,6]]的["fo","ob","ar"]，在这种情况下的表达式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重复做同样的工作一遍又一遍。例如，如果您已经计算出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回报n部分从i个指标的s所有分区以后

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