Qual é uma maneira mais rápida de encontrar todas as partições exclusivas de um inteiro e seus pesos?

Tenho visto muitas postagens sobre esse assunto, mas nenhuma é exatamente o que estou procurando.

Quero encontrar todas as maneiras pelas quais um número inteiro positivo N maior que 1 pode ser expresso como a soma de no máximo N números inteiros de 1 a N, como de costume.

Por exemplo, na notação padrão, estas são todas as partições de 6:

[(1, 1, 1, 1, 1, 1),
 (1, 1, 1, 1, 2),
 (1, 1, 1, 2, 1),
 (1, 1, 1, 3),
 (1, 1, 2, 1, 1),
 (1, 1, 2, 2),
 (1, 1, 3, 1),
 (1, 1, 4),
 (1, 2, 1, 1, 1),
 (1, 2, 1, 2),
 (1, 2, 2, 1),
 (1, 2, 3),
 (1, 3, 1, 1),
 (1, 3, 2),
 (1, 4, 1),
 (1, 5),
 (2, 1, 1, 1, 1),
 (2, 1, 1, 2),
 (2, 1, 2, 1),
 (2, 1, 3),
 (2, 2, 1, 1),
 (2, 2, 2),
 (2, 3, 1),
 (2, 4),
 (3, 1, 1, 1),
 (3, 1, 2),
 (3, 2, 1),
 (3, 3),
 (4, 1, 1),
 (4, 2),
 (5, 1),
 (6,)]

Agora, a notação é de entropia muito baixa: primeiro, cada ocorrência do número aumenta o tamanho de uma partição específica. Isso é ineficiente e é difícil contar as ocorrências dos números quando eles se repetem muitas vezes. Quero substituir todas as ocorrências de um número por uma tupla de dois elementos, na qual o primeiro elemento é o número e o segundo é a contagem. Por exemplo, (1, 1, 1, 1, 1, 1)é equivalente a (1, 6). Ambos contêm a mesma informação, mas um é claramente muito mais conciso.

E segundo, há muitas duplicatas na saída; por exemplo, há cinco partições que contêm quatro 1s e um 2, que são contadas como cinco elementos separados. Isso também é ineficiente, já que a adição é comutativa; mudar a ordem dos números não altera o resultado, então todos são equivalentes, são todos o mesmo elemento.

Entretanto, se substituirmos todos os cinco por apenas um elemento, perdemos informações.

Em vez disso, desejo substituí-lo pelo seguinte formato:

Counter({((1, 2), (2, 2)): 6,
         ((1, 1), (2, 1), (3, 1)): 6,
         ((1, 4), (2, 1)): 5,
         ((1, 3), (3, 1)): 4,
         ((1, 2), (4, 1)): 3,
         ((1, 1), (5, 1)): 2,
         ((2, 1), (4, 1)): 2,
         ((1, 6),): 1,
         ((2, 3),): 1,
         ((3, 2),): 1,
         ((6, 1),): 1})

Então, quero que o resultado seja um Counterem que as chaves sejam as partições exclusivas e os valores sejam quantas maneiras os números podem ser organizados.

E sim, eu escrevi uma função para isso, usando força bruta e memorização. Ela se mostrou bem eficiente.

Primeiro, esta é a implementação que gera o resultado no formato padrão. Posto aqui para comparação:

def partitions(number: int) -> list[tuple[int, ...]]:
    result = []
    stack = [(number, ())]

    while stack:
        remaining, path = stack.pop()
        if not remaining:
            result.append(path)
        else:
            stack.extend((remaining - i, path + (i,)) for i in range(remaining, 0, -1))

    return result

São necessários 582 milissegundos para encontrar todas as partições de 20 no CPython e 200 milissegundos no PyPy3:

CPython

In [22]: %timeit partitions(20)
582 ms ± 4.22 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

PyPy3

In [36]: %timeit partitions(20)
199 ms ± 3.17 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Agora, a abordagem de força bruta com memorização que gera o formato pretendido:

PARTITION_COUNTERS = {}


def partition_counter(number: int) -> Counter:
    if result := PARTITION_COUNTERS.get(number):
        return result
    
    result = Counter()
    for i in range(1, number):
        for run, count in partition_counter(number - i).items():
            new_run = []
            added = False
            for a, b in run:
                if a == i:
                    new_run.append((a, b + 1))
                    added = True
                else:
                    new_run.append((a, b))
            
            if not added:
                new_run.append((i, 1))
            
            result[tuple(sorted(new_run))] += count
    
    result[((number, 1),)] = 1
    PARTITION_COUNTERS[number] = result
    return result

CPython

In [23]: %timeit PARTITION_COUNTERS.clear(); partition_counter(20)
10.4 ms ± 72.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

PyPy3

In [37]: %timeit PARTITION_COUNTERS.clear(); partition_counter(20)
9.75 ms ± 58.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Leva apenas 10 milissegundos para encontrar todas as partições de 20, muito, muito mais rápido que a primeira função, e o PyPy3 não o torna mais rápido.

Mas como podemos fazer melhor? Afinal, estou apenas usando força bruta. Sei que existem muitos algoritmos inteligentes para partição de números inteiros, mas nenhum deles gera saídas no formato pretendido.