Discussion :

[nico1492]

Bonjour à toutes et tous,


Petite question postée en conséquence de l'absence de résultats de recherche vraiment fiables ici ou ailleurs...

J'élabore actuellement un programme qui doit, sur la base d'un listing d'écritures comptables pour un client donné, rapprocher les écritures entre elles par montant afin de les lettrer (règles connues du lettrage comptable, rien de plus, mais de façon automatisée)

Lorsque les relations se font en 1 pour 1, aucun problème : 100 euros au débit rapprochés de 100 euros au crédit = match = lettrage.
Sauf que potentiellement bien entendu, il y a N écritures au crédit à rapprocher avec N écritures au débit. Par exemple :

Débit	Crédit
50
50
50
	100
	50
200

Cette liste pourrait donner lieu au lettrage de toutes les lignes sauf la dernière qui ne serait pas considérée (150 d'un côté, 150 de l'autre)
Les combinaisons n'auraient pas de priorité, peu importe ce qu'on lettre du moment qu'on a l'équilibre.

J'ai lu un peu de littérature d'algo, dont celle du "Knapsack problem" mais elle ne me semble pas appropriée car là l'idée c'est bien d'avoir un match complet.

Avez-vous déjà été confrontés à la question ? Des suggestions ? Des snippets de code ou d'algo ?

Merci pour vos suggestions

[mp5696]

Salut,

Alors je ne suis ni expert en algo ni du problème mais je me suis amusé a y réfléchir un peu ce matin donc je pense qu'il doit y a voir bien mieux que cette solution. Si j'ai bien compris le but est de trouver une combinaison optimale (selon des critères que tu choisis : le moins de valeurs par ex.) des valeurs de débit qui en somme est égale a la somme des crédits ?

Il y a ce forum https://stackoverflow.com/questions/...ch-a-given-sum
Qui je pense répond a ta question en adaptant un peu.

Peut être qu'en enlevant préalablement les matchs "parfaits" (1 pour 1) comme ci dessous tu peux gagner du temps de calcul:

- Ordonner les listes si possibles.
- Trouver les relations en 1 pour 1, les "lettrer" (même si je ne sais pas ce que ça veut dire ahha) puis les enlever des datasets pour n'avoir plus que les valeurs restantes. (dans ton exemple on enlèverait un 50 de chaque colonne).
-Calculer la somme des débits restants (dans l'exemple 100 car le 50 a été enlevé)
- Trouver la combinaison dont tu as besoin avec les valeurs restantes (méthodes proposées dans le lien ci dessus). (Ici 50+50 car toutes les autres combinaisons sont > à 100)


En espérant avoir été clair et que ça t'aide un peu

[balkany]

Il me semble que, une fois que tu as calculé laquelle de tes deux colonnes a la plus petite somme, tu es ramené à résoudre pour l'autre le problème de trouver un sous-tableau ayant une somme donnée, et cela de manière non contiguë.
Voici un lien qui explique comment faire : https://fizzbuzzer.com/maximum-conti...ray-challenge/

La partie non contiguë est en seconde section, avec donc une complexité en .

[Flodelarab]

Bonjour

Lettrer, c'est donner du sens. Ce qui ne semble pas être le but de ta quête.

• Soit tu sais les lignes à exclure, et c'est un problème de granularité: "Quel sont les associations les plus petites possibles ?". Sinon, tu donnerais la lettre A à tous les débits, et la lettre A à tous les crédits.
• Soit tu ne sais pas les lignes à exclure, et il faut les chercher. Ma suggestion est de chercher les groupes stables, de proche en proche. Groupe avec 1 élément, puis 2, puis 3, puis ...

Peux-tu préciser ton but ? (en considérant ce que je viens de dire)

[nico1492]

Merci pour vos réponses et mes excuses pour mon absence sur ce sujet une fois posté, même si j'avais pris connaissance de vos réponses. Même si je comprends bien l'esprit du lettrage, j' en sais quelque chose, il m'avait été explicitement demandé de rapprocher les montants de la sorte. J'ai pu monter un algo qui s'est inspiré de ce que je racontais et des quelques réponses ici.

Merci encore