屈服子组合

Question

我需要一个函数返回给定段的子段。例如，sub_combinations("ABCD")应该产生：

("A", "B", "C", "D") 
("A", "B", "CD") 
("A", "BC", "D") 
("A", "BCD") 
("AB", "C", "D") 
("AB", "CD") 
("ABC", "D") 
("ABCD") 
("ABD", "C") * 
("AC", "BD") * 
("AC", "B", "D") * 
("ACD", "B") * 
("AD", "BC") * 
("AD", "B", "C") * 

("A","C","B","D")是无效的，因为它不是按序列顺序。换句话说，("A","B","C","D")是正确的。

("AC", "B", "D")是有效的，因为“C”按顺序跟在“A”之后，“B”跟在“AC”之后。

这是据我已经得到了：

def sub_combinations(segment): 
     for i in range(1, len(segment)): 
       for j in sub_combinations(segment[i:]): 
         yield (segment[:i],) + j 
     yield (segment,) 

for i in sub_combinations("ABCD"): 
     print(i) 

('A', 'B', 'C', 'D') 
('A', 'B', 'CD') 
('A', 'BC', 'D') 
('A', 'BCD') 
('AB', 'C', 'D') 
('AB', 'CD') 
('ABC', 'D') 
('ABCD',) 

然而，这是缺少这些额外的组合。

关于如何进行的任何建议？

Answer 1

你可以改变你的代码如下：

def sub_combinations(segment): 
    if len(segment) == 1: 
    yield (segment,) 
    else: 
    for j in sub_combinations(segment[1:]): 
     yield (segment[0],)+j 
     for k in range(len(j)): 
     yield (segment[0]+j[k],)+j[:k]+j[k+1:] 

如果段仅包含一个字符的结果是很容易。否则，分开第一个字符并确定字符串其余部分的所有分区。之后，您将得到以下（不同的）解决方案：分解字符可以构建一个单独的元组，也可以将其添加到以前解决方案的任何元组中。

由于递归调用，此方法构建了从单个字符大小写到全部参数的解决方案集。

你的榜样情况下提供了以下结果：

('A', 'B', 'C', 'D') 
('AB', 'C', 'D') 
('AC', 'B', 'D') 
('AD', 'B', 'C') 
('A', 'BC', 'D') 
('ABC', 'D') 
('AD', 'BC') 
('A', 'BD', 'C') 
('ABD', 'C') 
('AC', 'BD') 
('A', 'B', 'CD') 
('AB', 'CD') 
('ACD', 'B') 
('A', 'BCD') 
('ABCD',) 

Answer 2

好，使用itertools library，我想出了这一点：

from itertools import permutations 
def sub_combinations(iterable, r): 
    pool = tuple(iterable) 
    n = len(pool) 
    for indices in permutations(range(n), r): 
     if sorted(indices) == list(indices): 
      yield tuple(pool[i] for i in indices) 

def combinations(s): 
    l = len(s) 
    for i in range(1, l+1): 
     for item in sub_combinations(s, i): 
      yield item 

Answer 3

你应该采取的第一个元素（ “A”）+中剩下的所有分区，因此让：
“A”， “AB” ，“AC”，“AD”，“ABC”，“ABD”，“ACD”，“ABCD”，那么对于这些​​集合中的每一个，您必须考虑剩下的和应用相同的例程（选择第一个元素，所有剩余的分区）等等......

通过以这种方式进行处理，您将得到所需的列表而不会重复。

Answer 4

1. 产生该组{'A', 'B', 'C', 'D'}
2. 对于每个分区的所有分区，串联的内集和排序外集。

搜索集合划分给this，所以用一个小的修改，并转换为Python 3的代码中，我们可以得到

def sub_combinations(set_): 
    if not set_: 
     yield [] 
     return 
    for i in range(1<<(len(set_)-1)): 
     parts = [[], []] 
     for item in set_: 
      parts[i&1].append(item) 
      i >>= 1 
     for b in sub_combinations(parts[1]): 
      yield sorted(''.join(x) for x in [parts[0]]+b) 

for p in sub_combinations("abcd"): 
    print(p) 

它打印

['abcd'] 
['a', 'bcd'] 
['acd', 'b'] 
['ab', 'cd'] 
['a', 'b', 'cd'] 
['abd', 'c'] 
['ac', 'bd'] 
['a', 'bd', 'c'] 
['ad', 'bc'] 
['ad', 'b', 'c'] 
['abc', 'd'] 
['a', 'bc', 'd'] 
['ac', 'b', 'd'] 
['ab', 'c', 'd'] 
['a', 'b', 'c', 'd']