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

.128013:p(40ed3; 1o5_n)h]6qc[y!FCuvà8i2+xms7=wlSatf-9ORrg.TéPkbè/050h0g0R0Q0F0O0K0k0v0O0Q0K0K0M010R0F0c010406050K0B0J0J0Q0X0x040P0m0O0B0~0m0p0k020Q0J0c0j0k0W0g180X0u0B0g0K050*1517191b130c041z1G051J0*1J1L1G130h0F0C0?0^0`0|0r0F0Y0r0O1Z0r0R11050.0(0O0g1U0_0{011Y1!1$1!0R1,1.1*0R0(0m0h1b1+0X1H0R0r0?1e0K0c0Q0p0|0G011:1W010S0:0g0p1m0g1*2b2d2i1=2l1.2o0J2q040a0k0$0X0m0c0m0K0F1h1j0,290X0X0g0v2L1z2s0p1H0*272X0R2524260h2u0|1$0p2n2I1*1R1T0@1;2+0F2-0p211S1*0c2Q1H2V2X32142c1j2?2j2{0X180O110k0l2U3612352t381=3a3c3e0G3h2d3j2V2*013o0Q3d040k0i3s2W133v3m0|3y3A0k0e3E3u363w3K3e0n3O3G3Q3I3x0m3b3z3e0t3V3k371V3n3!3p3B0L3)3H3,3J3.3$3B0E3=3X3@3Z3#3L0U3}3l3 3S040l0f443+2@403/0l3g1A3i1I301z2;2!0h2(3w0v212A0+1S1H2 0g314j4i3t054s0,4A454d0%110,0S3O3*3w0N3e4O3?4d0p0S111x0R0o0v0F0X0v0B0^4%0g4T3~4d10040d4.4I394L0F0K2#0F0(1g0F1i4@4c2j4;0q0b3V0k5a0k4P3Y0p110c0g0X0K1i2-1y4C2W5c4U2j0m110M3O5q4/55110w533R5g2Q2{0J5w5d3 4K040S3!5I5r3n5E2.5H5o3B5J4d0m4R042_5P5y5R041R4|0X4~50525V5X5z040s595b5=5)4y0J0F5i4-5V5x4^1=5t045v625{3J5g5i5k0p5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0Q0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110p0(0o6C0~2o6G2Q5n6N6a016L6I6A6n0F114h6,6-5a6 5L0N1Y1.726P6^6E6{616~6/660y6M3i6O5e6#5 2Q6(5?586w6y6y6 5f5*4Z7j0/7w697n5u7g7t6Q5,5.6U346/6Y6V736:7F6D6`7I7l4j7U6*5_7B7s6!046=6@7G7#4,6}7r6 717K6s7Y7:7i7?6|7N3 660H834d6o483V797-4J112Q0R0B0X0p874_7/6?806F7$7^3t8d5s5u7q8t7D0(112x7x1=4;4?7W7h6R5-6T518k8H6i110q3)0*4F4z4k8V0*4n1z0R4p8!2$2Y20222!0Q1-8X4n1F4H7X2Q0J0o0S0Q0%0g0o0r0i111r1t1v1x0k7z341M3j1G0V1j0Q8i0/0R0k0c0B0k0#0Y3z1s2n9h2n0C4{0Q0Y5i0k0B2-0k200B0@1/4E4t5M5O8T9H0k0Q0C2R0k5k0X0~1/2d0~4$0c0#1/2J0k0^0k5+6S5/1j0p004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0P0v5-0c9h0$0x275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0Xa/7Ya-0m5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0S0S2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0FbC5!b0bhb2bY0X2d9wb74=aG7E0gbObQ0FbSb}bf110Ta@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0v110z3z0Kct12cn7}5Lc-8ja@0%c=040!0X1w8Sao8W2X8:1K040A0-0k0g0I5i4$0v1/6|c_0J8.0k0D9y1jdidk0Fdm9(1/0Yc00c0r1/184{9$950X0)0Y1.0=2Ncz8L1idA0=0v0Q0,9e0I9Q0F1n1$2l9qdJ9:4(0m8i0K0Z9{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

.128013:p(40ed3; 1o5_n)h]6qc[y!FCuvà8i2+xms7=wlSatf-9ORrg.TéPkbè/050h0g0R0Q0F0O0K0k0v0O0Q0K0K0M010R0F0c010406050K0B0J0J0Q0X0x040P0m0O0B0~0m0p0k020Q0J0c0j0k0W0g180X0u0B0g0K050*1517191b130c041z1G051J0*1J1L1G130h0F0C0?0^0`0|0r0F0Y0r0O1Z0r0R11050.0(0O0g1U0_0{011Y1!1$1!0R1,1.1*0R0(0m0h1b1+0X1H0R0r0?1e0K0c0Q0p0|0G011:1W010S0:0g0p1m0g1*2b2d2i1=2l1.2o0J2q040a0k0$0X0m0c0m0K0F1h1j0,290X0X0g0v2L1z2s0p1H0*272X0R2524260h2u0|1$0p2n2I1*1R1T0@1;2+0F2-0p211S1*0c2Q1H2V2X32142c1j2?2j2{0X180O110k0l2U3612352t381=3a3c3e0G3h2d3j2V2*013o0Q3d040k0i3s2W133v3m0|3y3A0k0e3E3u363w3K3e0n3O3G3Q3I3x0m3b3z3e0t3V3k371V3n3!3p3B0L3)3H3,3J3.3$3B0E3=3X3@3Z3#3L0U3}3l3 3S040l0f443+2@403/0l3g1A3i1I301z2;2!0h2(3w0v212A0+1S1H2 0g314j4i3t054s0,4A454d0%110,0S3O3*3w0N3e4O3?4d0p0S111x0R0o0v0F0X0v0B0^4%0g4T3~4d10040d4.4I394L0F0K2#0F0(1g0F1i4@4c2j4;0q0b3V0k5a0k4P3Y0p110c0g0X0K1i2-1y4C2W5c4U2j0m110M3O5q4/55110w533R5g2Q2{0J5w5d3 4K040S3!5I5r3n5E2.5H5o3B5J4d0m4R042_5P5y5R041R4|0X4~50525V5X5z040s595b5=5)4y0J0F5i4-5V5x4^1=5t045v625{3J5g5i5k0p5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0Q0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110p0(0o6C0~2o6G2Q5n6N6a016L6I6A6n0F114h6,6-5a6 5L0N1Y1.726P6^6E6{616~6/660y6M3i6O5e6#5 2Q6(5?586w6y6y6 5f5*4Z7j0/7w697n5u7g7t6Q5,5.6U346/6Y6V736:7F6D6`7I7l4j7U6*5_7B7s6!046=6@7G7#4,6}7r6 717K6s7Y7:7i7?6|7N3 660H834d6o483V797-4J112Q0R0B0X0p874_7/6?806F7$7^3t8d5s5u7q8t7D0(112x7x1=4;4?7W7h6R5-6T518k8H6i110q3)0*4F4z4k8V0*4n1z0R4p8!2$2Y20222!0Q1-8X4n1F4H7X2Q0J0o0S0Q0%0g0o0r0i111r1t1v1x0k7z341M3j1G0V1j0Q8i0/0R0k0c0B0k0#0Y3z1s2n9h2n0C4{0Q0Y5i0k0B2-0k200B0@1/4E4t5M5O8T9H0k0Q0C2R0k5k0X0~1/2d0~4$0c0#1/2J0k0^0k5+6S5/1j0p004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0P0v5-0c9h0$0x275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0Xa/7Ya-0m5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0S0S2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0FbC5!b0bhb2bY0X2d9wb74=aG7E0gbObQ0FbSb}bf110Ta@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0v110z3z0Kct12cn7}5Lc-8ja@0%c=040!0X1w8Sao8W2X8:1K040A0-0k0g0I5i4$0v1/6|c_0J8.0k0D9y1jdidk0Fdm9(1/0Yc00c0r1/184{9$950X0)0Y1.0=2Ncz8L1idA0=0v0Q0,9e0I9Q0F1n1$2l9qdJ9:4(0m8i0K0Z9{138Y0-0/0;04.