Escreva uma função recursiva que gere todas as possíveis combinações para um jogo da MegaSena com 6 dezenas
Passo 1
O problema pede uma função recursiva que gere todas as combinações de
dezenas distintas escolhidas dentre os números de
a
(MegaSena). O conteúdo principal aqui é backtracking ou geração de combinações via recursão, mantendo uma lista temporária com a combinação atual e avançando até ter
elementos.
Passo 2
A ideia é percorrer sequencialmente a lista de números disponíveis, numa chamada recursiva que:
. Adiciona o número atual à combinação temporária.
. Se a combinação temporária atingir tamanho
, copia-a ao resultado.
. Caso contrário, faz recursão a partir do próximo índice.
. Após voltar da recursão, remove o último número (backtracking) e continua com o próximo.
Passo 3
Definimos:
source
: lista de inteiros dea . k
: tamanho da combinação (aqui\(6\)
).comb
: lista temporária que armazena a combinação em construção.resultado
: lista que acumula todas as combinações finais.- A função interna
backtrack(start)
tenta incluir cada elemento de índicei
emcomb
, comi
variando destart
até o final desource
.
Passo 4
A implementação em Python fica assim:
def \(gerar_combinacoes\)(source, k):
resultado \(=\) []
comb \(=\) []
def backtrack(start):
# Se atingimos k elementos, gravamos uma cópia da combinação
if len(comb) \(==\) k:
resultado.append(comb.copy())
return
# Tentar cada índice a partir de 'start'
for i in range(start, len(source)):
comb.append(source[i])
backtrack(i \(+1\))
comb.pop() # desfaz a escolha para tentar o próximo
backtrack(\(0\))
return resultado
# Exemplo de uso:
numeros \(=\) list(range(\(1\), \(61\)))
combinacoes \(= gerar_combinacoes\)(numeros, \(6\))
# Isso produzirá uma lista com C(\(60,6\)) combinações
Resposta
def \(gerar_combinacoes\)(source, k):
resultado \(=\) []
comb \(=\) []
def backtrack(start):
if len(comb) \(==\) k:
resultado.append(comb.copy())
return
for i in range(start, len(source)):
comb.append(source[i])
backtrack(i \(+1\))
comb.pop()
backtrack(\(0\))
return resultado
# Para MegaSena:
numeros \(=\) list(range(\(1\), \(61\)))
combinacoes \(= gerar_combinacoes\)(numeros, \(6\))