Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Mais aussi sur les technos front comme React, Angular, Typescript et Javascript en général.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Qqun peut il m'expliquer ce code de rapprochement bancaire

+2 votes

je ne comprends pas comment cela fonctionne

liste = [80.00, 115.00, 70.98, 170.00, 46.00, 12.00, 46.45, 134.39]
resultat = 557.39

def subset(array, somme):
    result = []

    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        # else:
        find(arr[1:], num - arr[0], path + (arr[0],))
        find(arr[1:], num, path)

    find(array, somme)

    return result

list_result = subset(liste, resultat)

print(len(list_result), " --- ", list_result)
demandé 30-Avr par bidochon (146 points)
edité 2-Mai par foxmask

Un peu de contexte svp. Où a été pêché cet algo ? Quels résultats obtient-on en le lançant, et que doit-on interpréter ?

le contexte
c'est pour faire du rapprochement bancaire,
retrouver dans la listes tous les éléments dont la somme, fait le résultat.

2 Réponses

+4 votes
 
Meilleure réponse

Spécification

Sachant un ensemble E de nombres réels et un nombre réel t, trouver les sous-ensembles S de E tel que sum(S) == t.

Dans l'univers merveilleux des mathématiques qui ont déjà tout formalisé, il s'agit d'une variante du subset sum problem, où la valeur finale n'est pas zéro (mais ça revient strictement au même).

swine

Ici, on s'intéresse à l'implémentation de la résolution du problème, qui est connu pour être NP-complet. Youpie.

Modélisation

Le problème peut être vu comme un arbre, où les nœuds sont les valeurs de X, et où un chemin de la racine à une feuille est un sous-ensemble de X.

Trouver toutes les combinaisons de sous-ensembles répondant au problème consiste donc à explorer les branches de l'arbre jusqu'à trouver une feuille dont la somme de tous les nœuds dans le chemin jusqu'à la racine est égal à t.

Or, un arbre étant une structure récursive, on peut imaginer une solution récursive au problème.

Implémentation récursive

Le principe est le suivant : on visite chacun des nœuds du graphe sachant :

  • la somme atteinte actuelle (num dans le code)
  • les valeurs qui n'ont pas encore été utilisées (arr dans le code)
  • les valeurs qui ont été utilisées pour atteindre la somme num actuelle (path dans le code ; il s'agit bien d'un chemin depuis la racine dans l'arbre)

On sait alors, quelque soit le nœud considéré, que :

  • si num est égale à T, alors un sous-ensemble (chemin) valide a été trouvé
  • il n'existe que deux possibilités : soit on prend le nœud, soit on le prend pas. Les deux cas sont possibles et non-exclusifs (donc deux appels récursifs dans tous les cas).

On en déduit qu'il va falloir :

  • accumuler les sous-ensembles (chemin) valides
  • pour chaque nœuds, considérer le cas où il est dans le sous-ensemble en cours de construction, et le cas où il ne l'est pas.

Suit une petite réécriture du code de l'OP, avec quelques annotations, qui implémente la solution comme on vient de le décrire :

def subsets_sums(values, total):
    """Return subsets of `values` so that sum of elements equals `total`"""
    subsets = []

    def find(arr, num, path=()):  # fonction appliquée à chaque nœud
        if not arr:
            return

        head, *tail = arr
        if head == num:  # on a atteint la valeur: on ajoute le chemin aux sous-ensembles valides
            subsets.append(path + (head,))

        # NB: cf remarque sur l'élagage pour l'optimisation du code
        find(tail, num - head, path + (head,))  # cas où on utilise le nombre
        find(tail, num, path)  # cas où on n'utilise pas le nombre

    find(values, total)  # on peuple la liste subsets…
    return subsets  # … et on la renvoie

On peut l'utiliser sur un cas d'exemple un peu moins bourrin que le code de l'OP :

expected_sum = 11  # on veut les sous-ensembles qui atteignent ça
availables = [1, 2, 3, 5, 11, 7]  # on veut des sous-ensembles de ça
subsets = subsets_sums(availables, expected_sum)

for solution in subsets:  # on les affiche propremment
    print(' + '.join(map(str, solution)) + ' == ' + str(expected_sum))
    assert sum(solution) == expected_sum

Qui nous renvoie :

1 + 2 + 3 + 5 == 11
1 + 3 + 7 == 11
11 == 11

Note : l'implémentation fonctionne avec tous les nombres réels, comprenant donc les nombres négatifs et flottants, et les doublons (testez en rajoutant un 11 dans availables).

Complexité & Optimisations

En m'appuyant sur ce post, je peux affirmer que la complexité de cet algorithme récursif est exponentiel (lire : c'est très mauvais). La bonne nouvelle, c'est que de toute façon le problème est NP-complet, donc faire mieux dans tous les cas, c'est pas encore possible, mais ça rapporte un million de dollars (ce qui est un peu du foutage de gueule vu l'importance du problème, mais bon, les maths ça rapporte pas).

Cela dit, l'algorithme présenté, s'il n'est pas optimal, peut être rendu un poil plus efficace en remarquant que, lorsqu'il n'y a que des nombres positifs (négatifs), si la somme courante num est supérieure (inférieure) au total visé, alors les appels récursifs sont inutiles, puisqu'ils exploreront des solutions qui de toute façon seront toutes supérieures (inférieures) au total visé.

Pour exploiter ça, on pourrait détecter si tous les nombres sont positifs (et non-nuls) :

if any(number <= 0 for number in values):
    # turn on optimization

Mais c'est un peu nul, dans le sens où il faut implémenter l'optimisation inverse (tous les nombres sont négatifs). Donc, la solution ultime dans ce genre de cas, qui est utilisée dans tous les problèmes du monde, du subset sum problem au parcours de dijkstra : un offset de valeur.

# on calcule et on ajoute l'offset à toutes les valeurs
offset = 1 + min(values)
values = [value + offset for value in values]

...  # application de l'algorithme

# on enlève l'offset à toutes les valeurs
subsets = [[value - offset for value in subset] for subset in subsets]
return subsets

Et voilà, on sait maintenant que, pendant l'exploration de l'arbre, on ne possède que des valeurs positives, donc on peut élaguer joyeusement :

if num <= total:
    find(tail, num - head, path + (head,))  # cas où on utilise le nombre
    find(tail, num, path)  # cas où on n'utilise pas le nombre
else:
    pass  # ya rien à faire, puisqu'on arrivera jamais à descendre jusqu'au total

Autres implémentations

On pourrait utiliser itertools.combinations et un peu d'intensions :

import itertools

def subsets_sums(numbers, total):
    return (
        subset
        for len_subset in range(1, len(numbers) + 1)
        for subset in itertools.combinations(numbers, r=len_subset)
        if sum(subset) == total
    )

On le teste avec le code de tout à l'heure :

subsets = subsets_sums(availables, expected_sum)

for solution in subsets:  # on les affiche propremment
    print(' + '.join(map(str, solution)) + ' == ' + str(expected_sum))
    assert sum(solution) == expected_sum

Qui nous renvoie exactement le même résultat (pas dans le même ordre, mais on s'en fiche) :

11 == 11
1 + 3 + 7 == 11
1 + 2 + 3 + 5 == 11

L'avantage de cette deuxième méthode, c'est l'économie mémoire considérable comparée à la solution récursive, car ici, merci les générateurs, à aucun moment la totalité de l'espace de recherche n'est stockée en mémoire. Et en plus, ce n'est plus du récursif, donc python est content.
L'inconvénient, c'est que les optimisations comme l'élaguage décrit plus haut ne sont pas implémentées, ni implémentables sans réimplémenter itertools.combinations et faire des coroutines. C'est rigolo, mais c'est pas trop le sujet.

Un autre détail : les solutions sont générées au fur et à mesure de la recherche (comprendre : c'est un générateur). C'est pas impossible de l'implémenter avec la méthode récursive, mais dans ce cas là, c'est automatique.

On pourrait aussi utiliser des solveurs proposant des heuristiques dédiées aux problèmes NP-complets.
Par exemple ici en ASP.

limite de 8000 caractères atteinte, je continue en commentaire

répondu 30-Avr par lucas (2,044 points)
sélectionné 6-Mai par bidochon

Benchmarks

Pour la gloire, j'ai testé jusqu'à quand j'arrivais à faire péter ma mémoire avec la solution récursive :

import random
numbers = tuple(random.randint(1, 100) for _ in range(100000))
print(len(subsets_sums(numbers, 200)))  # RecursionError

Il a fallu augmenter la taille de la stack, sinon la récursivité passait point :

import sys
sys.setrecursionlimit(10000)  # fini sur un segfault (parce que c'est un hack dégueux)

Le temps de calcul est monstrueux, et la RAM est très vite peuplée. Cependant, on arrive vite à la limite de l'augmentation de la stack, donc difficile d'avoir un benchmark parfait à ce sujet.

Pour la méthode non récursive, par contre, le temps de calcul est toujours aussi gargantuesque, mais on a plus de problème de segfault ou de limite de récursion. Donc on peut potentiellement faire chauffer sa chambre en attendant les résultats, sans risque de baisse de température ou de segfault à cause de la stack ou du manque de RAM.

Encore des liens

Un grand merci
j'ai toujours hésité, à poster des demandes,
mais je m'aperçois qu'il y as des gens passionnés et altruistes
cela fais plaisir

Pense à accepter la réponse si elle te convient ;)

(en cliquant sur la coche verte en dessous du score de la réponse)

en y réfléchissant, si tous les chiffres sont positifs, on peut pour le coup, supprimer tous les chiffres dont l'addition, avec le chiffre le plus petit, soit plus grand que le résultat attendu,
ou que le chiffre lui même soit plus grand que le total

listevalues = [3, 5, 5, 6, 7.89, 4.84, 19.61, 5.96, 10, 9.71, 1.05, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]
total = 19.71
liste = [x for x in liste
atravailler if min(listevalues) + x <= total]

Effectivement, c'est un bon moyen de gagner du temps. À condition que la cible à atteindre soit du même ordre de grandeur que les valeurs de la liste, sinon on pourrait perdre plus de temps qu'on en gagne.

Il y a certainement plus à creuser, par exemple en regardant à partir de combien de valeurs choisies on est forcément au dessus de la cible, ça permet de limiter de manière conséquente la taille de l'arbre.

0 votes

oui mais on repart forcement dans ce cas dans la recursivité non?

répondu 3-Mai par bidochon (146 points)
...