recursive elimination of character groups in a string in python

You can use recursion with a generator. Additionally, applying itertools.groupby to produce groupings up front leads to a shorter solution:

from itertools import groupby as gb
def get_groups(s, chain=[]):
   if not s:
      yield chain+[s]
   else:
      r = [list(b) for _, b in gb(s)]
      for i, a in enumerate(r):
        if len(a) > 1:
           t = ''.join(map(''.join, [*r[:i], *([] if i >= len(r) else r[i+1:])]))
           yield from get_groups(t, chain+[s])

cases = ['RGRRRGGGRR', 'GGGRGRGRG', 'GGRRGRRRRGGGGRGRGG', 'GRRRGRRRGRRRGRRRGR']
for case in cases:
   print(f'{case}: {any(get_groups(case))}')

Output:

RGRRRGGGRR: True
GGGRGRGRG: False
GGRRGRRRRGGGGRGRGG: True
GRRRGRRRGRRRGRRRGR: True

get_groups produces an empty list [] if there is no possible path whereby the input is completed reduced to an empty string by removing groupings, and a listing of all the possible paths to an empty string.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top