python - Yielding sub combinations

Question

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") is not valid since it is not in sequence order. In other words, ("A","B","C","D") is instead correct.

("AC", "B", "D") is valid since "C" follows "A" in sequential order, and "B" follows "AC".

This is as far as I've gotten:

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.

Any suggestions on how to proceed?

Answer 1

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

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