Generate a list of all possible "patterns" of letters

Question

I'm trying to find a way to generate all possible "patterns" of length N out of a list of K letters. I've looked at similar questions but they all seem to be asking about combinations, permutations, etc. which is not exactly what I'm after.

For example, let K = 3 and N = 2. That is, I want all 2-letter "patterns" that can be made with the letters [A, B, C]. AA is one such pattern. AB is another. And those are the only two. BB and CC are the same as AA, it's just "a letter, and then the same letter." Similarly, BA, BC, AC, etc. are the same as AB, it's just "a letter, and then a different letter." So for this simple case, there are only two patterns, and in fact this illustrates why K must be less than or equal to N (adding additional letters to choose from doesn't change anything).

If instead, K = 3, N = 3, then the five possible patterns would be AAA, AAB, ABA, ABB, and ABC. Every other permutation of three letters has a pattern that is identical to one of those five.

If K = 2 and N = 3, then there are just four possible patterns: AAA, AAB, ABA, ABB. (ABC is no longer a valid choice because I only have two letters to choose from.)

Of course, these examples are trivial to do by hand - I'm trying to create code that will generate all possible patterns for larger values of N and K. This may be more of a pure mathematical question but ultimately I need a Python function that will produce these so I thought I'd try here first to see if anyone knows or can think of an efficient way to do this.

Answer 1

One of the comments, from @JacobRR, was very close to what we need. Each "pattern" actually corresponds to partitioning of set {1, 2, ..., N} into K subsets. Each subset (even empty!) corresponds to the positions where letter l_k should be placed (l_1 = A, l_2 = B etc.). There's a demo here. https://thewebdev.info/2021/10/28/how-to-generate-set-partitions-in-python

For example, in case K=3, N=3, the partitions would be

{1,2,3}, ∅, ∅
{1}, {2, 3}, ∅
{2}, {1, 3}, ∅
{3}, {1, 2}, ∅
{1}, {2}, {3}

and for K=2, N=3, it's

{1,2,3}, ∅
{1}, {2, 3}
{2}, {1, 3}
{3}, {1, 2}

corresponding exactly to the given examples.

This question is also relevant.

https://codereview.stackexchange.com/questions/1526/finding-all-k-subset-partitions

I also wrote my own naive implementation.

import copy

N = 3
K = 2

iter = min(N, K)

def partitions(S, K):

    if K == 1:
        return [[S]]
    if len(S) == 0:
        return [[]]
    
    result = []
    S_new = copy.copy(S)
    first = S_new.pop(0)
    
    if (K-1 <= len(S_new)):
        p1 = partitions(S_new, K-1)
        for p in p1:
            p.append([first])
            result.append(p)
    if (K <= len(S_new)):
        p2 = partitions(S_new, K)

        for p in p2:
            for idx in range(len(p)):
                p_new = copy.deepcopy(p)
                p_new[idx].append(first)
                result.append(p_new)
                
        
    return result

for idx in range(1, iter+1):
    print(partitions([i for i in range(0, N)], idx))