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

.128013snTc)wuql3 (è;ébokp/h1tà[aRPmy7!]f4O_296ev-8Fx+dCiSg:5=.0r050W0P0x0A0Y0j0b0l0e0j0A0b0b0%010x0Y0t010406050b0h0D0D0A0*0E040Z0r0j0h0~0r0c0l020A0D0t0o0l0B0P180*0i0h0P0b050u1517191b130t041z1G051J0u1J1L1G130W0Y0Q0?0^0`0|0v0Y0!0v0j1Z0v0x11050.0q0j0P1U0_0{011Y1!1$1!0x1,1.1*0x0q0r0W1b1+0*1H0x0v0?1e0b0t0A0c0|0M011:1W010I0:0P0c1m0P1*2b2d2i1=2l1.2o0D2q040a0l0C0*0r0t0r0b0Y1h1j0,290*0*0P0e2L1z2s0c1H0u272X0x2524260W2u0|1$0c2n2I1*1R1T0@1;2+0Y2-0c211S1*0t2Q1H2V2X32142c1j2?2j2{0*180j110l0w2U3612352t381=3a3c3e0M3h2d3j2V2*013o0A3d040l0k3s2W133v3m0|3y3A0l0J3E3u363w3K3e0$3O3G3Q3I3x0r3b3z3e0O3V3k371V3n3!3p3B0F3)3H3,3J3.3$3B0S3=3X3@3Z3#3L0N3}3l3 3S040w0)443+2@403/0w3g1A3i1I301z2;2!0W2(3w0e212A0+1S1H2 0P314j4i3t054s0,4A454d0s110,0I3O3*3w0g3e4O3?4d0c0I111x0x0L0e0Y0*0e0h0^4%0P4T3~4d10040m4.4I394L0Y0b2#0Y0q1g0Y1i4@4c2j4;0f0#3V0l5a0l4P3Y0c110t0P0*0b1i2-1y4C2W5c4U2j0r110%3O5q4/55110z533R5g2Q2{0D5w5d3 4K040I3!5I5r3n5E2.5H5o3B5J4d0r4R042_5P5y5R041R4|0*4~50525V5X5z040H595b5=5)4y0D0Y5i4-5V5x4^1=5t045v625{3J5g5i5k0c5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0A0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110c0q0L6C0~2o6G2Q5n6N6a016L6I6A6n0Y114h6,6-5a6 5L0g1Y1.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 660V834d6o483V797-4J112Q0x0h0*0c874_7/6?806F7$7^3t8d5s5u7q8t7D0q112x7x1=4;4?7W7h6R5-6T518k8H6i110f3)0u4F4z4k8V0u4n1z0x4p8!2$2Y20222!0A1-8X4n1F4H7X2Q0D0L0I0A0s0P0L0v0k111r1t1v1x0l7z341M3j1G0K1j0A8i0/0x0l0t0h0l0p0!3z1s2n9h2n0Q4{0A0!5i0l0h2-0l200h0@1/4E4t5M5O8T9H0l0A0Q2R0l5k0*0~1/2d0~4$0t0p1/2J0l0^0l5+6S5/1j0c004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0Z0e5-0t9h0C0E275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0*a/7Ya-0r5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0I0I2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0YbC5!b0bhb2bY0*2d9wb74=aG7E0PbObQ0YbSb}bf110Ra@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0e110T3z0bct12cn7}5Lc-8ja@0sc=040d0*1w8Sao8W2X8:1K040X0-0l0P0U5i4$0e1/6|c_0D8.0l0y9y1jdidk0Ydm9(1/0!c00t0v1/184{9$950*0n0!1.0=2Ncz8L1idA0=0e0A0,9e0U9Q0Y1n1$2l9qdJ9:4(0r8i0b0(9{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

.128013snTc)wuql3 (è;ébokp/h1tà[aRPmy7!]f4O_296ev-8Fx+dCiSg:5=.0r050W0P0x0A0Y0j0b0l0e0j0A0b0b0%010x0Y0t010406050b0h0D0D0A0*0E040Z0r0j0h0~0r0c0l020A0D0t0o0l0B0P180*0i0h0P0b050u1517191b130t041z1G051J0u1J1L1G130W0Y0Q0?0^0`0|0v0Y0!0v0j1Z0v0x11050.0q0j0P1U0_0{011Y1!1$1!0x1,1.1*0x0q0r0W1b1+0*1H0x0v0?1e0b0t0A0c0|0M011:1W010I0:0P0c1m0P1*2b2d2i1=2l1.2o0D2q040a0l0C0*0r0t0r0b0Y1h1j0,290*0*0P0e2L1z2s0c1H0u272X0x2524260W2u0|1$0c2n2I1*1R1T0@1;2+0Y2-0c211S1*0t2Q1H2V2X32142c1j2?2j2{0*180j110l0w2U3612352t381=3a3c3e0M3h2d3j2V2*013o0A3d040l0k3s2W133v3m0|3y3A0l0J3E3u363w3K3e0$3O3G3Q3I3x0r3b3z3e0O3V3k371V3n3!3p3B0F3)3H3,3J3.3$3B0S3=3X3@3Z3#3L0N3}3l3 3S040w0)443+2@403/0w3g1A3i1I301z2;2!0W2(3w0e212A0+1S1H2 0P314j4i3t054s0,4A454d0s110,0I3O3*3w0g3e4O3?4d0c0I111x0x0L0e0Y0*0e0h0^4%0P4T3~4d10040m4.4I394L0Y0b2#0Y0q1g0Y1i4@4c2j4;0f0#3V0l5a0l4P3Y0c110t0P0*0b1i2-1y4C2W5c4U2j0r110%3O5q4/55110z533R5g2Q2{0D5w5d3 4K040I3!5I5r3n5E2.5H5o3B5J4d0r4R042_5P5y5R041R4|0*4~50525V5X5z040H595b5=5)4y0D0Y5i4-5V5x4^1=5t045v625{3J5g5i5k0c5m5C3Y4;5B5;5Q0|5~114a6l5(0|4;5^5V065b63545)0,4|2_0A0.4,5%640|6668326z5D5*4{4}4 2T6r6J016j6h465S5~606Z4:116v326x5`6m3x110c0q0L6C0~2o6G2Q5n6N6a016L6I6A6n0Y114h6,6-5a6 5L0g1Y1.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 660V834d6o483V797-4J112Q0x0h0*0c874_7/6?806F7$7^3t8d5s5u7q8t7D0q112x7x1=4;4?7W7h6R5-6T518k8H6i110f3)0u4F4z4k8V0u4n1z0x4p8!2$2Y20222!0A1-8X4n1F4H7X2Q0D0L0I0A0s0P0L0v0k111r1t1v1x0l7z341M3j1G0K1j0A8i0/0x0l0t0h0l0p0!3z1s2n9h2n0Q4{0A0!5i0l0h2-0l200h0@1/4E4t5M5O8T9H0l0A0Q2R0l5k0*0~1/2d0~4$0t0p1/2J0l0^0l5+6S5/1j0c004Z9i0_0?4%4)4+2Q961I3j2;3w1@1#1%1)8=3w2w2n2p112C0Z0e5-0t9h0C0E275:344y8=334j8Ua33Y5L4M8D0|5!5c8O464X044Z4#9?4*7$at6X118G7T7}7E9)8K9+aG56973i8c7D6c5j5l1x8l657M7|6W7VaK6W7E4y5Ga!0|5L5N0*a/7Ya-0r5U7m7}5Z115$a%7XaM8J7R8MaQ7*7A6.aL7u6%b13w7{a|a+aW6e6gax6)046ka*7X896qbq3w6u7+8u5|6daYa@bg7_6/a,8@7v7%3taUbF4Y0I0I2R0~4Nbe3YbD8ybF8A048Cbm5?aJ7(bb7P9*7Sb(a(8Qbx7b11a=a@7E0YbC5!b0bhb2bY0*2d9wb74=aG7E0PbObQ0YbSb}bf110Ra@8977b-7XaRbx7CbM045haX6fbJ5p7`a$cc7OaNb5aicjbv5Ac5bjbBb#8Eb86,7,7a6/5Lcab@cGcsbC8wcRcpbHbdbu8P04aSbKcM7Bb;048g8i8Ncx5K0e110T3z0bct12cn7}5Lc-8ja@0sc=040d0*1w8Sao8W2X8:1K040X0-0l0P0U5i4$0e1/6|c_0D8.0l0y9y1jdidk0Ydm9(1/0!c00t0v1/184{9$950*0n0!1.0=2Ncz8L1idA0=0e0A0,9e0U9Q0Y1n1$2l9qdJ9:4(0r8i0b0(9{138Y0-0/0;04.