Logique entre 2 colonnes
Fermé
Help-Me-Please
-
19 mars 2016 à 10:37
Guillermo93 Messages postés 9 Date d'inscription samedi 19 mars 2016 Statut Membre Dernière intervention 28 avril 2016 - 23 mars 2016 à 21:42
Guillermo93 Messages postés 9 Date d'inscription samedi 19 mars 2016 Statut Membre Dernière intervention 28 avril 2016 - 23 mars 2016 à 21:42
A voir également:
- Logique entre 2 colonnes
- Supercopier 2 - Télécharger - Gestion de fichiers
- Word 2 colonnes - Guide
- Fusionner 2 colonnes excel - Guide
- 2 comptes whatsapp - Guide
- Classer par ordre alphabétique excel plusieurs colonnes - Guide
4 réponses
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
857
21 mars 2016 à 07:08
21 mars 2016 à 07:08
Bonsoir,
Ton dernier exemple est juste ce qu'il faut pour commencer à se faire des nœuds au cerveau.
J'ai un peu joué avec tes colonnes pour vérifier tes résultats et avoir un premier retour sur tes besoins.
Je suis passé par une modélisation graphe orienté (8 sommets, les villes, et 11 arcs, les liaisons).
Nîmes/Ajaccio est en double. Je n'ai gardé qu'une occurrence pour que la matrice d'adjacence (Adj dans le fichier excel) ne contienne que des 0/1.
Si la présence de ces doublons est absolument nécessaire, il faut le dire.
Intérêt de cette matrice :
Dans ton exemple, les 8 villes sont réparties en 2 composantes connexes : {Ajaccio, Nîmes} d'un côté et le reste de l'autre.
Dans ce reste, il y a 2 composantes fortement connexes {Paris, Angers, Rennes} et {Lens, Marseille, Nantes}.
Pour un petit nombre de villes et de liaisons, on peut se dire que ça ne sert pas à grand chose toutes ces complications.
Ça deviendra cependant très utile lorsque tu auras 50 villes et 150 liaisons.
Quelques questions supplémentaires :
1) il est possible d'aller d'une ville i à une ville j par des chemins différents, différents par les villes traversées ou par la longueur du chemin.
Exemples :
Es-tu intéressé par le chemin le plus court ou cherches-tu tous les chemins?
Dans le fichier excel, je n'ai gardé que les chemins les plus courts.
C'est pour cela qu'il n'y a que des chemins de longueur <=3.
2) dans la vraie vie, combien as-tu de villes et de liaisons?
Combien as-tu de composantes connexes et quelle est la taille maxi de la plus grosse composante?
3) pour quel projet t'intéresses-tu à ce genre de question?
Le fichier : https://www.cjoint.com/c/FCvgbEisCBO
Cordialement
Ton dernier exemple est juste ce qu'il faut pour commencer à se faire des nœuds au cerveau.
J'ai un peu joué avec tes colonnes pour vérifier tes résultats et avoir un premier retour sur tes besoins.
Je suis passé par une modélisation graphe orienté (8 sommets, les villes, et 11 arcs, les liaisons).
Nîmes/Ajaccio est en double. Je n'ai gardé qu'une occurrence pour que la matrice d'adjacence (Adj dans le fichier excel) ne contienne que des 0/1.
Si la présence de ces doublons est absolument nécessaire, il faut le dire.
Intérêt de cette matrice :
- En l'élevant aux puissances 2, 3, .... on obtient le nombre de chemins qui relient les sommets i, j avec des chemins de longueurs 2, 3, ....
- En calculant (Id+Adj)^7 on a la fermeture transitive du graphe (ce qui permet de connaître les villes qui sont joignables par un chemin à étape et celles qui ne le seront pas).
- C'est aussi un bon moyen de connaître la longueur maximale utile d'un chemin pour couvrir toutes les liaisons inter-villes.
Dans ton exemple, les 8 villes sont réparties en 2 composantes connexes : {Ajaccio, Nîmes} d'un côté et le reste de l'autre.
Dans ce reste, il y a 2 composantes fortement connexes {Paris, Angers, Rennes} et {Lens, Marseille, Nantes}.
Pour un petit nombre de villes et de liaisons, on peut se dire que ça ne sert pas à grand chose toutes ces complications.
Ça deviendra cependant très utile lorsque tu auras 50 villes et 150 liaisons.
Quelques questions supplémentaires :
1) il est possible d'aller d'une ville i à une ville j par des chemins différents, différents par les villes traversées ou par la longueur du chemin.
Exemples :
- Paris/Rennes/Paris et Paris/Angers/Rennes/Paris sont deux chemins pour une même boucle.
- Paris/Lens et Paris/Angers/Rennes/Marseille/Nantes/Lens.
Es-tu intéressé par le chemin le plus court ou cherches-tu tous les chemins?
Dans le fichier excel, je n'ai gardé que les chemins les plus courts.
C'est pour cela qu'il n'y a que des chemins de longueur <=3.
2) dans la vraie vie, combien as-tu de villes et de liaisons?
Combien as-tu de composantes connexes et quelle est la taille maxi de la plus grosse composante?
3) pour quel projet t'intéresses-tu à ce genre de question?
Le fichier : https://www.cjoint.com/c/FCvgbEisCBO
Cordialement
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
857
19 mars 2016 à 10:52
19 mars 2016 à 10:52
Bonjour,
il faudrait surtout que tu nous mettes à disposition le fichier excel qui contient tes données en donnant des exemples de solutions manuelles et en précisant s'il faut trouver les chemins les plus courts.
utilise cjoint.com pour partager ton fichier
cordialement
il faudrait surtout que tu nous mettes à disposition le fichier excel qui contient tes données en donnant des exemples de solutions manuelles et en précisant s'il faut trouver les chemins les plus courts.
utilise cjoint.com pour partager ton fichier
cordialement
Guillermo93
Messages postés
9
Date d'inscription
samedi 19 mars 2016
Statut
Membre
Dernière intervention
28 avril 2016
19 mars 2016 à 15:07
19 mars 2016 à 15:07
https://www.cjoint.com/c/FCtohbwDwMs
Voila pour le lien.
J'ai changé de pseudo car je viens de créer mon compte sur le site.
Je te remercie par avance pour ton aide.
Voila pour le lien.
J'ai changé de pseudo car je viens de créer mon compte sur le site.
Je te remercie par avance pour ton aide.
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
857
23 mars 2016 à 00:57
23 mars 2016 à 00:57
Bonsoir,
Quand tu parles de "phase expérimental du projet", de quoi s'agit-il?
Quel est ton rôle dans ce projet?
En tout cas, j'ai lancé les "verts" de ton dernier fichier :
276 sommets (un sommet est une liaison) et 2 158 arcs (un arc relie 2 liaisons qui peuvent s'enchaîner, ie telles que la ville d'arrivée de la 1ère liaison est égale à la ville de départ de la 2nde liaison).
Après 1/2 seconde de traitement : 36 doubles, 342 triples, 1 534 quadruples.
J'ai voulu tester sur 4 fois plus de liaisons en dupliquant 2 fois les verts:
1 104 sommets, 34 528 arcs (normal, c'est 2 158*16).
Après, c'est moins drôle, il a fallu 82 secondes pour obtenir 576 doubles, 21 888 triples, 392 704 quadruples.
Pour le coup, le temps réel, il faut oublier et en plus, que vas-tu faire d'une telle quantité d'info?
cordialement
Quand tu parles de "phase expérimental du projet", de quoi s'agit-il?
Quel est ton rôle dans ce projet?
En tout cas, j'ai lancé les "verts" de ton dernier fichier :
276 sommets (un sommet est une liaison) et 2 158 arcs (un arc relie 2 liaisons qui peuvent s'enchaîner, ie telles que la ville d'arrivée de la 1ère liaison est égale à la ville de départ de la 2nde liaison).
Après 1/2 seconde de traitement : 36 doubles, 342 triples, 1 534 quadruples.
J'ai voulu tester sur 4 fois plus de liaisons en dupliquant 2 fois les verts:
1 104 sommets, 34 528 arcs (normal, c'est 2 158*16).
Après, c'est moins drôle, il a fallu 82 secondes pour obtenir 576 doubles, 21 888 triples, 392 704 quadruples.
Pour le coup, le temps réel, il faut oublier et en plus, que vas-tu faire d'une telle quantité d'info?
cordialement
Guillermo93
Messages postés
9
Date d'inscription
samedi 19 mars 2016
Statut
Membre
Dernière intervention
28 avril 2016
23 mars 2016 à 09:09
23 mars 2016 à 09:09
Bonjour,
Quand je parle de phase d'expérimentation c'est qu'il n'est tout simplement pas abouti dans la conception. Il faudra que je peaufine un peu sa mise en page et que je rajoute des colonnes d'informations diverses concernant les personnes mains n'ayant pas d'influence sur les résultats de recherche de permutant.
Mon rôle est de finaliser cet outil qui me permet de mettre en place des permutations de personnes.
Si la durée n'est que 82 secondes pour un tel volume, cela me convient parfaitement!
En gros, l'utilisation provisoirement sera une vingtaine de villes mais par la suite si cela marche bien alors je l'utiliserai au niveau national et donc beaucoup plus de villes.
Du coup tu es passé par une macro pour ton test?
Pourrais-tu me mettre en lien le fichier pour voir comment tu as fait?
Je te remercie par avance.
Cordialement.
Quand je parle de phase d'expérimentation c'est qu'il n'est tout simplement pas abouti dans la conception. Il faudra que je peaufine un peu sa mise en page et que je rajoute des colonnes d'informations diverses concernant les personnes mains n'ayant pas d'influence sur les résultats de recherche de permutant.
Mon rôle est de finaliser cet outil qui me permet de mettre en place des permutations de personnes.
Si la durée n'est que 82 secondes pour un tel volume, cela me convient parfaitement!
En gros, l'utilisation provisoirement sera une vingtaine de villes mais par la suite si cela marche bien alors je l'utiliserai au niveau national et donc beaucoup plus de villes.
Du coup tu es passé par une macro pour ton test?
Pourrais-tu me mettre en lien le fichier pour voir comment tu as fait?
Je te remercie par avance.
Cordialement.
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
857
>
Guillermo93
Messages postés
9
Date d'inscription
samedi 19 mars 2016
Statut
Membre
Dernière intervention
28 avril 2016
23 mars 2016 à 10:03
23 mars 2016 à 10:03
Bonjour,
Oui, une macro.
C'est obligatoire pour avoir ce genre de temps de réponse.
Il faut également passer par des tableaux. L'affichage se fait ainsi par bloc de façon instantanée.
Je ne sais pas trop si l'utilisation d'un dictionary à la place des tableaux amènerait une diminution de la durée de traitement. A voir ....
Après, il reste le C.
En revanche, j'ai voulu réorganiser le code pour le rendre plus présentable .. mauvaise idée!
Le code s'est mis à planter à un endroit où ça se passait bien hier soir.
J'ai donc colmaté mes REDIM en fixant la taille à 100 000, ce qui est exagéré pour 200 ou 300 liaisons.
Au bout du compte il faut 89 secondes pour 1 100 liaisons et toujours une demi seconde pour 276 liaisons.
Dans la macro, il y a des lignes en commentaire qu'il suffit d'activer pour avoir l'affichage des tables utiles dans l'algorithme.(successeurs, prédécesseurs, degrés intérieur et extérieur, cumul intérieur et extérieur des degrés)
Le fichier : https://www.cjoint.com/c/FCxiOHBnXBR
Cordialement
Oui, une macro.
C'est obligatoire pour avoir ce genre de temps de réponse.
Il faut également passer par des tableaux. L'affichage se fait ainsi par bloc de façon instantanée.
Je ne sais pas trop si l'utilisation d'un dictionary à la place des tableaux amènerait une diminution de la durée de traitement. A voir ....
Après, il reste le C.
En revanche, j'ai voulu réorganiser le code pour le rendre plus présentable .. mauvaise idée!
Le code s'est mis à planter à un endroit où ça se passait bien hier soir.
J'ai donc colmaté mes REDIM en fixant la taille à 100 000, ce qui est exagéré pour 200 ou 300 liaisons.
Au bout du compte il faut 89 secondes pour 1 100 liaisons et toujours une demi seconde pour 276 liaisons.
Dans la macro, il y a des lignes en commentaire qu'il suffit d'activer pour avoir l'affichage des tables utiles dans l'algorithme.(successeurs, prédécesseurs, degrés intérieur et extérieur, cumul intérieur et extérieur des degrés)
Le fichier : https://www.cjoint.com/c/FCxiOHBnXBR
Cordialement
Guillermo93
Messages postés
9
Date d'inscription
samedi 19 mars 2016
Statut
Membre
Dernière intervention
28 avril 2016
>
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
Modifié par Guillermo93 le 23/03/2016 à 22:01
Modifié par Guillermo93 le 23/03/2016 à 22:01
Bonsoir,
La macro fonctionne déjà parfaitement pour l'utilisation que je vais en avoir.
Je vais juste devoir modifier quelques lignes de code lorsque j'aurai finalisé la mise en page finale de la feuille excel pour la réception des informations.
Il me reste encore la prise ne compte des critères (Vert,Rouge).
Le temps de réponse n'est pas spécifiquement un problème car suffisamment court.
Après pour le C, je n'ai pour le coup aucune connaissance de ce langage de programmation.
Sachant que c'est un google form que j'utilise pour la saisie des utilisateurs, les résultats apparaissent sur une sheet Google que je copie dans le fichier excel pour utiliser la macro et faire le travail.
Si t'as d'autres idées je suis bien entendu preneur car je suis d'avoir ton niveau de programmation et de connaissance dans ce domaine.
Cordialement.
La macro fonctionne déjà parfaitement pour l'utilisation que je vais en avoir.
Je vais juste devoir modifier quelques lignes de code lorsque j'aurai finalisé la mise en page finale de la feuille excel pour la réception des informations.
Il me reste encore la prise ne compte des critères (Vert,Rouge).
Le temps de réponse n'est pas spécifiquement un problème car suffisamment court.
Après pour le C, je n'ai pour le coup aucune connaissance de ce langage de programmation.
Sachant que c'est un google form que j'utilise pour la saisie des utilisateurs, les résultats apparaissent sur une sheet Google que je copie dans le fichier excel pour utiliser la macro et faire le travail.
Si t'as d'autres idées je suis bien entendu preneur car je suis d'avoir ton niveau de programmation et de connaissance dans ce domaine.
Cordialement.
JvDo
Messages postés
1978
Date d'inscription
mercredi 27 juillet 2005
Statut
Membre
Dernière intervention
28 septembre 2020
857
19 mars 2016 à 16:40
19 mars 2016 à 16:40
Bonjour,
tu n'as pas quelque chose de plus consistant?
Tu parlais de dizaines de lignes.... et tu n'en mets que 5.
Question : souhaites-tu la liste de tous les chemins pour tous les trajets (ceux d'un point de départ quelconque vers un point d'arrivée quelconque) ou simplement pour les boucles (A--> A, B-->B, C--> C ...)
cdlt
tu n'as pas quelque chose de plus consistant?
Tu parlais de dizaines de lignes.... et tu n'en mets que 5.
Question : souhaites-tu la liste de tous les chemins pour tous les trajets (ceux d'un point de départ quelconque vers un point d'arrivée quelconque) ou simplement pour les boucles (A--> A, B-->B, C--> C ...)
cdlt
Guillermo93
Messages postés
9
Date d'inscription
samedi 19 mars 2016
Statut
Membre
Dernière intervention
28 avril 2016
20 mars 2016 à 13:46
20 mars 2016 à 13:46
J'ai refais un modèle avec un peu plus d'information pour te montrer le résultat que j'aimerai obtenir.
https://www.cjoint.com/c/FCumTtUcRis
https://www.cjoint.com/c/FCumTtUcRis
Modifié par Guillermo93 le 21/03/2016 à 12:42
Je te remercie déjà pour le travail accompli et le temps que tu prends pour me répondre,
1) La notion de distance n'est pas nécessaire dans ma recherche.
Les doublons doivent être laissés si les noms et prénoms ne sont pas identiques.
Les villes peuvent donc apparaître à plusieurs reprise sur le départ ou l'arrivée.
Je ne recherche que les possibilités permettant d'obtenir une ville de départ identique à une ville d'arrivée et ce avec un maximum de 2 étapes soit 4 villes au total:
(ex: Paris->Marseille ; Marseille->Lens ; Lens-> Nantes ; Nantes->Paris)
2) Dans la vraie vie, ce sera un formulaire incrémenté par des utilisateurs qui alimentera ce fichier excel. Le nombre de villes pourra être important (+/- 50) et surtout le nombre de personne pourra lui atteindre 1000 pers.
Que veux-tu dire par composante connexe?
3) Pour des permutations de personnel. Afin que puisse être réalisé des permutations de 2, 3 ou 4 personnes. D’où l'obligation de retrouver la ville de départ égale à celle d'arrivée.
Ton système de modélisation graphe est ingénieuse mais le volume final de ce fichier fera qu'il risque de ne plus être lisible avec le nombre de liaisons et de sommets.
En même temps je ne t'avais pas donner toutes les cartes.
Le modèle que je t'ai envoyé n'ai pas complet par ailleurs, car je souhaiterai également faire vérifier une condition pour que la permutation puisse se faire.
Dans le cas de la fiche 13, identique à la fiche 8, la condition 1 ne permet pas de prendre en compte la permutation avec la fiche 3. Car couleur différente. J'espère être assez clair dans mon explication.
Voir nouveau modèle : https://www.cjoint.com/c/FCvlM6lVgps
Merci encore.
Cdt
Modifié par JvDo le 21/03/2016 à 16:05
Avec 1000 personnes et + ou - 50 villes, ça fait quand même quelques centaines voire milliers de sommets (j'imagine qu'il n'y aura pas 1000 personnes pour chaque liaison).
Il faut laisser tomber la matrice d'adjacence et passer à la liste d'adjacence.
Il faut également prendre le graphe des arcs (le line graph) du graphe que j'ai utilisé dans mon post précédent. Les sommets sont maintenant des liaisons inter-villes numérotées comme dans ton tableau. Ils intègrent donc nativement les doublons.
Cette liste est un tableau de listes qui contient les successeurs de chaque sommet.
Il devient "facile" de faire boucler une macro sur chaque sommet pour identifier les cycles de longueurs 2, 3 ou 4.
En effet, il suffit d'avoir la liste des prédécesseurs du sommet de départ pour connaître la fin du cycle puisque la ville d'arrivée d'un prédécesseur du sommet de départ est la ville de départ du sommet de départ.
Je ne sais pas ce que ça fera en terme de dénombrement mais ça risque de faire beaucoup de réponses.
Avec un dessin rapide à la main du nouveau graphe, la liste d'adjacence se construit facilement et permet d'obtenir tous les chemins de longueur 4 (il y en a 26) parmi lesquels il est facile d'identifier les cycles (6 de longueur 2 et 6 de longueur 3).
On obtient bien les mêmes résultats que ceux que tu indiques dans ton exemple.
Cordialement
21 mars 2016 à 22:30
J'ai du essayé de comprendre tes formules excel car je ne connaissais pas du tout les adjacences.
Du coup tu penses qu'une macro est réalisable par rapport à la recherche des permutations possibles?
Bonne soirée.
22 mars 2016 à 13:10
Oui, la liste d'adjacence évite le stockage d'une matrice creuse en ne gardant que les sommets reliés.
Naturellement, si la matrice n'est pas creuse, l'intérêt de la liste d'adjacence se discute.
Sur des petits modèles, les liste et matrice d'adjacence se calculent par formule facilement. Malheureusement, les temps de calcul peuvent devenir prohibitifs et il faut passer par les macros.
Je viens de tester sur 50 liaisons (270 arcs) et les formules tiennent encore la route.
L'établissement des chemins me semble en revanche beaucoup plus facile en macro qu'en formule.
Si tu as ton vrai fichier (sans les noms, je n'en ai pas besoin) avec tes milliers de liaisons, je pourrai tester les temps de réponse.
cordialement
22 mars 2016 à 17:12
Je vais t'envoyer un modèle avec des centaines de liaisons.
Bien entendu pour le moment il ne s'agit que de la phase expérimental du projet donc les noms de villes et de personnes seront fictifs.
Je t'envoi ça ce soir.
Cordialement.