import time
import string
 
def sub_combinations(segment, size=0):
    if segment == ():
        yield ()
        return
    stop = min(size or len(segment), len(segment))
    for i in range(1, stop + 1):
        for j in sub_combinations(segment[i:], size):
            yield (segment[:i],) + j
 
 
def subtuples(t):
  for i in range(1<< (len(t)-1)):
    result = [ [ t[0] ] ]
    for j in range(len(t)-1):
      if (1<<j) & i:
        result[-1].append(t[j+1])
      else:
        result.append([ t[j+1] ])
    yield result
 
f = sub_combinations
data = tuple(string.ascii_lowercase[:22])
 
for f in sub_combinations, subtuples:
    t0 = time.time()
    for x in f(data):
        pass
    print('{} {}'.format(f.__name__, time.time() - t0))

aW1wb3J0IHRpbWUKaW1wb3J0IHN0cmluZwoKZGVmIHN1Yl9jb21iaW5hdGlvbnMoc2VnbWVudCwgc2l6ZT0wKToKICAgIGlmIHNlZ21lbnQgPT0gKCk6CiAgICAgICAgeWllbGQgKCkKICAgICAgICByZXR1cm4KICAgIHN0b3AgPSBtaW4oc2l6ZSBvciBsZW4oc2VnbWVudCksIGxlbihzZWdtZW50KSkKICAgIGZvciBpIGluIHJhbmdlKDEsIHN0b3AgKyAxKToKICAgICAgICBmb3IgaiBpbiBzdWJfY29tYmluYXRpb25zKHNlZ21lbnRbaTpdLCBzaXplKToKICAgICAgICAgICAgeWllbGQgKHNlZ21lbnRbOmldLCkgKyBqCgoKZGVmIHN1YnR1cGxlcyh0KToKICBmb3IgaSBpbiByYW5nZSgxPDwgKGxlbih0KS0xKSk6CiAgICByZXN1bHQgPSBbIFsgdFswXSBdIF0KICAgIGZvciBqIGluIHJhbmdlKGxlbih0KS0xKToKICAgICAgaWYgKDE8PGopICYgaToKICAgICAgICByZXN1bHRbLTFdLmFwcGVuZCh0W2orMV0pCiAgICAgIGVsc2U6CiAgICAgICAgcmVzdWx0LmFwcGVuZChbIHRbaisxXSBdKQogICAgeWllbGQgcmVzdWx0CgpmID0gc3ViX2NvbWJpbmF0aW9ucwpkYXRhID0gdHVwbGUoc3RyaW5nLmFzY2lpX2xvd2VyY2FzZVs6MjJdKQoKZm9yIGYgaW4gc3ViX2NvbWJpbmF0aW9ucywgc3VidHVwbGVzOgogICAgdDAgPSB0aW1lLnRpbWUoKQogICAgZm9yIHggaW4gZihkYXRhKToKICAgICAgICBwYXNzCiAgICBwcmludCgne30ge30nLmZvcm1hdChmLl9fbmFtZV9fLCB0aW1lLnRpbWUoKSAtIHQwKSk=