Quantas combinações para n pontos num jogo de basquete?

Question

Suponha que num jogo de basquete existem 3 movimentos que somam pontos, o movimento "A" vale 1 ponto, o movimento "B" vale dois pontos e o movimento "C" vale 3 pontos.

Como poderiamos escrever um código que contasse de quantas maneiras diferentes poderiamos atingir n pontos? Por exemplo, para 3 pontos as possibilidades são: AAA, AB, BA, C, ou seja, existem 4 possibilidades (note que a ordem importa)

Esse exercício está descrito no livro "Introduction to recursive programming" de Manuel Rubio Sanchez, de 2017 (exercício 8.3)

Answer 1

Uma maneira bem força bruta de resolver está abaixo. Note que em vez de calcular o número de possibilidades estamos devolvendo uma lista com cada uma das possibilidades, para contar as possibilidades é só contar os elementos da lista

 import itertools

def adiciona_permutacoes (lista):
    listao = []

    for i in range(len(lista)):

        for e in itertools.permutations(lista[i], len(lista[i])):
            aux = ''
            for j in range(len(e)):
                aux = aux + str(e[j])
            listao.append(aux)
    return listao


def number_of_ways(n,lista=[]):
    lista1 =['A']
    lista2 = ['AA', 'B']
    lista3 = ['AAA', 'BA', 'C', 'AB']
    if n==1: return lista1
    if n==2: return lista2
    if n==3: return lista3
    if n>3:
        for i in range(1,n-1):
            if i<=n-1:
                for a in range(i):
                    for b in range(n-i):
                        aux = number_of_ways(i)[a]+number_of_ways(n-i)[b]
                        lista.append(aux)
                        lista = list(set(lista)-set(number_of_ways(n-1)))
        return lista

if __name__=='__main__':

    # para n=6
    lista_com_permutações = list(set(adiciona_permutacoes(number_of_ways(6))))

    #para a contagem com n=6
    contagem = len(list(set(adiciona_permutacoes(number_of_ways(6)))))

    print(lista_com_permutações)
    print(contagem)

O resultado para alguns n selecionados segue abaixo

n=4
['AC', 'AAAA', 'ABA', 'AAB', 'BAA', 'CA', 'BB']

n=5
['CB', 'ABB', 'BBA', 'BC', 'BAB', 'AAAAA', 'BAAA', 'AABA', 'AAAB', 'ABAA']