A bunch of different simple combination and permutation generators in Python. Yes I know about itertools 😁 just for funsies

combos_and_perms.py

from functools import reduce
import itertools
from collections.abc import Generator


def combinations[T](
    lst: list[T], k: int, combo: list[T] = None) -> Generator[list[T]]:
  """ Yield combinations of the list of size k """
  if combo is None:
    combo = []
  if k == 0:
    yield combo
    return
  for i in range(len(lst)):
    # put the i'th element in the combo accumulator and then
    # call with the rest of the elements
    yield from combinations(lst[i+1:], k-1, combo + [lst[i]])


def combinations_full_recursive[T](
    lst: list[T], k: int, combo: list[T] = None) -> Generator[list[T]]:
  """ Yield combinations of the list of size k """
  if combo is None:
    combo = []
  if k == 0:
    yield combo
    return
  if not lst:
    return
  # take the current element
  yield from combinations_full_recursive(lst[1:], k-1, combo + [lst[0]])
  # dont the front element
  yield from combinations_full_recursive(lst[1:], k, combo)


def combinations_queue[T](
    lst: list[T], k: int) -> Generator[list[T]]:
  """ Yield combinations of the list of size k """
  stack = [(0, [])]
  while stack:
    start, combo = stack.pop(0)
    if len(combo) == k:
      yield combo
    # we have a combo here that's not finished - so we can start at start, eg
    # the elements we haven't used yet, and push the possibility of using each 
    # element in the i'th spot on the stack
    for i in range(start, len(lst)):
      stack.append((i + 1, combo + [lst[i]]))


def permutations[T](lst: list[T], r: int | None = None) -> Generator[list[T]]:
  """ Yield permutations of size r"""
  if not lst or r == 0:
    yield []
    return
  
  r = len(lst) if r is None else r
  for i in range(len(lst)):
    # take out the current element
    rest = lst[:i] + lst[i+1:]
    # stick it at the start of the rest of the perms
    yield from ([lst[i]] + p for p in permutations(rest, r - 1))


def permutations_queue[T](
    lst: list[T], r: int | None = None) -> Generator[list[T]]:
  """ Yield permutations of size r"""
  r = len(lst) if r is None else r
  if not lst:
    yield []
  stack = [(lst, [])]
  while stack:
    rest, perm = stack.pop(0)
    if len(perm) == r:
      yield perm
      continue
    # same logic as recursive
    for i in range(len(rest)):
      stack.append((rest[:i] + rest[i+1:], perm + [rest[i]]))


# based on ocaml implementation:
# by: http://typeocaml.com/2015/05/05/permutation/
def insert_all_positions[T](x: T, lst: list[T]) -> list[list[T]]:
  def inner(prev, results, orig_lst):
    match orig_lst:
      case []:
        return [(prev + [x])] + results
      case [first, *rest]:
        return inner(prev + [first], [(prev + [x] + orig_lst)] + results, rest)
  return inner([], [], lst)


def permutations_full_recursive[T](
    lst: list[T], r: int | None = None) -> Generator[list[T]]:
 
  r = len(lst) if r is None else r
  if r == 0:
    yield []
    return
  if not lst or r > len(lst):
    return

  match lst:
    case [x] if r == 1:
      yield [x]
    case [first, *rest]:
      # permutations of size r with first in them
      yield from reduce(
        lambda acc, p: acc + insert_all_positions(first, p),
        permutations_full_recursive(rest, r - 1),
        []
      )
      # permutations of size without first in them
      yield from permutations_full_recursive(rest, r)


def main():

  a = [1, 2, 3, 4]
  for r in range(len(a) + 1):
    print(f"{r=}")
    print('recur', list(combinations(a, r)))
    print('frecu', list(combinations_full_recursive(a, r)))
    print('queue', list(combinations_queue(a, r)))
    print('its  ', list(itertools.combinations(a, r)))
  
  a = [1, 2, 3, 4]
  for r in range(len(a) + 1):
    print(f"{r=}")
    print('recur', list(permutations(a, r)))
    print('frecu', list(permutations_full_recursive(a, r)))
    print('queue', list(permutations_queue(a, r)))
    print('its  ', list(itertools.permutations(a, r)))
  

if __name__ == "__main__":
  main()