Obtenir une somme fixée

Tu peux utiliser la classe decimal pour utiliser des nombres décimaux.

>>> from decimal import Decimal
>>> Decimal("1.2")
Decimal('1.2')
>>> Decimal(1.2)
Decimal('1.1999999999999999555910790149937383830547332763671875')
>>> Decimal(1.2+1.4)
Decimal('2.5999999999999996447286321199499070644378662109375')
>>> Decimal("1.2+1.4")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
decimal.InvalidOperation: [<class 'decimal.ConversionSyntax'>]
>>> Decimal("1.2")+Decimal("1.4")
Decimal('2.6')

Est-ce que tu as 3 ou 4 jeux de données à proposer ?

Por moi, l'astuce serait de commencer par les exposants $p_k$ les plus élevés, ou par les plus bas ; je n'arrive pas à me décider !

Si tu dois reconstiter le nombre 1,2345 à partir d'entiers, avec $p_k$ limité à 4 , il n'y a pas des tonnes de façons d'obtenir le 5 final ; Pour chacune de ces solutions, on va ensuite chercher à obtenir le 4 en avant dernière position etc

Donc même si l'arbre qu'il faut parcourir est énorme, dans les faits, il y a des tas de branches qui s'avèrent tout de suite inutiles.

Sauf erreur de ma part, il doit être possible de travailler uniquement avec des entiers en multipliant $S$ par une puissance de 10. (Ah, bah, je viens de voir que tu l'avais dit dès le post initial).

Ensuite, clairement, la récursivité convient bien, et puisque on somme uniquement des entiers positifs, il y a moyen d'élaguer pas mal de branches.
On doit pouvoir aussi procéder par programmation dynamique, ou simplement par mémoïsation.

JP nl a écrit:

(avec 10 sortes de crottes en chocolats, combien de ballotins possibles, le ballotin contenant N crottes, c'est bien ça ?)

Euh c'est plutôt 10 boîtes et 5 crottes. 3 exemples de répartitions possibles :
(0 0 0 0 1 0 0 0 2 2)
(0 1 0 1 0 1 0 1 0 1)
(5 0 0 0 0 0 0 0 0 0)

À la relecture, je m'aperçois que ce n'est pas $\Gamma_{N}^{10}$, mais $\displaystyle \sum_{i=0}^{N} \Gamma_{i}^{10}$.

Nous sommes d'accord ;-).

En fait, en corrigeant mon précédent message, je me suis rendu compte que mon algorithme ne répondait pas à la demande d'exhaustion des cas car pour une même liste de n_i, il peut y avoir plusieurs listes de p_i (et réciproquement, d'ailleurs).

Pour y remédier, le moyen le plus simple est de changer la nature de la réponse en une liste de couples de tuples...
Voici donc la deuxième version :

def somme_fixe2(A: list[int], S: int, P: int, N: int) -> dict:
    """Cherche s'il existe une liste (p_1, ..., p_q) et une liste (n_1,...,n_q)
    d'entiers tels que sum(n_k * a_k * 10^(P-p_k), k=1..q) = S avec les contraintes
    n_1 + ... + n_q <= N et (p_1, ..., p_q) <= P.
    Renvoie une liste de couples formés des tuples (n_1, ..., n_q)
    et (p_1, ..., p_q)."""

    if S < 0 or S >= 10**(P+1):
        return []

    if len(A) == 0:
        return [] if S !=0 else [((), ())]

    a0 = A[0]
    sols = []
    for p in range(P+1):
        for n in range(N+1):
            sol_prev = somme_fixe2(A[1:], S - n * a0 * 10**(P-p), P, N-n)
            for n_list, p_list in sol_prev:
                sols.append(((n, *n_list), (p, *p_list)))
    return sols

Ainsi, cette fois-ci :

somme_fixe2([3,1,4,1], 3141, 3, 8)

renvoie

[((1, 1, 1, 1), (0, 1, 2, 3)), ((1, 2, 3, 1), (0, 2, 2, 3)), ((1, 1, 1, 1), (0, 3, 2, 1)), ((1, 1, 3, 2), (0, 3, 2, 2)), ((2, 3, 2, 1), (2, 0, 2, 3)), ((2, 1, 2, 3), (2, 3, 2, 0))]

On voit en particulier que le tuple (1,1,1,1) de n_i est associé à deux couples de p_i : (0,1,2,3) et (0,3,2,1), ce qui est logique puisque les a_i correspondants sont égaux.

La première méthode a l'avantage d'éviter les multiplicités en les écrasant au fur et à mesure, mais elle peut rater des cas.

Ça se complique sévèrement. À l'heure actuelle, j'opterais pour un algorithme dont le fil rouge serait la baisse du premier chiffre (en partant de S). Si on arrive à zéro en N étapes, c'est gagné.

Exemple : atteindre 22258 avec [111; 3; 14] demande l'étude de 3 sous-cas : 11158, 19258, et 8258. Et on recommence. Etc.
Notez que baisser de 14 descend plus vite que baisser de 111. :-)

Par défaut, les versions de Python classiques ont une profondeur de récursion assez élevée.
Je viens de faire le test avec un script tout bête et j'ai obtenu 989.

def recur(n):
    try:
        return recur(n+1)
    except:
        return n

Tu lances le test avec "recur(0)" et le nombre renvoyé est la profondeur de récursion.

Puisque tu voulais te limiter à de petites valeurs de N, et si ton algorithme diminue strictement N à chaque étape, tu n'auras aucun problème... mais si je ne m'abuse, N ne diminue pas strictement...

Effectivement, la limite de récursion de Python est fixée par défaut à 1000, mais au moment d'un test, elle dépend de l'état de la pile d'exécution au moment du lancement du script. Visiblement, Pyzo ajoute une couche d'exécution d'une dizaine d'étages de profondeur...

J'ai réussi à m'en sortir tout de même :

def somme_fixe3(A: list[int], S: int, P: int, N: int) -> dict:
    """Cherche s'il existe une liste (p_1, ..., p_q) et une liste (n_1,...,n_q)
    d'entiers tels que sum(n_k * a_k * 10^(P-p_k), k=1..q) = S avec les contraintes
    n_1 + ... + n_q <= N et (p_1, ..., p_q) <= P,
    en répétant éventuellement les éléments de la liste A.
    Renvoie un ensemble de tuples con tenant des couples qui à chaque valeur de A 
    associent la somme des coefficients n_k*10**(P-p_k) correspondants."""

    if S < 0:
        return set()

    if N == 0:
        if S !=0:
            return set()
        return {tuple((a, 0) for a in A)}

    sols = set()
    for n in range(1, N+1):
        for p in range(P+1):
            multi = n * 10**(P-p)
            for a in [0] + A:
                sols_prev = somme_fixe3(A, S - a * multi, P, N-n)
                for sol in sols_prev:
                    d = dict(sol)
                    if a in d:
                        d[a] += multi
                    elif a!= 0:
                        d[a] = multi
                    sols.add(tuple((k, d[k]) for k in d))
    return sols

Cette fois, on renvoie directement un ensemble de solutions (pour éviter de répéter plusieurs fois la même), chacune des solutions étant sous la forme d'un tuple de couples. J'aurais préféré renvoyer un ensemble de dictionnaires, mais les dictionnaires ne sont pas hashables.

Ainsi, les trois essais

somme_fixe3([111, 3, 14], 111*200 + 3*10 + 14*2, 3, 5)

somme_fixe3([111, 3], 111*101 + 3*10, 3, 4)

somme_fixe3([11, 3, 14], 473, 3, 7)

renvoient respectivement les 3 résultats

{((111, 200), (3, 10), (14, 2))}

{((111, 101), (3, 10))}

{((11, 13), (3, 110), (14, 0)), ((11, 10), (3, 121), (14, 0)), ((11, 0), (3, 111), (14, 10)), ((11, 40), (3, 11), (14, 0)), ((11, 43), (3, 0), (14, 0)), ((11, 1), (3, 0), (14, 33)), ((11, 30), (3, 1), (14, 10)), ((11, 3), (3, 100), (14, 10))}

.

On doit pouvoir faire encore plus efficace avec des résolutions d'équations diophantiennes... mais je n'ai pas encore cherché dans cette voie, car si elle est sûrement plus efficace sur de grandes valeurs de N, elle est bien plus pénible à écrire !

Voici le code corrigé :

def sommeCoef(A, N, P, score, liste=None):
    if liste is None:
        liste = []
    if score < 0 :
        return False
    if N >= 0 :
        if score == 0 :
            print(liste)
            return True
        else :
            for elem in A :
                for k in range(P+1) :
                    test = sommeCoef(A, N-1, k, score - elem * 10**k, liste + [[k,elem]])
                    if test :
                        liste.append([k, elem])

On ajoute un argument "liste" à la fonction qui sera modifié par effet de bord à l'exécution de la fonction.

Pour ne pas avoir besoin de le spécifier dans l'appel au départ., on donne une valeur par défaut à "liste"... mais une subtilité veut qu'on ne peut pas l'initialiser avec une liste vide car ce serait la même liste utilisée à tous les appels de la fonction puisque l'instanciation de la valeur par défaut se fait au moment de la création de la fonction et non à son exécution. L'astuce consiste à donner une valeur fixe (et impossible à obtenir autrement) par défaut et à tester à l'exécution si la valeur de la liste est cette valeur par défaut. Cela donne les deux premières lignes.

Ensuite, tu avait une erreur en renvoyant "test" à la fin de ta boucle : je l'ai supprimé. Une autre erreur était que tu mettais "A" au lieu de "elem" dans tes listes.

Pour finir, il suffit de faire l'appel récursif en adjoignant à la liste le couple [k, elem].


Le problème de cette méthode c'est que tu fais afficher les différentes solutions mais tu ne peux pas les réutiliser dans une autre fonction car elles ne sont pas renvoyées.

Pour comprendre mes messages précédents, petite explication sur les types de base de Python :

• les 'set' représentent des ensembles, au sens mathématique. On les entoure avec des accolades, comme en maths. Ils ne contiennent que des objets non mutables et par définition ne peuvent contenir qu'un seul exemplaire de chaque objet. Ils possèdent les méthodes usuelles mathématiques sur les ensembles (union, intersection, différence, etc.)
• les 'tuple' sont des listes non mutables. On les entoure avec des parenthèses au lieu des crochets. Ils peuvent néanmoins contenir des objets mutables.
• les 'dict' sont des dictionnaires qui à des clés (non mutables) associent des valeurs (mutables ou non). C'est une sorte d'intermédiaire entre une liste (dont les clés seraient les indices) et une fonction (dont les valeurs sont calculées plutôt que stockées).

Pour en savoir plus, évidemment, suivre un cours basique de Python devrait aider...