Yield et programation récursive en python

Le problème exposé dans ce sujet a été résolu.

Bonjour,

Je tente un programme probablement tout bête, mais pour moi qui n’ai jamais travaillé concrètement sur des arbres, je me retrouves à faire des trucs bizarres avec des résultats innatendus.

Mon but : partant d’une liste de nombre, mettons [1, 2, 3], je veux toutes les combinaisons d’opérations élémentaires possibles de ces nombres. Oublions * et /, faisons juste + et -. Je veux donc 

1 + 2 + 3
1 + 2 - 3
1 - 2 + 3
1 - 2 - 3
...

Il faudra aussi faire toutes les permutation (car priorité d’opération avec * et /), mais je verrai ça pus tard. J’ai utilisé une fonction récursive et des yield, mais tout ne se passe pas comme prévu :

def combinaison(nb, ll_nb):
    """Fait les 4 opérations entre nb et le premier élemnt de ll_nb.
    Et itère."""
    print(nb, ll_nb)
    if len(ll_nb) == 1:
        yield [i for i in [nb + ll_nb[0]]]
        yield [i for i in [nb - ll_nb[0]]]
    else:
        yield [i for i in combinaison(nb + ll_nb[0], ll_nb[1:])]
        yield [i for i in combinaison(nb - ll_nb[0], ll_nb[1:])]

# Appel de la fonction avec gestion 
tous_les_nombres = []
for i in liste_nombre:
    ll_inter = liste_nombre.copy()
    ll_inter.remove(i)
    for j in combinaison(i, ll_inter.copy()):
        tous_les_nombres += j

print("Tous les nombre obtenus : ", tous_les_nombres)
## Tous les nombre obtenus :  [[6], [0], [2], [-4], [6], [0], [4], [-2], [6], [2], [4], [0]]

Je voudrai me débarrasser des listes. Faire un simple flat n’est pas suffisant, car dès que l’on a plus de nombres, j’ai des listes de listes de listes de…

J’imagine que j’ai mal fait mon truc, et que les yield [i for i in ... ] que j’ai ajouter pour forcer l’expression des générateurs peuvent être gérés autrement.

Une idée de la part de plus pytoniste que moi ?

Merci. :)

+0 -0

là comme ça je dirais que ça ne te sert à rien de yield des listes, les générateurs sont itérables en eux même.

ensuite il y a l’astuce du yield from qui te permet de faire un "flat" de ta liste pour reprendre ton besoin fonctionnel.

je dirais donc : 

def combinaison(nb, ll_nb):
    """Fait les 4 opérations entre nb et le premier élemnt de ll_nb.
    Et itère."""
    print(nb, ll_nb)
    if len(ll_nb) == 1:
        yield nb + ll_nb[0] # ici on ne génère qu'un seul nombre
        yield nb - ll_nb[0] #idem
    else:
        yield from  combinaison(nb + ll_nb[0], ll_nb[1:]) # ici on va déléguer la génération à l'appel récursif, mais du coup on a un générateur "plat" à la fin
        yield from combinaison(nb - ll_nb[0], ll_nb[1:]) # idem
+1 -0

j’étais en train de rédiger un exemple de run de mon code :

prenons l’exemple de nb = 1, ll_nb = [2, 4]

au premier passage on va appeler

  • yield from combinaison(1 + 2, [4])

    • ce qui va demander de générer combinaison(3, [4]) qui va donc passer dans le premier if
    • ce qui va générer 3+43 + 4 puis 3−43 - 4.

  • yield from combinaison(1 - 2, [4])

    • de la même manière qu’au dessus, on génèrera −1+4-1 + 4 puis −1−4-1 - 4.

Notons que j’ai trouvé un tuto sur un petit site francophone qui t’explique tout ça très bien.

+1 -0

Salut,

Ça me parait laborieux, à coup d'itertools on peut construire les permutations possibles sans se fatiguer

from itertools import combinations_with_replacement, permutations

from operator import add, sub, mul, truediv

numbers = [1, 2, 3]
operations = [add, sub, mul, truediv]

results = []

for lnbs in permutations(numbers):
    print(lnbs)  # every ways to take our three numbers
    for ops in combinations_with_replacement(operations, len(numbers) - 1):
        print(ops)  # every ways to pick two operations to apply
        pnum = lnbs[0]
        for num, op in zip(lnbs[1:], ops):
            pnum = op(pnum, num)
        results.append(pnum)

print(results)  # or set(results) to remove duplicates

On pourrait être plus sioux et enlever les permutations autour des opérateurs symétriques * et +. C’est pas compliqué, suffit de traiter les opérateurs symétriques séparément.

+4 -0

Merci du truc, @adri1. Je connais très mal itertools. Et je voulais comprendre pourquoi ce que je faisais ne se comportait pas comme je m’y attendais avant d’aller plus loin.

Merci à vous deux.

+0 -0

Bonjour,

Bien que ce fil soit marqué résolu j’ai une remarque à faire sur le code de adri1, ce code permet bien de trouver toutes les combinaisons mais le calcul est faux dans certains cas, le priorités ne sont respectées par exemple :

1 + 2 * 3 retourne 9 alors que ca devrait être 7.

from operator import add, sub, mul, truediv 
from itertools import permutations, combinations_with_replacement as repl 

OPER = {"+":add, "-":sub, "*":mul, "/":truediv}

def comb(lnb, lops):
   "Même fonction que celle de adri1, mais sans le calcul du résultat."
   for nbs in permutations(lnb):
       for ops in repl(lops, len(lnb)-1):
           res = [nbs[0]]
           for nb, op in zip(nbs[1:], ops):
               res.extend([op, nb])
           yield res

def calc(ops):
   "Calcul de chaque opération avec priorités pour * et /"
   if len(ops) == 3:
       n1, op, n2 = ops
       return OPER[op](n1, n2)
   if ('*' in ops) or ('/' in ops):
       try:
           i = ops.index('*')
       except ValueError:
           i = ops.index('/')
       nb = calc(ops[i-1:i+2])
       ops = ops[:max(i-1,0)] + [nb] + ops[i+2:]
       return calc(ops)
   else:
       ops = [calc(ops[:3])] + ops[3:]
       return calc(ops)

for ops in comb([1,2,3], ["+","*"]):
   res = calc(ops)
   print(' '.join(map(str, ops)),'=',res)
+0 -0

le priorités ne sont respectées

On s’en moque, c’est géré par les permutations. Ce que toi tu notes 1+2*3, je le note 2*3+1.

Par contre, ce que moi je note 1+2*3 en prenant une évaluation de gauche à droite est inaccessible à ton algorithme qui ne fera pas la différence avec 2*3+1 (alors que mathématiquement, calculer (1+2)*3 est bien une façon d’appliquer deux opérations élémentaires à un ensemble de trois nombres). Si vraiment le but de l’OP est ne pas pouvoir atteindre (1+2)*3 en aucun cas, la bonne façon de corriger est d’éliminer toutes les suites d’opérations qui ne sont pas équivalentes quand lues de gauche à droite ou dans l’ordre conventionnel (donc toutes celles où un + ou - se retrouve à gauche d’un * ou /). Les permutations se chargeront d’explorer les combinaisons possibles là où ton code va faire des doublons.

+0 -0

Les permutations renvoient des "doublons" donc à la fois 1+2*3 = 9 et 2*3+1 = 7 si on calcule sans tenir compte de priorités.

J’ai suivit ce mode de calcul parce que c’est ce que Gabbro semblait vouloir faire :

Il faudra aussi faire toutes les permutation (car priorité d’opération avec * et /)

+0 -0

Après réflexion, j’ai dit une connerie qui est masquée par la symétrie de +. La proposition de @kayou évalue 1-2*3 d’une façon inaccessible à mon algo. Si on veut respecter les priorités, il faut la jouer plus fine pour tenir compte de l’asymétrie de -. Une solution serait de construire l’ensemble des suites d’opérations qui sont identiques lues de gauche et droite ou bien avec les règles de priorités (donc avec les opérations de basse priorité à droite), mais de bien appliquer les opérations asymétriques comme - dans les deux sens lorsqu’on distribue par dessus l’ensemble des permutations des nombres de départs. C’est pas un problème si facile que je pensais au premier abord.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte