simple recursive algorithm and corresponding iterative variant to enumerate subsets of size k of a n-sized set

enumerate_combinations.py

import collections

def enumcombs(l: list, k: int):
    # assert len(l) > 0 and k > 0
    L = []
    # s = sorted(l)  # should only be done on first call
    if k==1:
        return [[x] for x in l]
    for i,item in enumerate(l):
        # assumption: no repeated items, otherwise have to use an auxiliary index set
        # sg = [x for x in l if x > item]
        sg = l[i+1:]  # should be faster
        if not sg: continue
        L.extend([item]+y for y in enumcombs(sg, k-1))
    return L

def enumcombs_lazy(l: list, k: int):
    # assert len(l) > 0 and k > 0
    L = []
    # s = sorted(l)  # should only be done on first call
    if k==1:
        for x in l:
            yield [x]
    for i,item in enumerate(l):
        # assumption: no repeated items, otherwise have to use an auxiliary index set
        # sg = [x for x in l if x > item]
        sg = l[i+1:]  # should be faster
        if not sg: continue
        for y in enumcombs(sg, k-1):
            yield [item]+y

def enumcombs_i(n: int, k: int):
    return enumcombs(list(range(1,n+1)), k)

def enumcombs_lazy_i(n: int, k: int):
    yield from enumcombs_lazy(list(range(1,n+1)), k)

# iterative variant
def enumcombs_iterative_lazy(n: int, k: int):
    assert n > 0 and 0 < k <= n
    S = collections.deque()
    l = list(range(1,n+1))
    for i in reversed(l):
        S.append(((i,), k-1))
    while S:
        t, h = S.pop()
        maxitem = t[-1]
        if h > 0:
            for idx in reversed(l[maxitem:]):  # maxitem, not maxitem+1, since items starts by 1
                S.append(((*t, idx), h-1))
        else:  # h == 0
            yield t

def enumcombs_stackless(n: int, k: int):
    assert n > 0 and 0 < k <= n
    state = list(range(1,k+1))  # e.g. for k=3: [1,2,3]
                 #      |
    level = k-1  # [1,2,3]  # levels for k=3: 0,1,2
    # mins = tuple(range(1,k+1))      # from 1 to k, bounds included
    maxs = tuple(range(n-k+1,n+1))  # from n-k+1 to n, bounds included

    # L = [] ###
    while True:
        if level == -1:
            # return L ###
            return
        if state[level] == maxs[level]:
            if level == k-1:
                # L.append(tuple(state)) ###
                yield tuple(state)
            state[level] = -1  # reset to min value for that level
            level -= 1  # transitions from maxval to -1 are leftwise
            continue
        elif state[level] == -1:
            state[level] = state[level-1] + 1
            if level != k-1:
                level += 1  # transitions from -1 to minval are rightwise
            continue
        else:
            if level == k-1:
                # L.append(tuple(state)) ###
                yield tuple(state)
                state[level] += 1
            else:
                state[level] += 1
                level += 1

if __name__ == '__main__':
    enumcombs_i(20, 10)