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

.1280133S0:6ebq(tà[kr+.fèP7 é8]d;oFym4!ih19gcxTuO2C-=slnw_5v/aR)p050z0g0k0%0H0W0V0v0M0W0%0V0V0U010k0H0*010406050V0P0E0E0%0o0D040c0B0W0P0~0B0X0v020%0E0*0A0v0(0g180o0i0P0g0V050$1517191b130*041z1G051J0$1J1L1G130z0H0#0?0^0`0|0I0H0L0I0W1Z0I0k11050.0h0W0g1U0_0{011Y1!1$1!0k1,1.1*0k0h0B0z1b1+0o1H0k0I0?1e0V0*0%0X0|0R011:1W010r0:0g0X1m0g1*2b2d2i1=2l1.2o0E2q040a0v0t0o0B0*0B0V0H1h1j0,290o0o0g0M2L1z2s0X1H0$272X0k2524260z2u0|1$0X2n2I1*1R1T0@1;2+0H2-0X211S1*0*2Q1H2V2X32142c1j2?2j2{0o180W110v0J2U3612352t381=3a3c3e0R3h2d3j2V2*013o0%3d040v0b3s2W133v3m0|3y3A0v0F3E3u363w3K3e0!3O3G3Q3I3x0B3b3z3e0f3V3k371V3n3!3p3B0u3)3H3,3J3.3$3B0x3=3X3@3Z3#3L0K3}3l3 3S040J0d443+2@403/0J3g1A3i1I301z2;2!0z2(3w0M212A0+1S1H2 0g314j4i3t054s0,4A454d0n110,0r3O3*3w0Y3e4O3?4d0X0r111x0k0Z0M0H0o0M0P0^4%0g4T3~4d10040j4.4I394L0H0V2#0H0h1g0H1i4@4c2j4;0)0e3V0v5a0v4P3Y0X110*0g0o0V1i2-1y4C2W5c4U2j0B110U3O5q4/55110m533R5g2Q2{0E5w5d3 4K040r3!5I5r3n5E2.5H5o3B5J4d0B4R042_5P5y5R041R4|0o4~50525V5X5z040y595b5=5)4y0E0H5i4-5V5x4^1=5t045v625{3J5g5i5k0X5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0%0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110X0h0Z6C0~2o6G2Q5n6N6a016L6I6A6n0H114h6,6-5a6 5L0Y1Y1.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-4J112Q0k0P0o0X874_7/6?806F7$7^3t8d5s5u7q8t7D0h112x7x1=4;4?7W7h6R5-6T518k8H6i110)3)0$4F4z4k8V0$4n1z0k4p8!2$2Y20222!0%1-8X4n1F4H7X2Q0E0Z0r0%0n0g0Z0I0b111r1t1v1x0v7z341M3j1G0Q1j0%8i0/0k0v0*0P0v0w0L3z1s2n9h2n0#4{0%0L5i0v0P2-0v200P0@1/4E4t5M5O8T9H0v0%0#2R0v5k0o0~1/2d0~4$0*0w1/2J0v0^0v5+6S5/1j0X004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0c0M5-0*9h0t0D275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0oa/7Ya-0B5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0r0r2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0HbC5!b0bhb2bY0o2d9wb74=aG7E0gbObQ0HbSb}bf110Ta@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0M110C3z0Vct12cn7}5Lc-8ja@0nc=040O0o1w8Sao8W2X8:1K040S0-0v0g0N5i4$0M1/6|c_0E8.0v0l9y1jdidk0Hdm9(1/0Lc00*0I1/184{9$950o0s0L1.0=2Ncz8L1idA0=0M0%0,9e0N9Q0H1n1$2l9qdJ9:4(0B8i0V0q9{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

.1280133S0:6ebq(tà[kr+.fèP7 é8]d;oFym4!ih19gcxTuO2C-=slnw_5v/aR)p050z0g0k0%0H0W0V0v0M0W0%0V0V0U010k0H0*010406050V0P0E0E0%0o0D040c0B0W0P0~0B0X0v020%0E0*0A0v0(0g180o0i0P0g0V050$1517191b130*041z1G051J0$1J1L1G130z0H0#0?0^0`0|0I0H0L0I0W1Z0I0k11050.0h0W0g1U0_0{011Y1!1$1!0k1,1.1*0k0h0B0z1b1+0o1H0k0I0?1e0V0*0%0X0|0R011:1W010r0:0g0X1m0g1*2b2d2i1=2l1.2o0E2q040a0v0t0o0B0*0B0V0H1h1j0,290o0o0g0M2L1z2s0X1H0$272X0k2524260z2u0|1$0X2n2I1*1R1T0@1;2+0H2-0X211S1*0*2Q1H2V2X32142c1j2?2j2{0o180W110v0J2U3612352t381=3a3c3e0R3h2d3j2V2*013o0%3d040v0b3s2W133v3m0|3y3A0v0F3E3u363w3K3e0!3O3G3Q3I3x0B3b3z3e0f3V3k371V3n3!3p3B0u3)3H3,3J3.3$3B0x3=3X3@3Z3#3L0K3}3l3 3S040J0d443+2@403/0J3g1A3i1I301z2;2!0z2(3w0M212A0+1S1H2 0g314j4i3t054s0,4A454d0n110,0r3O3*3w0Y3e4O3?4d0X0r111x0k0Z0M0H0o0M0P0^4%0g4T3~4d10040j4.4I394L0H0V2#0H0h1g0H1i4@4c2j4;0)0e3V0v5a0v4P3Y0X110*0g0o0V1i2-1y4C2W5c4U2j0B110U3O5q4/55110m533R5g2Q2{0E5w5d3 4K040r3!5I5r3n5E2.5H5o3B5J4d0B4R042_5P5y5R041R4|0o4~50525V5X5z040y595b5=5)4y0E0H5i4-5V5x4^1=5t045v625{3J5g5i5k0X5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0%0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110X0h0Z6C0~2o6G2Q5n6N6a016L6I6A6n0H114h6,6-5a6 5L0Y1Y1.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-4J112Q0k0P0o0X874_7/6?806F7$7^3t8d5s5u7q8t7D0h112x7x1=4;4?7W7h6R5-6T518k8H6i110)3)0$4F4z4k8V0$4n1z0k4p8!2$2Y20222!0%1-8X4n1F4H7X2Q0E0Z0r0%0n0g0Z0I0b111r1t1v1x0v7z341M3j1G0Q1j0%8i0/0k0v0*0P0v0w0L3z1s2n9h2n0#4{0%0L5i0v0P2-0v200P0@1/4E4t5M5O8T9H0v0%0#2R0v5k0o0~1/2d0~4$0*0w1/2J0v0^0v5+6S5/1j0X004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0c0M5-0*9h0t0D275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0oa/7Ya-0B5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0r0r2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0HbC5!b0bhb2bY0o2d9wb74=aG7E0gbObQ0HbSb}bf110Ta@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0M110C3z0Vct12cn7}5Lc-8ja@0nc=040O0o1w8Sao8W2X8:1K040S0-0v0g0N5i4$0M1/6|c_0E8.0v0l9y1jdidk0Hdm9(1/0Lc00*0I1/184{9$950o0s0L1.0=2Ncz8L1idA0=0M0%0,9e0N9Q0H1n1$2l9qdJ9:4(0B8i0V0q9{138Y0-0/0;04.