屈服子组合 [英] Yielding sub combinations

问题描述

我需要一个函数，它返回子段对于一个给定段。例如， sub_combinations（ABCD）应产生：

I need a function which returns subsegments for a given segment. For example, sub_combinations("ABCD") should yield:

("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）是不是正确的。

("A","C","B","D") is not valid since it is not in sequence order. In other words, ("A","B","C","D") is instead correct.

（AC，B，D）是有效的，因为C跟随A的顺序，而B遵循交流

("AC", "B", "D") is valid since "C" follows "A" in sequential order, and "B" follows "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',)

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

However this is missing those extra combinations.

如何进行任何建议？

推荐答案

您可能会改变你的code如下：

You may change your code as follows:

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:]

如果你的段只包含一个字符的结果是很容易的。否则分裂出去的第一个字符，并确定你的字符串的其余所有分区。之后，你有以下的（不同的）解决方案：在splitt客字符生成一个单独的元组，也可以将其添加到您的任何previous解决方案的元组

If your segment contains only one character the result is quite easy. Otherwise split off the first character and determine all partitions of the rest of your string. Afterwards you have the following (distinct) solutions: the splitt-off character builds a separate tuple or you can add it to any of the tuples of your previous solution.

由于递归调用此方法构建的解决方案，从单个字符的情况下达到充分论证设置。

Due to the recursive calls this method builds the solution set from the single character case up to the full argument.

您例子的情况下提供了以下结果：

Your example case gives the following result:

('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',)

这篇关于屈服子组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！