Bonjour à tous,je sollicite votre aide pour m'aider à rédiger une formule mathématique.

Cela me semblait simple de prime abord mais in fine je n'arrive pas à traduire ce que fait mon code sous la forme d'une formule simple.

L'idée est la suivante:

Mon code joue avec plusieurs matrices de colonnes E (noté de 0 à n) et de lignes P (de 0 à m).

J'ai donc parfois plus de lignes que de colonnes ou plus de colonnes que de lignes.

Néanmoins pour chaque matrice je recherche la combinatoire qui maximise le produit des valeurs EnPm.

Exemple de 3 lignes et 4 colonnes: mon code retrouve les 3 couples (car 3 lignes < 4 colonnes ) EnPm pour lesquels le produit des valeurs est le plus grand.

Si j'ai 4 lignes et 3 colonnes idem ce sera 3 couples pour lesquels le produit des valeurs est le plus grand.

Pour imager mon propos ce serais un peu comme emprunter un chemin en partant du plus grand côté d'un damier et de sauter de case en case jusqu'à atteindre la fin du damier puis on compte les points des cases parcourues et on retient le chemin avec le plus grand nombre de points.

J'essaye depuis quelque jours de le formuler via le symbole grand Pi (Fonctionnant comme Sigma mais pour faire des produits au lieu des sommes si j'ai bien tout compris) mais le problème est que je n'arrive pas à expliciter au sein de la formule le parcours à la fois des lignes et des colonnes pour former le couple.

Si vous avez des pistes pour m'aiguiller vers les éléments qu'il me manque pour me permettre de formulé ce que je décris plus haut en une formule simple ce serais magnifique.

Bonne journée à tous,

Unitjarl

Bonjour. Pourrais-tu décrire un exemple précis ? Parce que je ne comprends pas bien :

> Exemple de 3 lignes et 4 colonnes: mon code retrouve les 3 couples (car 3 lignes < 4 colonnes ) EnPm pour lesquels le produit des valeurs est le plus grand.

Il y a 12 couples possibles : E1P1, E1P2, E1P3, E1P4, E2P1, E2P2, E2P3, E2P4, E3P1, E3P2, E3P3, E3P4.

Tu cherches la plus grande valeur parmi ces 12 ? Apparemment non puisque tu dis qu'il y a 3 couples à retrouver. Au fait, tu cherches les couples (le résultat sera par exemple le couple (1,3)) ou bien la valeur du produit (le résultat sera alors E1.P3 = 6x4 = 24 par exemple) ?

> je recherche la combinatoire

C'est quoi une combinatoire ?

> ce serais un peu comme emprunter un chemin en partant du plus grand côté d'un damier

C'est pas carré, un damier ?

Si le but est de trouver le chemin avec le plus grand nombre de points, est-ce qu'on a droit de repasser par une même case ? Si oui, il n'y a pas de plus grande valeur possible (on peut toujours faire mieux).

------------------

Après réflexion, on dirait que tu cherches à maximiser la somme \( \sum_{i=1}^N E_iP_{k_i} \) pour les \( k_i \) appartenant à {1, ..., M}. Par exemple avec N=3 et M=4 il s'agirait de maximiser \( E_1P_{k_1} + E_2P_{k_2} + E_3P_{k_3} \) où les \(k_i\) appartiennent à {1, 2, 3, 4}. C'est ça ?

-
Edité par robun 17 mars 2020 à 13:35:35

Bonjour, Alors oui un damier c'est carré en effet et non pas les matrices que j'utilise mais je ne trouvais pas d'autres termes sur le coup. Je vais donc tenté de mieux détailler un autre exemple.

Alors voici deux matrices en exemple:

Les solutions sont en vert. L'idée est donc que la solution final est bornée par la plus petite taille de colonne où de lignes. Ainsi si j'ai 5 lignes et 9 colonnes j'obtiendrai donc 5 couples. Ce bornage est du au fait qu'une ligne et une colonne ne peuvent servir qu'une fois, j'avais passé sous silence ce point dans mon dernier message car je voulais aborder un cas général avant mon cas complexe.

Comment je trouve ma solution? En essayant toutes les combinaison de couples possible car mes matrices seront toujours limitées (pas plus de 10 E de manières générale et de 4 P).

Mon code liste donc toutes les combinaison de E_i;P_j (pour i allant de 1 à 4 dans le premier cas et j allant de 1 à 3) pour lesquels les index du couple suivant sont différents de l'ensemble des index des couples précédents.

Ici on a dans le premier et second cas (car c'est à chaque fois une matrice 4x3):

24 combinaisons possibles (4*3*2)

Ensuite je détermine la ou les meilleurs combinaison en gardant celle(s) qui maximise le produit des valeurs aux coordonnées E_i;P_j

En soit maximiser la somme ou le produit revient au même pour déterminer quels sont les meilleurs coordonnées mais j'utilise également la valeur obtenue par le produit ultérieurement voilà pourquoi je parlais de maximiser un produit.

J'espère avoir été plus clair avec cette exemple.

En soit ce que je n'arrive pas a écrire c'est le parcours des E et des P dans une formule impliquant grand Pi

J'ai imaginé de l'écrire comme suit mais je suis a peu près sur que ça ne doit pas s'écrire ainsi:

Bonne journée,

Unitjarl

Si c'est le produit que tu maximises, il reste encore à exprimer que les numéros de colonnes (ou de lignes, selon les cas) doivent être tous distincts.

On pourrait peut-être écrire quelque chose comme ça :

Premier cas : le nombre de lignes (les Pi) est <= au nombre de colonnes (les Ej) - comme sur le premier schéma, sauf que je nomme i les lignes et j les colonnes.

\(  \Pi_{i=1}^n P_i E_{j_k} \)

où les \( j_k \) sont des nombres entre 1 et m (le nombre de colonnes) tous distincts entre eux.

Deuxième cas : le nombre de colonnes (les Ei) est <= au nombre de lignes (les Pj) - comme sur le deuxième schéma.

\(  \Pi_{i=1}^m E_i P_{j_k} \)

où les \( j_k \) sont des nombres entre 1 et n (le nombre de lignes) tous distincts entre eux.

-
Edité par robun 18 mars 2020 à 20:08:53

On va supposer que le nombres de colonnes m est supérieur au nombre de lignes n . On cherche le maximum pour toutes les injections de [1, n] dans [1, m] du produit pour i allant de 1 à n des P_i E_{f(i)}. Si on note E l'ensemble [1, n], F l'ensemble [1, m] et I(E, F) l'ensemble des injections de E dans F, on cherche

\[
   \max_{f \in I(E, J)} \prod_{i = 1}^n P_i E_{f(i)}.
\]

-
Edité par yo@n97one 18 mars 2020 à 13:38:08

Merci beaucoup pour vos réponses.

Je ne comprend pas bien le terme injection dans la proposition de yo@n97one, ce que je comprend de cette formule c'est qu'on maximise les produits des valeurs de la variable P_i E_f(i) avec i allant de 1 à n et permettant de définir que l'on prend une ligne P_i et une colonne E et là je ne comprend plus bien malgré l'aide textuelle. Petit f est une fonction? un ensemble de 1 à m? un ensemble de 1 à m mais limité par le fait que cette ensemble doit appartenir à l'injection?

Une chose que robun met parfaitement en avant c'est que plutôt que d’essayé de tout mettre de force dans une formule je devrais plutôt explicité que j'ai bien deux cas distinct à savoir nombre de colonnes >= nombre de lignes et nombre de lignes > nombre de colonnes. Je le fait moi même dans le code pour savoir à partir de quel index (le plus petit) je démarre le parcours de mes listes.

Encore merci pour vos explications et votre aide

Bonne journée,

Unitjarl

f est une fonction qui à un entier entre 1 et n (un numéro de ligne) associe un entier entre 1 et m (un numéro de colonnes). Ainsi, pour chaque numéro de ligne i, f(i) est le numéro de colonnes de la case qu'on prend pour cette ligne i. Mais on ne peut pas prendre toutes les fonctions, il ne faut considérer que celles qui n'associent pas le même numéro de colonnes à deux lignes différentes. Une telle fonction est appelée une injection. On parcourt donc toutes les injections et on prend celle qui donne le maximum.

Je n'ai donné que le cas où le nombre de lignes était inférieur car l'autre cas est tout à fait symétrique, cette fois on prend les injections de l'ensemble des entiers entre 1 et m dans l'ensemble des entiers entre 1 et n (c'est-à-dire les injections de F dans E) et les produits qu'on a sont les P_{f(i)}E_i (le numéro de colonnes et la ligne de la case qu'on choisit à cette colonne) :

\[ \max{f \in I(F, E)} \prod{i = 1}^m P{f(i)} E{i}. \]

Mais pourquoi cherches-tu une telle formule ? La réponse à cette question nous aidera t'aiguiller vers ce qu'il te faut vraiment.

Bonjour yo@n97one et merci pour cette explication très pédagogique.

Au vue de ce que tu m'expliques la fonction est en parfaite adéquation avec ce que je cherche à faire.

Je travaille sur un projet qui permet d'établir la probabilité d'obtenir un élément X à partir d'éléments parents (les lignes P) ces parents sont transformés par des éléments (E) et cette formule à pour but de dispatché les éléments disponibles sur les parents disponibles tu en maximisant la probabilité de X.

Je fais donc des couples parent-éléments en considérant qu'une fois qu'un élément est recrutée pour transformer un parent elle n'est plus disponible pour les autres parents. L'inverse est vrai un parent ne peut pas être transformé par plus d'un élément.

Les valeurs des couples représente la probabilité d'obtenir X avec un élément et un parent donné. Enfin je maximise la valeur des produit pour obtenir la ou les combinaisons parent-éléments qui permet/permettent d'avoir un maximum de chance d'obtenir X.

J'ai rédiger mes scripts, testé des toy_exemples pour être sur que mon code ne fais pas n'importe quoi mais il me faut maintenant rédiger plus clairement ce qu'il fait et pour cela je trouvais qu'une formule mathématique décrivant la mécanique de calcul qui me permet d'avoir la probabilité d'obtenir X était plus justifié qu'un long paragraphe probablement pas très clair (d'ailleurs mon premier message du topic le montre).

Merci beaucoup à chacun d'entre vous pour votre aide.

Bonne journée,

Unitjarl

Avec cette grille, tu vas retenir quoi ?

10  12  13  30
11  15  16  25
14  10  18  20

tbc92

Je retiendrai P2E2; P3E3 et P1E4 (15*18*30 = 8100)