Dictionnaire où plusieurs clés sont associés à la même valeur

Salut à tous,

Je me pose des questions (existentielles ?) sur la déclaration d’un dictionnaire où plusieurs clés sont associés à la même valeur. On pourrait faire ce code.

1

dic = {'a': 2, 'b': 2, 'c':2, 'd': 3}

Mais si on décide de changer la valeur associée, il faudrait faire de multiples changements. Sinon, on pourrait faire ça.

1
2

dic = {'d': 3}
dic['a'] = dic['b'] = dic['c'] = 2

Mais c’est quand même plus lourd. Et finalement, on pourrait utiliser une variable pour la valeur 2.

1
2

DEUX = 2
dic = {'a': DEUX, 'b': DEUX, 'c': DEUX, 'd':DEUX}

Mais il y a-t-il une autre méthode que j’ai raté qui permettrait de faire quelque chose du genre {'a', 'b', 'c': 2} ?

Merci d’avance pour vos réponses.

Je suis curieux de savoir comment tu utilises ce dictionnaire dans ton programme.

Ici on dirait que tu veux simplement l’"inverse" de ce dictionnaire.

{2: ['a', 'b', 'c'], 3: ['d']}

Bonjour,

Ça semble être un problème existentiel mais je ne le saisis pas bien.

Ton soucis c’est que dans ton code tu associes plusieurs clés à une même valeur, que tu pourrais à l’avenir modifier cette valeur dans ton programme et que tu voudrais que ça se fasse le plus simplement possible ?

Tu aurais un exemple de cas concret où ce « problème » se poserait ?

Merci pour vos réponses.

Je n’ai pas de programme où j’en ai besoin, je me posais juste la question. Mais voici un exemple (mauvais je pense) où ça pourrait être utile.

On a un endroit où on demande à l’utilisateur de rentrer une caractéristique, mais il y a plein de manières d’écrire cette caractéristique. Si c’est par exemple le sexe, on aurait garçon, homme, M, H, garcon, etc. On aurait alors

1
2

dic = {'H': 'H', 'M': 'H', etc.}
sexe = dic[sexe] 

Dans ce genre de cas, j’imagine que l’« inverse » du dictionnaire donné par @victor, correspondrait bien, s’il y a une manière simple d’obtenir la clé associé à un élément du tableau. Ici, si on avait {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}, il faudrait pouvoir obtenir 'H' facilement à partir de ’homme’.

Effectivement.

Même si ce n’est pas trop le sujet, j’imagine qu’il y a une méthode plus Pythonesque pour cet exemple, non ?

Pour récupérer la clé du dictionnaire à partir d’une valeur ? Si oui, je verrais bien quelque chose comme ceci (qui peut surement être amélioré).

1
2
3
4
5
6
7

dic = {'H': ['homme', 'H', 'h'], 'F': ['femme', 'féminin', 'f']}
gender = input()
gender_code = [k for k, v in dic.items() if gender in v]
try:
    gender_code = gender_code[0]
except KeyError:
    print("Entrée invalide.")

La description de ton problème me fait typiquement penser à une structure Union-find, couplée par exemple à un dictionnaire : tu peux regrouper des clefs ensemble dans ton union-find (par exemple, 'a', 'b' et 'c'), et étant donnée une clef, trouver à quelle classe elle appartient et utiliser cette classe comme clef de ton dictionnaire pour connaître la valeur associée.

La solution proposée par victor et entwanne (deux dictionnaires, dans les deux sens) est un peu différente, et j’ai l’impression qu’elle répond assez bien au problème « je veux pouvoir grouper une clef avec une autre » : on récupère la valeur X associée au groupe et on l’affecte à la nouvelle clef à grouper dans le dictionnaire direct, et on ajoute cette clef à grouper dans la valeur associée à X dans le dictionnaire indirect tout en l’enlevant de son ancienne valeur. Tout est en temps constant.

Ça permet aussi de résoudre efficacement le problème de « je veux pouvoir connaître toutes les clefs auxquelles est associée une certaine valeur » (sans reparcourir tout le dictionnaire, ce qui serait particulièrement inefficace), mais j’ai l’impression qu’il ne fait pas partie de ce que tu demandes (après le problème XY, la solution YZ ? :-D) Si on met de côté les groupes de clefs, c’est même la solution évidente pour résoudre ce problème, qui peut en effet aussi s’écrire comme « je veux une association clef/valeur mais aussi une association valeur/clef ».

Par contre, pour changer une valeur associée à un groupe, c’est plus compliqué. Le dictionnaire indirect te permet d’éviter de parcourir tout ton dictionnaire direct, mais il faut quand même, dans le dictionnaire direct, changer la valeur associée à chaque élément de ton groupe. Pan, $O(n)$ : la même complexité que si tu utilisais des bêtes listes d’association.

La solution avec l’union-find te permet d’éviter ça et d’avoir du $O(\log n)$ un peu partout, pour un coût en mémoire qui a l’air à peu près similaire. C’est vraiment un cas d’école d’utilisation de cette structure.

Note qu’il reste à mon avis quelque chose de pas clair dans la définition de ton problème : qu’est-ce qui se passe si par hasard deux clefs ont la même valeur associée alors que tu ne voulais pas les grouper, et que tu veux changer la valeur d’une des deux ? Est-ce que la deuxième veut changer aussi ? C’est difficile de répondre à ta place, et tu n’as pas donné suffisamment d’informations sur ton problème de départ pour savoir, mais mon intuition est que le comportement où on groupe les clefs explicitement ou pas du tout est plus logique. Si tu veux retrouver l’autre comportement, ajouter un union-find aux doubles dictionnaires de victor m’a l’air d’être la bonne solution (quand je change une valeur, je vérifie si elle n’est pas déjà présente ailleurs, et le cas échéant je fusionne les deux classes. La complexité globale de la mise à jour reste la même, c’est informagique.)

PS : une recherche très rapide « union find python » me donne pas mal de résultats, dont aucun ne me semble être universellement validé par la communauté. Ça fait trop longtemps que je n’ai pas utilisé sérieusement ce langage pour t’en proposer une, mais je suis à peu près certain qu’il y en a au moins une de qualité dans le lot.

Je n’avais pas du tout penser à du Union-Find pour ça, mais ouais c’est une manière cool de voir le problème en particulier quand on décide de changer l’un des deux valeurs.

Note qu’il reste à mon avis quelque chose de pas clair dans la définition de ton problème : qu’est-ce qui se passe si par hasard deux clefs ont la même valeur associée alors que tu ne voulais pas les grouper, et que tu veux changer la valeur d’une des deux ? Est-ce que la deuxième veut changer aussi ?

Ben, il n’y a aucun problème réel derrière, je me suis levé ce matin et je me suis posé cette question.

Si tu veux retrouver l’autre comportement, ajouter un union-find aux doubles dictionnaires de victor m’a l’air d’être la bonne solution (quand je change une valeur, je vérifie si elle n’est pas déjà présente ailleurs, et le cas échéant je fusionne les deux classes. La complexité globale de la mise à jour reste la même, c’est informagique.)

Ouep, on garde la même complexité et on a une solution assez flexible. Je suis quasiment sûr d’avoir un code sur mon ordi pour les Union-Find en Python. Je vais jouer un peu avec (et avec les deux comportements possibles).