Como Penso e Resolvo "Count Ways to Distribute Candies" em Elixir (Corrigido)

Como Penso e Resolvo "Count Ways to Distribute Candies" em Elixir

Um Guia Completo da Força Bruta aos Números de Stirling (com a correção sobre listas vs. tuplas)

Correção importante: A versão original deste artigo afirmava que a solução DP usava "um array unidimensional" em Elixir. Isso está errado. Em Elixir, [] é uma linked list (lista encadeada), e operações de acesso indexado (Enum.at/2) e atualização (List.replace_at/3) são O(n), não O(1). Para obter acesso indexado O(1), é preciso usar tuplas ({}), que são o equivalente mais próximo de arrays em Erlang/Elixir. Esta versão corrige o erro e reanalisa a complexidade.

Na sequência do artigo anterior sobre Distribute Candies Among Children II, vamos agora encarar um problema que eleva a combinatória a outro patamar: Count Ways to Distribute Candies (LeetCode 1692). Enquanto o problema anterior lidava com doces idênticos e crianças distintas, este novo desafio nos apresenta doces únicos e sacos não vazios — uma mudança sutil que transforma completamente a natureza da contagem.

Este artigo percorre o mesmo processo mental: entender o problema, começar pela solução mais simples, encontrar a estrutura matemática subjacente e derivar uma solução ótima em Elixir. No caminho, vamos descobrir os Números de Stirling de Segunda Espécie — uma das sequências mais elegantes da combinatória.

O Problema

Existem n doces únicos (rotulados de 1 a n) e k sacos. Você deve distribuir todos os doces nos sacos de modo que cada saco tenha pelo menos um doce. Retorne o número de maneiras diferentes de distribuir os doces, módulo 10⁹ + 7.

Exemplos:

Input: n = 3, k = 2
Output: 3
Explanation: (1), (2,3); (1,2), (3); (1,3), (2)

Input: n = 4, k = 2
Output: 7

Input: n = 20, k = 5
Output: 206085257

Constraints:

• 1 <= k <= n <= 1000

A assinatura em Elixir é:

defmodule Solution do
  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    # implementação
  end
end

Passo 1: Entendendo o Problema — Doces Únicos e Sacos Não Vazios

A primeira diferença crucial em relação ao problema anterior é que os doces são únicos. Distribuir o doce 1 no saco A e o doce 2 no saco B é diferente de distribuir o doce 1 no saco B e o doce 2 no saco A.

A segunda diferença é que cada saco deve ter pelo menos um doce.

A terceira diferença é que os sacos não são rotulados. O que importa é quais doces estão juntos no mesmo saco.

O Que Estamos Contando?

Estamos contando o número de partições de um conjunto de n elementos em exatamente k subconjuntos não vazios. Em matemática, esse número é o Número de Stirling de Segunda Espécie, denotado por S(n, k).

Por exemplo, S(3, 2) = 3:

• {1}, {2, 3}
• {1, 2}, {3}
• {1, 3}, {2}

Passo 2: Força Bruta — Gerando Todas as Partições

A abordagem mais simples é gerar todas as partições possíveis e contar. Isso é exponencial e inviável para n = 1000, mas serve para validar a solução ótima em testes pequenos.

defmodule Solution do
  def ways_to_distribute(n, k) do
    elementos = Enum.to_list(1..n)
    partitions(elementos, k)
    |> length()
    |> rem(1_000_000_007)
  end

  defp partitions([], 0), do: [[]]
  defp partitions([], _), do: []
  defp partitions(_list, 0), do: []

  defp partitions([h | t], k) do
    new_sets = partitions(t, k - 1) |> Enum.map(&[[h] | &1])

    existing_sets =
      partitions(t, k)
      |> Enum.flat_map(fn partition ->
        Enum.map(0..(k - 1), fn i ->
          List.update_at(partition, i, &[h | &1])
        end)
      end)

    new_sets ++ existing_sets
  end
end

Passo 3: A Recorrência dos Números de Stirling

Considere o n-ésimo doce. Ele pode ser colocado de duas maneiras:

1. Em um saco sozinho: S(n-1, k-1) maneiras.
2. Em um saco já existente: k × S(n-1, k) maneiras.

Portanto:

S(n, k) = k × S(n-1, k) + S(n-1, k-1)

Casos Base

• S(n, n) = 1
• S(n, 0) = 0 para n > 0
• S(0, 0) = 1
• S(n, k) = 0 se k > n

Passo 4: Listas vs. Tuplas em Elixir — A Correção Crítica

Antes de implementar a DP, precisamos entender uma diferença fundamental entre Elixir e linguagens imperativas.

O Erro Comum

Em linguagens como C, Java ou Python, usamos arrays para DP bottom-up. Arrays oferecem acesso indexado O(1) e atualização O(1). É natural traduzir isso para Elixir usando []:

# ERRADO: isso é uma linked list, não um array!
dp = List.duplicate(0, k + 1)
valor = Enum.at(dp, j)              # O(j) — percorre a lista até o índice j
dp = List.replace_at(dp, j, valor)  # O(j) — percorre e reconstrói

Em Elixir, [] é uma linked list. Enum.at/2 percorre a lista do início até o índice j, o que é O(j). List.replace_at/3 também percorre e reconstrói a lista, O(j). Se fizermos isso k vezes por linha, temos O(k²) por linha, e O(n × k²) no total — muito pior do que os O(n × k) que eu havia afirmado.

A Solução Correta: Tuplas

Em Erlang/Elixir, a estrutura de dados com acesso indexado O(1) é a tupla ({}). A função elem/2 acessa um elemento em O(1), e put_elem/3 cria uma nova tupla com um elemento substituído (mas com custo O(k) por causa da cópia — mais sobre isso adiante).

# CORRETO: tupla com acesso O(1)
dp = {1, 0, 0, 0}          # tupla de tamanho 4
valor = elem(dp, 2)         # O(1)
nova_dp = put_elem(dp, 2, 5) # O(k) — copia a tupla inteira

Estratégia Eficiente: Reconstruir a Tupla Inteira por Linha

Como put_elem/3 é O(k), fazer k atualizações por linha seria O(k²) por linha. A estratégia eficiente é reconstruir a tupla inteira em uma única passada usando Enum.map seguido de List.to_tuple/1:

nova_dp =
  0..k
  |> Enum.map(fn j -> ... end)
  |> List.to_tuple()

Isso é O(k) por linha, resultando em O(n × k) no total.

Passo 5: Implementação Correta com Tuplas

defmodule Solution do
  @mod 1_000_000_007

  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    cond do
      k > n -> 0
      k == n -> 1
      true -> build_dp(n, k)
    end
  end

  defp build_dp(n, k) do
    # Linha inicial: i = 0 → dp[0] = 1, dp[j] = 0 para j > 0
    initial_dp =
      0..k
      |> Enum.map(fn j -> if j == 0, do: 1, else: 0 end)
      |> List.to_tuple()

    # Iterar de i = 1 até n, reconstruindo a tupla inteira a cada linha
    final_dp =
      Enum.reduce(1..n, initial_dp, fn i, dp ->
        max_j = min(i, k)

        0..k
        |> Enum.map(fn j ->
          cond do
            j == 0 -> 0
            j > max_j -> 0
            true -> (j * elem(dp, j) + elem(dp, j - 1)) |> rem(@mod)
          end
        end)
        |> List.to_tuple()
      end)

    elem(final_dp, k)
  end
end

Análise da Complexidade Corrigida

• Tempo: O(n × k) — para cada uma das n linhas, reconstruímos uma tupla de tamanho k+1 em O(k).
• Espaço: O(k) — mantemos apenas duas tuplas de tamanho k+1 por vez (a atual e a anterior).

Nota: A tupla em si ocupa O(k) espaço, mas como só mantemos duas por vez, o espaço auxiliar é O(k).

Traçando n = 4, k = 2

i	dp[0]	dp[1]	dp[2]
0	1	0	0
1	0	1	0
2	0	1	1
3	0	1	3
4	0	1	7

Resultado: elem(dp, 2) = 7 ✓

Passo 6: Alternativa com Mapa (Para Comparação)

Se preferir evitar tuplas, é possível usar um mapa com chaves inteiras. Map.put/3 e Map.get/3 são O(log k) em média, resultando em O(n × k × log k) no total — ligeiramente pior que a tupla, mas sem a necessidade de reconstruir a estrutura inteira.

defmodule Solution do
  @mod 1_000_000_007

  def ways_to_distribute(n, k) do
    cond do
      k > n -> 0
      k == n -> 1
      true -> build_dp_map(n, k)
    end
  end

  defp build_dp_map(n, k) do
    initial = %{0 => 1}

    final =
      Enum.reduce(1..n, initial, fn i, dp ->
        max_j = min(i, k)

        Enum.reduce(1..max_j, dp, fn j, acc ->
          valor = (j * Map.get(acc, j, 0) + Map.get(acc, j - 1, 0)) |> rem(@mod)
          Map.put(acc, j, valor)
        end)
      end)

    Map.get(final, k, 0)
  end
end

Comparação:

Estrutura	Acesso	Atualização	Tempo Total
Lista ([])	O(k)	O(k)	O(n × k²) ❌
Tupla ({})	O(1)	O(k) por put_elem, mas O(k) para reconstruir a linha inteira	O(n × k) ✅
Mapa (%{})	O(log k)	O(log k)	O(n × k × log k) ⚠️

Para k ≤ 1000, a tupla é a melhor escolha. Para k muito grande, o mapa pode ser competitivo.

Passo 7: Por Que a Ordem dos Sacos Não Importa?

Na recorrência S(n, k) = k × S(n-1, k) + S(n-1, k-1), o fator k representa a escolha de qual saco existente receberá o novo doce. A contagem final é independente da ordem porque cada partição é contada exatamente uma vez: o doce n é adicionado ao saco que já contém o menor elemento (em alguma ordenação implícita). Esse é um resultado clássico da combinatória.

Passo 8: A Conexão com os Números de Stirling

Os Números de Stirling de Segunda Espécie S(n, k) aparecem em:

1. Partições de conjuntos: partições de n elementos em k subconjuntos não vazios.
2. Funções sobrejetoras: k! × S(n, k) é o número de funções sobrejetoras de n para k elementos.
3. Momentos de distribuições: aparecem em momentos de Poisson e binomial.
4. Polinômios de Bell: são os coeficientes dos polinômios de Bell.

A fórmula explícita é:

S(n, k) = (1/k!) × Σ_{j=0}^{k} (-1)^j × C(k, j) × (k - j)^n

Mas a recorrência é muito mais eficiente para computação.

Passo 9: O Modelo Mental — Resumo

1. Reformule matematicamente: conte partições de um conjunto de n elementos em k subconjuntos não vazios.
2. Identifique a estrutura: são os Números de Stirling de Segunda Espécie.
3. Encontre a recorrência: S(n, k) = k × S(n-1, k) + S(n-1, k-1).
4. Escolha a estrutura de dados correta em Elixir: tuplas para acesso indexado O(1), não listas.
5. Implemente DP bottom-up: reconstrua a tupla inteira a cada linha para evitar O(k²).
6. Aplique o módulo: rem(10⁹ + 7) em cada passo.
7. Verifique com exemplos: trace os casos de teste dados.

Solução Completa em Elixir (Corrigida)

defmodule Solution do
  @mod 1_000_000_007

  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    cond do
      k > n -> 0
      k == n -> 1
      true -> build_dp(n, k)
    end
  end

  defp build_dp(n, k) do
    # Linha inicial: i = 0 → dp[0] = 1, dp[j] = 0 para j > 0
    # Usamos uma TUPLA, não uma lista!
    initial_dp =
      0..k
      |> Enum.map(fn j -> if j == 0, do: 1, else: 0 end)
      |> List.to_tuple()

    final_dp =
      Enum.reduce(1..n, initial_dp, fn i, dp ->
        max_j = min(i, k)

        # Reconstruímos a tupla inteira em uma passada — O(k)
        0..k
        |> Enum.map(fn j ->
          cond do
            j == 0 -> 0
            j > max_j -> 0
            true -> (j * elem(dp, j) + elem(dp, j - 1)) |> rem(@mod)
          end
        end)
        |> List.to_tuple()
      end)

    elem(final_dp, k)
  end
end

Traçando n = 4, k = 2:

• Inicial: {1, 0, 0}
• i=1: {0, 1, 0}
• i=2: {0, 1, 1}
• i=3: {0, 1, 3}
• i=4: {0, 1, 7}
• Resultado: 7 ✓

Por Que Esse Problema Importa

O problema Count Ways to Distribute Candies é uma porta de entrada para os Números de Stirling, que aparecem em teoria dos grafos, probabilidade, análise de algoritmos e física estatística.

A lição mais importante — e a que motivou esta correção — é que a escolha da estrutura de dados certa é tão importante quanto o algoritmo. Em linguagens imperativas, arrays são a escolha óbvia para DP indexado. Em Elixir, a escolha óbvia ([]) é uma linked list, e usá-la ingenuamente transforma um algoritmo O(n × k) em O(n × k²). A estrutura correta é a tupla, que oferece acesso indexado O(1) e pode ser reconstruída eficientemente em O(k) por linha.

Essa é uma armadilha comum para desenvolvedores vindos de linguagens imperativas, e reconhecê-la é um passo importante na maestria de Elixir. A regra prática é: se você precisa de acesso indexado O(1), use tuplas; se precisa de inserção/remoção no início, use listas; se precisa de chaves arbitrárias, use mapas.

Conclusão

Este artigo completou a jornada iniciada no problema anterior. Começamos com doces idênticos e crianças distintas, usando stars and bars e inclusão-exclusão para obter uma solução O(1). Agora, com doces únicos e sacos não vazios, usamos os Números de Stirling de Segunda Espécie e programação dinâmica com tuplas para obter uma solução O(n × k).

A correção sobre listas vs. tuplas é um lembrete valioso: em Elixir, a estrutura de dados que parece "natural" para quem vem de linguagens imperativas pode não ser a mais eficiente. Listas são ótimas para padrões de acesso sequencial (head/tail), mas péssimas para acesso indexado. Tuplas são o oposto. Escolher a ferramenta certa para o trabalho é a essência da programação eficiente.

---

Nota de verificação: A solução com tuplas foi testada contra a força bruta para todos os pares (n, k) com n ≤ 12, e validada para n = 20, k = 5 (resultado 206085257). A análise de complexidade foi corrigida para refletir o custo real das operações em listas e tuplas em Elixir.