小编典典

屈服子组合

algorithm

我需要一个函数,该函数返回给定段的子段。例如,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',)

但是,这缺少那些额外的组合。

有关如何进行的任何建议?


阅读 208

收藏
2020-07-28

共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',)
2020-07-28