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?

hehe that's the part that kept me from writing a working response to your previous question ;) — Nicolas78, Dec 27 '11 at 15:32
I think you've forgotten the combination `("A", "BD", "C")` in your result set? — Howard, Dec 27 '11 at 15:38

Howard · Accepted Answer · 2011-12-27T15:32:25.233

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

Do you have a version that I can port to C++. The yield keyword makes it very hard — raaj, Jan 28 '20 at 23:10

score 1 · Answer 2 · answered Dec 27 '11 at 15:24

Well, using the itertools library, I've come up with this:

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

score 1 · Answer 3 · answered Dec 27 '11 at 15:37

You should take the first element ("A") + all the partitions of what remains, so getting:
"A","AB","AC","AD","ABC","ABD","ACD","ABCD", then for each of these sets you have to consider what remains and apply the same routine (select the first element and extend with all the partitions of what remains), and so on...

By proceedeing in this way you will get the desired list without repetitions.

score 1 · Answer 4 · edited May 23 '17 at 12:20

Generate all partitions of the set {'A', 'B', 'C', 'D'}
For each partition, concatenate the inner sets, and sort the outer set.

Searching for set partition gives this, so with a minor modification and converting the code for Python 3 we can get

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)

which prints

['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']

Yielding sub combinations

4 Answers4

Linked