屈服子组合

一尘不染

屈服子组合

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

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

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

阅读 183

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