from typing import Sequence
import itertools


def generate_all_kmers(k: int, alphabet="CGAT") -> Sequence[str]:
    """generate all polymers of length k
    Args:
        k: length of the Kmer
        alphabet: base unit of the kmer, [C, G, A, T] for DNA
    """

    def _generate_all_kmers(partial_kmers: Sequence[str]):
        if len(partial_kmers[0]) == k:
            return partial_kmers
        return _generate_all_kmers(
            partial_kmers=list(
                itertools.chain.from_iterable(
                    [partial_kmer + n for n in alphabet]
                    for partial_kmer in partial_kmers
                )
            )
        )

    return _generate_all_kmers(alphabet)