Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Lettrage comptable automatique sur des écritures comptables


Sujet :

Algorithmes et structures de données

  1. #1
    Membre du Club
    Lettrage comptable automatique sur des écritures comptables
    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

  2. #2
    Membre à l'essai
    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/4632322/finding-all-possible-combinations-of-numbers-to-reach-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

  3. #3
    Membre confirmé
    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 [latex]{\cal O}(nlog(n))[/latex].

  4. #4
    Expert éminent sénior
    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)
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.