Aller au contenu

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 :

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
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 : 5/5

.1280137w3pfbr42mgn5!OcC8[oà;:R0]=yé+)lSivPd q96t(.xF-kèa1/su_The050L0*0Q0Y0I0G0#0M0q0G0Y0#0#0B010Q0I0e010406050#0$0k0k0Y0h0C040H0u0G0$0~0u0m0M020Y0k0e0w0M0y0*180h0N0$0*0#050!1517191b130e04051G1z1J0!1G130L0I0J0?0^0`0|0^0m0l0$0Y0l0*0V0e0C0Q0)1i0M0)0I0l0)0G1/0)0Q11050.0g0G0*1S0_0{011.1:1=1:0Q1{1}1_0Q0h1H1*0?1e0#0e0Y0m0|0j011 1U010f0:0*0m1m0*1_2h2j2o212r1}2u0k2w040a0M0K0h0u0e0u0#0I1h1j0,2f0h0h0*0q2R1z2y0m1H0!1*2%2b2d2c1`0L2A1V0I0m2t2O1_1P1R0@202;2?0m0u2`1_0e2W1H2#2%37142i1j2|2p300h180G1_0Y1-2W0f0|030%0%0q310*1=2 0u0V0d0V0Z110M0Z1z0Y383b123a2z3d213f3h3j3l0*3n013p3r3t3v2@3y0V2m040M0j3F3H2j3J2#2:013O0Y3i1H3k0)3m3o3q3s0,3Y303!0d3C0d3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0i3C0i451A473K3c1T3N0u3g3=3Q3_3S3{3W3~4k403z0n3C0n4q37483b3/4c4A4g3V3}3u4G3x3z0P3C0P4M4s494v4b4x3P3@3R3T4U4j3w3!0b3C0b4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0s3C0s4{2$4}4u2}504y4d4f4C4h4E4W580V0O3C0O5d3-4P4a5i4-4e4/4D4V3 4Y3A0z110Z0z5v5f4Q515k5C5n5E4X3!0Z3B045W5v1K351z2`2*0L2d2/5y4V2_1Q1H340*363I463,054V5@2z0I0L0|3q2#5V3Q5 615o5F640M2E0*675T5q5X454)5h0W110,0f5_2$4t3/0c3C6p5}5g3e0f111x0Q3r0I0h0q0$0^6E0*6v6r5y10040R6L6j3e6m0I0#2b0I0g1g0I1i6R5x4 6O0F0x6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0!3G0M790M6M4 0m110e0*0h0#1i2?1y6/2$7b6S210u110B6v7p6(5h6O0t6%4~5h7e045=300k7v7c6k110f4x7J7q4b7f2W7H7P7x2p0u6t042=7V7C6T041P6W0h6Y6!6$7n6w3/6O0A6-7B1j6|0%633z424.7{6f6 426b2v7357831_773%7a7K7(5=0k0I7h6K7:7w7%7r7t7$6x3N7f7h7j0m7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0V4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0Y0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110m0g0%8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0Va03*7a9R3/6l040c1.1}8@996m6B8:9N8k9W8J8_0o9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0V5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0maD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0Ebw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0Q0$0ha@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0!5|5#5?5%5:1z0Q5*cD2-2(0Y1|cA0!5(1F7;5yaA0%0f0Y0W0*0%0)7 1r1t1v1x0MaG391M3J1G0p1j0Yb{0/0Q0M0e0$0M0D0l3=1s2tc?2t0J6V1!7h0M0$2?0M0g0u0$0@1~5{3t047N0h1z5|0M0Y0J2X0M7j0h0~1~2j0~0q0 0D1~2P0M0^0Mcn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^cP4 2C2t2v110Kd#7/395=6w3+6qcy9}8V630i3Ab*bX4?e1b-72b+e5e25R4;a33xe69Bb@am6ocl4 7Z7bel7D6z046B6D6F6Hbrch9611ckcsa|8-90coa?ey8K116+cv6:9$9~6^e16`3k819?ef70b.9-8ReX545DeVe!768*9D8,8t7i7kbsb~a|bve=b38BeC4Q7S2@7Ie^5yafdibIa#7G0ue ara/017Y117#f0bm8 7+dGcqeI8LbMe{bO0me!7 6{9,e(e184e8e43Zfw2ne$5Sfv3y9Bb?e-az1s9caqbEa,8`f48~7ge/8we;e{6N8AeI9Y8HfX9fb4eM6qd~9nfqe18SftbTfA8(eYfF4necfz40f/fHaZb 9a8ue:fRfba-f9g1e}aBa*b6b$eP9oe19qf;e9f?9vfyb/f}0V9vfDedaUe!gi8bfIfa7E3S0f2X0~ekg8e?g7fOgz0gcf2tfleAeIeEficpd@9|facufngV5~b%gg0V9^gjf|eW9/gneZe19/gsg*e!g(gxg0a|f27Offbx7!g5fc7!crgJg1gL040h2j1#gO6PgQ6A0fgC2Y0IgFh4gH040Vg5bKhbeLgYeNg!gff.a9e3goeWa5g-fFa5g;hze!aag^bkcde.8v2?h0gIccfJdFgTh3hta|a`f%g~fThNfNhWb3b54sged eQaQbbg.aQf^eee!5af{hGe1aWhJaYei7!hjhRgzhMg4g}7X7tcb7ohLfKgbh%f+gWaFf*7;fpe!bieTfuh@e1behCiq5rfC4Tg=irf bkgyb b^0-b{hVib8J0W0q110U3=0#ifb#fog#hwbZg)h{5HaR9;iyiYh`h;iVh~i0b_iGg5iK110(0h1wijdkdgcz2%cN1I040r0-0M0*0T7hdx0q1~9OiP0kcK0M0vd61jj2j40Ij6dE1~0lh80e0)1~186VdCc%0h0X0l1}0=2ThTa?jk0=0q0Y0,c:0Tdq0I1n1=2rc jtdL6Fdb7i0SdT6.0,8=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 : 5/5

.1280137w3pfbr42mgn5!OcC8[oà;:R0]=yé+)lSivPd q96t(.xF-kèa1/su_The050L0*0Q0Y0I0G0#0M0q0G0Y0#0#0B010Q0I0e010406050#0$0k0k0Y0h0C040H0u0G0$0~0u0m0M020Y0k0e0w0M0y0*180h0N0$0*0#050!1517191b130e04051G1z1J0!1G130L0I0J0?0^0`0|0^0m0l0$0Y0l0*0V0e0C0Q0)1i0M0)0I0l0)0G1/0)0Q11050.0g0G0*1S0_0{011.1:1=1:0Q1{1}1_0Q0h1H1*0?1e0#0e0Y0m0|0j011 1U010f0:0*0m1m0*1_2h2j2o212r1}2u0k2w040a0M0K0h0u0e0u0#0I1h1j0,2f0h0h0*0q2R1z2y0m1H0!1*2%2b2d2c1`0L2A1V0I0m2t2O1_1P1R0@202;2?0m0u2`1_0e2W1H2#2%37142i1j2|2p300h180G1_0Y1-2W0f0|030%0%0q310*1=2 0u0V0n0V0Z110M0Z1z0Y383b123a2z3d213f3h3j3l0*3n013p3r3t3v2@3y0V2m040M0j3F3H2j3J2#2:013O0Y3i1H3k0)3m3o3q3s0,3Y303!0d3C0d3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0i3C0i451A473K3c1T3N0u3g3=3Q3_3S3{3W3~4k403z0n3C0n4q37483b3/4c4A4g3V3}3u4G3x3z0P3C0P4M4s494v4b4x3P3@3R3T4U4j3w3!0b3C0b4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0s3C0s4{2$4}4u2}504y4d4f4C4h4E4W580V0O3C0O5d3-4P4a5i4-4e4/4D4V3 4Y3A0z110Z0z5v5f4Q515k5C5n5E4X3!0Z3B045W5v1K351z2`2*0L2d2/5y4V2_1Q1H340*363I463,054V5@2z0I0L0|3q2#5V3Q5 615o5F640M2E0*675T5q5X454)5h0W110,0f5_2$4t3/0c3C6p5}5g3e0f111x0Q3r0I0h0q0$0^6E0*6v6r5y10040R6L6j3e6m0I0#2b0I0g1g0I1i6R5x4 6O0F0x6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0!3G0M790M6M4 0m110e0*0h0#1i2?1y6/2$7b6S210u110B6v7p6(5h6O0t6%4~5h7e045=300k7v7c6k110f4x7J7q4b7f2W7H7P7x2p0u6t042=7V7C6T041P6W0h6Y6!6$7n6w3/6O0A6-7B1j6|0%633z424.7{6f6 426b2v7357831_773%7a7K7(5=0k0I7h6K7:7w7%7r7t7$6x3N7f7h7j0m7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0V4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0Y0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110m0g0%8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0Va03*7a9R3/6l040c1.1}8@996m6B8:9N8k9W8J8_0o9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0V5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0maD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0Ebw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0Q0$0ha@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0!5|5#5?5%5:1z0Q5*cD2-2(0Y1|cA0!5(1F7;5yaA0%0f0Y0W0*0%0)7 1r1t1v1x0MaG391M3J1G0p1j0Yb{0/0Q0M0e0$0M0D0l3=1s2tc?2t0J6V1!7h0M0$2?0M0g0u0$0@1~5{3t047N0h1z5|0M0Y0J2X0M7j0h0~1~2j0~0q0 0D1~2P0M0^0Mcn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^cP4 2C2t2v110Kd#7/395=6w3+6qcy9}8V630P3Ab*bX4?e1b-72b+e5e25R4;a33xe69Bb@am6ocl4 7Z7bel7D6z046B6D6F6Hbrch9611ckcsa|8-90coa?ey8K116+cv6:9$9~6^e16`3k819?ef70b.9-0VeR2n545DeVe!70b=aZb 9a8u7kbsb~a|bve?b38BeC4Q7S2@7Ie_5yafdibIa#7G0uf0ara/017Y117#f1bm8 7+dGcqeI8LbMe|bO0me*7 6{9,e)e184e8e43Zfxe$4TfA40fCe,9D8,e~aBa*fab e^fOeD8t7ie;c66q8Ja`e|5y9Y8Hf!9fb4eMfXeOd eQ8(bbeZe14neYfw8(ecfFeW8Sbjc88fe:8waqbEa,8`f58~9baCfo9|f-9nfre19qfubTfB3yaR9;f|e*9ve%5Sf_gi8bb?fKes0f0f2X0~ekfR8^a-gF990gcf2tfmeAeIeEfjcpd@gdcteKf+7;fqe*9^gje9gl9/fzb/fGe!fD5medaUg!9Bgxfbf37Ofgbx7!g8fc7ZffgI7dgK040h2j1#gN6PgP6AgAgC0IgEg5fb8_0Vg~bKh9eLgceN5~b%9oe1aaeTfveee*a5g*f=a9g.55g+eWaagwbkg0f6g22?g~fQhhe.6UgReHepa_8Ahb7FhNg4hqa|fnb6b$ePhtaQf;f_5af^hye1h;gsg:69h@g?hKei7!hgccgy7gfUg3hP7tcb7ocdfL9ch$f,gV04c)4sh+f.h-bihwgkg,behBf_beh_gpe1bihJhKe-a|b^0-b{crhRiC0q110U3=0#ieb#fphsgg5He3hGe*bRh=g;e6bViviVi!h}fJg^11b_iFg~0WiJ040(0h1wgXdkdgcz2%cN1I040r0-0M0*0T7hdx0q1~9OiN0kcK0M0vd61jj4j60Ij8dE1~0lh60e0)1~186VdCc%0h0X0l1}0=2TdFgS2Sc%0q0Y0,c:0Tdq0I1n1=2rc jvdL6Fdb7i0SdT6.0,8=0;04.