Cadeaux circulaires

Pour fêter la nouvelle année, un groupe d'amis a décidé qu'il y aurait une distribution de petits cadeaux lors de la soirée. Pour préparer cela, chacun a écrit son nom sur un papier qu'il a déposé dans un chapeau.

Au moment de la distribution de cadeaux, chaque participant tire un papier. Il découvre ainsi la personne à laquelle il va devoir faire son cadeau (potentiellement lui).

Un tel appariement des invités s'appelle en mathématiques une permutation. On cherche dans cet exercice à déterminer si cette permutation est circulaire.

On garantit que :

  • il y a au moins une personne invitée à cette fête ;
  • chaque personne fait un cadeau à une unique personne (éventuellement elle-même),
  • chaque personne ne reçoit qu'un unique cadeau (éventuellement en provenance d'elle-même).

On représente une distribution par un dictionnaire Python dans lequel :

  • les clés sont les personnes offrant le cadeau ;
  • les valeurs sont les personnes recevant le cadeau.

Conséquence des règles sur le dictionnaire

Les règles garantissent que :

  • le dictionnaire est non-vide
  • chaque personne apparaît exactement une fois en tant que clé du dictionnaire
  • et exactement une fois en tant que valeur associée à une clé.
Exemple pour distribution_a

Voici un exemple, avec 6 personnes, de « distribution » de cadeaux qui respecte les règles ci-dessus :

  • Anne fait un cadeau à Élodie ;
  • Élodie fait un cadeau à Bruno ;
  • Bruno fait un cadeau à Fidel ;
  • Fidel fait un cadeau à Anne ;
  • Claude fait un cadeau à Denis ;
  • Denis fait un cadeau à Claude.
flowchart LR
    A(["Anne"]) --> E(["Élodie"])
    E --> B(["Bruno"])
    B --> F(["Fidel"])
    F --> A
    C(["Claude"]) --> D(["Denis"])
    D --> C

Le dictionnaire correspondant à cette distribution est le suivant :

🐍 Script Python
distribution_a = {
    "Anne": "Élodie",
    "Élodie": "Bruno",
    "Bruno": "Fidel",
    "Fidel": "Anne",
    "Claude": "Denis",
    "Denis": "Claude",
    }

Dans cette distribution il y a deux cycles distincts :

  • un premier cycle avec Anne, Élodie, Bruno, Fidel ;
  • et un second cycle avec Claude et Denis.

Cette distribution n'est donc pas circulaire.

Exemple pour distribution_b
🐍 Script Python
distribution_b = {
    "Anne": "Claude",
    "Bruno": "Fidel",
    "Claude": "Élodie",
    "Denis": "Anne",
    "Élodie": "Bruno",
    "Fidel": "Denis"
    }

flowchart LR
    A(["Anne"]) --> C(["Claude"])
    B([Bruno]) --> F(["Fidel"])
    C(["Claude"]) --> E(["Élodie"])
    D([Denis]) --> A
    E --> B
    F --> D

Cette distribution comporte un unique cycle : Anne, Claude, Élodie, Bruno, Fidel, Denis. Cette distribution est donc circulaire.

Une présentation est dite circulaire si elle ne présente qu'un unique cycle. Pour savoir si une distribution est circulaire, on peut utiliser l'algorithme ci-dessous :

  • on part d'un donateur initial;
  • on inspecte son destinataire dans la distribution,
  • ce destinataire devient à son tour donateur ;
  • on recommence le parcours jusqu'à ce que le destinataire soit le donateur initial ;
  • la distribution est circulaire si on l'a effectué autant de « sauts » qu'il y a de personnes dans le groupe.

Compléter la fonction est_circulaire.

Exemples 
>>> distribution_a = {
    "Anne": "Élodie",
    "Bruno": "Fidel",
    "Claude": "Denis",
    "Denis": "Claude",
    "Élodie": "Bruno",
    "Fidel": "Anne"
    }
>>> est_circulaire(distribution_a)
False
>>> distribution_b = {
    "Anne": "Claude",
    "Bruno": "Fidel",
    "Claude": "Élodie",
    "Denis": "Anne",
    "Élodie": "Bruno",
    "Fidel": "Denis"
    }
>>> est_circulaire(distribution_b)
True

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013l7/r0!n3_éhf45(Ovtb1c9eS[iTP8pF-wC.;àa: +q]èmxksR=og)2du6y050%0x0s0M0A0b0W0O0v0b0M0W0W0Y010s0A0E010406050W0(0T0T0M0e0*040y0Z0b0(0~0Z0h0O020M0T0E0K0O0X0x180e0Q0(0x0W050d1517191b130E041z1G051J0d1J1L1G130%0A0r0?0^0`0|0l0A0!0l0b1Z0l0s11050.0t0b0x1U0_0{011Y1!1$1!0s1,1.1*0s0t0Z0%1b1+0e1H0s0l0?1e0W0E0M0h0|0$011:1W010m0:0x0h1m0x1*2b2d2i1=2l1.2o0T2q040a0O0C0e0Z0E0Z0W0A1h1j0,290e0e0x0v2L1z2s0h1H0d272X0s2524260%2u0|1$0h2n2I1*1R1T0@1;2+0A2-0h211S1*0E2Q1H2V2X32142c1j2?2j2{0e180b110O0u2U3612352t381=3a3c3e0$3h2d3j2V2*013o0M3d040O0i3s2W133v3m0|3y3A0O0n3E3u363w3K3e0o3O3G3Q3I3x0Z3b3z3e0)3V3k371V3n3!3p3B0c3)3H3,3J3.3$3B0D3=3X3@3Z3#3L0w3}3l3 3S040u0f443+2@403/0u3g1A3i1I301z2;2!0%2(3w0v212A0+1S1H2 0x314j4i3t054s0,4A454d0V110,0m3O3*3w0H3e4O3?4d0h0m111x0s0j0v0A0e0v0(0^4%0x4T3~4d10040p4.4I394L0A0W2#0A0t1g0A1i4@4c2j4;0#0N3V0O5a0O4P3Y0h110E0x0e0W1i2-1y4C2W5c4U2j0Z110Y3O5q4/55110z533R5g2Q2{0T5w5d3 4K040m3!5I5r3n5E2.5H5o3B5J4d0Z4R042_5P5y5R041R4|0e4~50525V5X5z040R595b5=5)4y0T0A5i4-5V5x4^1=5t045v625{3J5g5i5k0h5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0M0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110h0t0j6C0~2o6G2Q5n6N6a016L6I6A6n0A114h6,6-5a6 5L0H1Y1.726P6^6E6{616~6/660g6M3i6O5e6#5 2Q6(5?586w6y6y6 5f5*4Z7j0/7w697n5u7g7t6Q5,5.6U346/6Y6V736:7F6D6`7I7l4j7U6*5_7B7s6!046=6@7G7#4,6}7r6 717K6s7Y7:7i7?6|7N3 660P834d6o483V797-4J112Q0s0(0e0h874_7/6?806F7$7^3t8d5s5u7q8t7D0t112x7x1=4;4?7W7h6R5-6T518k8H6i110#3)0d4F4z4k8V0d4n1z0s4p8!2$2Y20222!0M1-8X4n1F4H7X2Q0T0j0m0M0V0x0j0l0i111r1t1v1x0O7z341M3j1G0q1j0M8i0/0s0O0E0(0O0k0!3z1s2n9h2n0r4{0M0!5i0O0(2-0O200(0@1/4E4t5M5O8T9H0O0M0r2R0O5k0e0~1/2d0~4$0E0k1/2J0O0^0O5+6S5/1j0h004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0y0v5-0E9h0C0*275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0ea/7Ya-0Z5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0m0m2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0AbC5!b0bhb2bY0e2d9wb74=aG7E0xbObQ0AbSb}bf110Ga@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0v110F3z0Wct12cn7}5Lc-8ja@0Vc=040B0e1w8Sao8W2X8:1K040I0-0O0x0U5i4$0v1/6|c_0T8.0O0L9y1jdidk0Adm9(1/0!c00E0l1/184{9$950e0S0!1.0=2Ncz8L1idA0=0v0M0,9e0U9Q0A1n1$2l9qdJ9:4(0Z8i0W0J9{138Y0-0/0;04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.128013l7/r0!n3_éhf45(Ovtb1c9eS[iTP8pF-wC.;àa: +q]èmxksR=og)2du6y050%0x0s0M0A0b0W0O0v0b0M0W0W0Y010s0A0E010406050W0(0T0T0M0e0*040y0Z0b0(0~0Z0h0O020M0T0E0K0O0X0x180e0Q0(0x0W050d1517191b130E041z1G051J0d1J1L1G130%0A0r0?0^0`0|0l0A0!0l0b1Z0l0s11050.0t0b0x1U0_0{011Y1!1$1!0s1,1.1*0s0t0Z0%1b1+0e1H0s0l0?1e0W0E0M0h0|0$011:1W010m0:0x0h1m0x1*2b2d2i1=2l1.2o0T2q040a0O0C0e0Z0E0Z0W0A1h1j0,290e0e0x0v2L1z2s0h1H0d272X0s2524260%2u0|1$0h2n2I1*1R1T0@1;2+0A2-0h211S1*0E2Q1H2V2X32142c1j2?2j2{0e180b110O0u2U3612352t381=3a3c3e0$3h2d3j2V2*013o0M3d040O0i3s2W133v3m0|3y3A0O0n3E3u363w3K3e0o3O3G3Q3I3x0Z3b3z3e0)3V3k371V3n3!3p3B0c3)3H3,3J3.3$3B0D3=3X3@3Z3#3L0w3}3l3 3S040u0f443+2@403/0u3g1A3i1I301z2;2!0%2(3w0v212A0+1S1H2 0x314j4i3t054s0,4A454d0V110,0m3O3*3w0H3e4O3?4d0h0m111x0s0j0v0A0e0v0(0^4%0x4T3~4d10040p4.4I394L0A0W2#0A0t1g0A1i4@4c2j4;0#0N3V0O5a0O4P3Y0h110E0x0e0W1i2-1y4C2W5c4U2j0Z110Y3O5q4/55110z533R5g2Q2{0T5w5d3 4K040m3!5I5r3n5E2.5H5o3B5J4d0Z4R042_5P5y5R041R4|0e4~50525V5X5z040R595b5=5)4y0T0A5i4-5V5x4^1=5t045v625{3J5g5i5k0h5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0M0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110h0t0j6C0~2o6G2Q5n6N6a016L6I6A6n0A114h6,6-5a6 5L0H1Y1.726P6^6E6{616~6/660g6M3i6O5e6#5 2Q6(5?586w6y6y6 5f5*4Z7j0/7w697n5u7g7t6Q5,5.6U346/6Y6V736:7F6D6`7I7l4j7U6*5_7B7s6!046=6@7G7#4,6}7r6 717K6s7Y7:7i7?6|7N3 660P834d6o483V797-4J112Q0s0(0e0h874_7/6?806F7$7^3t8d5s5u7q8t7D0t112x7x1=4;4?7W7h6R5-6T518k8H6i110#3)0d4F4z4k8V0d4n1z0s4p8!2$2Y20222!0M1-8X4n1F4H7X2Q0T0j0m0M0V0x0j0l0i111r1t1v1x0O7z341M3j1G0q1j0M8i0/0s0O0E0(0O0k0!3z1s2n9h2n0r4{0M0!5i0O0(2-0O200(0@1/4E4t5M5O8T9H0O0M0r2R0O5k0e0~1/2d0~4$0E0k1/2J0O0^0O5+6S5/1j0h004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0y0v5-0E9h0C0*275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0ea/7Ya-0Z5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0m0m2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0AbC5!b0bhb2bY0e2d9wb74=aG7E0xbObQ0AbSb}bf110Ga@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0v110F3z0Wct12cn7}5Lc-8ja@0Vc=040B0e1w8Sao8W2X8:1K040I0-0O0x0U5i4$0v1/6|c_0T8.0O0L9y1jdidk0Adm9(1/0!c00E0l1/184{9$950e0S0!1.0=2Ncz8L1idA0=0v0M0,9e0U9Q0A1n1$2l9qdJ9:4(0Z8i0W0J9{138Y0-0/0;04.