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
1
2
3
4
5
6
7
8
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
1
2
3
4
5
6
7
8
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 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
>>> 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

.128013ita;Fn2R!7+14 f08elorO=[à]/mC3dvT.S5éwbcyq:-up)_9hxPès6(gk050F0s0c0d0b0t0$0o0O0t0d0$0$0x010c0b0U010406050$0T0C0C0d0v0P040J0u0t0T0~0u0g0o020d0C0U0e0o0i0s180v0Q0T0s0$050B1517191b130U04051G1z1J0B1G130F0b0G0?0^0`0|0^0g0)0T0d0)0s0S0U0P0c0Y1i0o0Y0b0)0Y0t1/0Y0c11050.0N0t0s1S0_0{011.1:1=1:0c1{1}1_0c0v1H1*0?1e0$0U0d0g0|0h011 1U010p0:0s0g1m0s1_2h2j2o212r1}2u0C2w040a0o0!0v0u0U0u0$0b1h1j0,2f0v0v0s0O2R1z2y0g1H0B1*2%2b2d2c1`0F2A1V0b0g2t2O1_1P1R0@202;2?0g0u2`1_0U2W1H2#2%37142i1j2|2p300v180t1_0d1-2W0p0|030W0W0O310s1=2 0u0S0E0S0m110o0m1z0d383b123a2z3d213f3h3j3l0s3n013p3r3t3v2@3y0S2m040o0h3F3H2j3J2#2:013O0d3i1H3k0Y3m3o3q3s0,3Y303!0E3C0E3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0n3C0n451A473K3c1T3N0u3g3=3Q3_3S3{3W3~4k403z0K3C0K4q37483b3/4c4A4g3V3}3u4G3x3z0%3C0%4M4s494v4b4x3P3@3R3T4U4j3w3!0k3C0k4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0r3C0r4{2$4}4u2}504y4d4f4C4h4E4W580S0X3C0X5d3-4P4a5i4-4e4/4D4V3 4Y3A0q110m0q5v5f4Q515k5C5n5E4X3!0m3B045W5v1K351z2`2*0F2d2/5y4V2_1Q1H340s363I463,054V5@2z0b0F0|3q2#5V3Q5 615o5F640o2E0s675T5q5X454)5h0*110,0p5_2$4t3/0M3C6p5}5g3e0p111x0c3r0b0v0O0T0^6E0s6v6r5y10040(6L6j3e6m0b0$2b0b0N1g0b1i6R5x4 6O0V0R6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0B3G0o790o6M4 0g110U0s0v0$1i2?1y6/2$7b6S210u110x6v7p6(5h6O0y6%4~5h7e045=300C7v7c6k110p4x7J7q4b7f2W7H7P7x2p0u6t042=7V7C6T041P6W0v6Y6!6$7n6w3/6O0A6-7B1j6|0W633z424.7{6f6 426b2v7357831_773%7a7K7(5=0C0b7h6K7:7w7%7r7t7$6x3N7f7h7j0g7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0S4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0d0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110g0N0W8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0Sa03*7a9R3/6l040M1.1}8@996m6B8:9N8k9W8J8_0j9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0S5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0gaD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0lbw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0c0T0va@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0B5|5#5?5%5:1z0c5*cD2-2(0d1|cA0B5(1F7;5yaA0W0p0d0*0s0W0Y7 1r1t1v1x0oaG391M3J1G0w1j0db{0/0c0o0U0T0o0L0)3=1s2tc?2t0G6V1!7h0o0T2?0o0N0u0T0@1~5{3t047N0v1z5|0o0d0G2X0o7j0v0~1~2j0~0O0 0L1~2P0o0^0ocn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^2dcJ1}3/d(251@282G1`2-2e3s0;3b2l2n5y2C2t2v2xa/2q2s6c110!d#7/c*2)cG2,5+dW4X0$5/2{4 5F325;5$c*csa|4R534TbX4?0n3A3CbL3G7^8,5P4S5m4;a33xeA3$3(5McdeHeweJey3ZeA7 0o448beFe5ev5B545D9?eM8(3%4pe#aHeG5jeI55b/40eA9q0o4Le;b6e?5A5le_9-8R0S9^0o4$f04(e%eSe)exe`e-a00o4`fc4|eRe@eTf5e,f7aM0o5cfn5efpf35ReKaUf7ba0o5ufy5wb e(f4e+eLf7bZ5K5!1M5$cMcC2(cFcE3/5.1H5(1Iercw39cy9}8V63eA6h3k81ftf;aR9;eVe{eBb!b@am6ocl4 7Z7bg37D6z046B6D6F6Hbrch9611cket4Q6U7+dGcqgg8K116+cv6:9$9~6^eNb*f|e-2mb.f6gzb=aZfL8t7i7kbsb~a|bvgOb38Bgkay7G0u7IgR5yafdibIa#gWgYare57Y117#gZbm8 gncpec9|e58LbMgkbO0gf77 6{9,f^3yf`bTeWh5gH9D8,7S1s9caqbEa,8`g%8~7ggL8wgNgU9f04gTg_b 9Y8HhqaEb4gu6qf.9ng eA8Sh2h7f}4ngEh4hH8bb?hc7F8ugMhk01gQg+gJazheaCg|hu7`b%9oe|gAfif79v72b+ez0S9qbjc87(3S0p2X0~g2hYgPa-i14Q0Ncf2tgqcjgq8-90coa?i9gshB7;g~f79^hIh=h89/h;gBil9BhQe5g#7Og:bx7!hVg-7!crhhe%i6040v2j1#ig6Pib6A0ph}2Y0bi0iGb 8_0ShVbKiNgth%gv5~h*hFa9h-gFi-hMfPeAaahPbkh`g(hThoiCi3iWeugma=93hya_8AiPhShn2?iNb54sb$gxh+aQbbi/5ai;fEeAaWi^bkg07!iVcchRhm8vjbiz7X7tcb7ocdhdaBa*j5ciaFii6rikeAbif?h3i=5rh6iof}bijqi_hbiw11b_b{iFjviw0O110f3=0$hgfojff/gy5Hi.h4bRjm69f;5Ihai`0|b^0-j)hV0*j-040H0v1wjMcxdgcz2%f(fY2*cHd?kj5:cO0D0-0o0s0Z7hdx0O1~9Oj;0CcK0o0zd61jkvkx0bkzdE1~0)iK0U0Y1~186VdCc%0v0#0)1}0=2TdFg@2Sc%0O0d0,c:0Zdq0b1n1=2rc kWdL6Fdb7i0IdT6.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

.128013ita;Fn2R!7+14 f08elorO=[à]/mC3dvT.S5éwbcyq:-up)_9hxPès6(gk050F0s0c0d0b0t0$0o0O0t0d0$0$0x010c0b0U010406050$0T0C0C0d0v0P040J0u0t0T0~0u0g0o020d0C0U0e0o0i0s180v0Q0T0s0$050B1517191b130U04051G1z1J0B1G130F0b0G0?0^0`0|0^0g0)0T0d0)0s0S0U0P0c0Y1i0o0Y0b0)0Y0t1/0Y0c11050.0N0t0s1S0_0{011.1:1=1:0c1{1}1_0c0v1H1*0?1e0$0U0d0g0|0h011 1U010p0:0s0g1m0s1_2h2j2o212r1}2u0C2w040a0o0!0v0u0U0u0$0b1h1j0,2f0v0v0s0O2R1z2y0g1H0B1*2%2b2d2c1`0F2A1V0b0g2t2O1_1P1R0@202;2?0g0u2`1_0U2W1H2#2%37142i1j2|2p300v180t1_0d1-2W0p0|030W0W0O310s1=2 0u0S0K0S0m110o0m1z0d383b123a2z3d213f3h3j3l0s3n013p3r3t3v2@3y0S2m040o0h3F3H2j3J2#2:013O0d3i1H3k0Y3m3o3q3s0,3Y303!0E3C0E3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0n3C0n451A473K3c1T3N0u3g3=3Q3_3S3{3W3~4k403z0K3C0K4q37483b3/4c4A4g3V3}3u4G3x3z0%3C0%4M4s494v4b4x3P3@3R3T4U4j3w3!0k3C0k4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0r3C0r4{2$4}4u2}504y4d4f4C4h4E4W580S0X3C0X5d3-4P4a5i4-4e4/4D4V3 4Y3A0q110m0q5v5f4Q515k5C5n5E4X3!0m3B045W5v1K351z2`2*0F2d2/5y4V2_1Q1H340s363I463,054V5@2z0b0F0|3q2#5V3Q5 615o5F640o2E0s675T5q5X454)5h0*110,0p5_2$4t3/0M3C6p5}5g3e0p111x0c3r0b0v0O0T0^6E0s6v6r5y10040(6L6j3e6m0b0$2b0b0N1g0b1i6R5x4 6O0V0R6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0B3G0o790o6M4 0g110U0s0v0$1i2?1y6/2$7b6S210u110x6v7p6(5h6O0y6%4~5h7e045=300C7v7c6k110p4x7J7q4b7f2W7H7P7x2p0u6t042=7V7C6T041P6W0v6Y6!6$7n6w3/6O0A6-7B1j6|0W633z424.7{6f6 426b2v7357831_773%7a7K7(5=0C0b7h6K7:7w7%7r7t7$6x3N7f7h7j0g7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0S4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0d0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110g0N0W8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0Sa03*7a9R3/6l040M1.1}8@996m6B8:9N8k9W8J8_0j9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0S5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0gaD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0lbw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0c0T0va@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0B5|5#5?5%5:1z0c5*cD2-2(0d1|cA0B5(1F7;5yaA0W0p0d0*0s0W0Y7 1r1t1v1x0oaG391M3J1G0w1j0db{0/0c0o0U0T0o0L0)3=1s2tc?2t0G6V1!7h0o0T2?0o0N0u0T0@1~5{3t047N0v1z5|0o0d0G2X0o7j0v0~1~2j0~0O0 0L1~2P0o0^0ocn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^2dcJ1}3/d(251@282G1`2-2e3s0;3b2l2n5y2C2t2v2xa/2q2s6c110!d#7/c*2)cG2,5+dW4X0$5/2{4 5F325;5$c*csa|4R534TbX4?0%3A3CbL3G7^8,5P4S5m4;a33xeA3$3(5McdeHeweJey3ZeA7 0o448beFe5ev5B545D9?eM8(3%4pe#aHeG5jeI55b/40eA9q0o4Le;b6e?5A5le_9-0SeA9^0o4$f04(e%eSe)exe`e-a00o4`fc4|eRe@eTf5e,f7aQ3%5cfn5efpf35ReKaUfuba0o5ufy5wb e(f4e+eLfubZ5K5!1M5$cMcC2(cFcE3/5.1H5(1Iercw39cy9}8V63eA6h3k81ftf;aR9;eVe{eBb!b@am6ocl4 7Z7bg37D6z046B6D6F6Hbrch9611cket4Q6U7+dGcqgg8K116+cv6:9$9~6^eNb*f|e-2mb.f6gzb=aZfL8t7i7kbsb~a|bvgOb38Bgkay7G0u7IgR5yafdibIa#gWgYare57Y117#gZbm8 gncpec9|e58LbMgkbO0gfu7 6{9,f^0S8472b+ezh59Bb?8,7S1s9caqbEa,8`g%8~7ggL8wgNgU9f04gTg_b 9Y8HhraEb4gu6qf.9ng eA8Sh2bTeW8(gEh4hI8bhce%gK8v2?hl01gQg+gJazhfaCg|hv7`b%9oe|gAfifu9vh7gBh:hbgIeu6A0p0p2X0~g2hZgPa-i14Q0Ncf2tgqcjgq8-90coa?i9gshC7;g~fu9^hJh8hL9/h=h/f8h^9D8Jg#7Og:bx7!hWg-7!crhie%i6040v2j1#ig6Pibh{h}2Y0bi0iGb 8_0ShWbKiNgth(gv5~h+hGa9h.gFi,hNfPeAaahQbkc88f8ugMiCi3iVh`g=a=93hza_8AiP7Fi{hpiNb54sb$gxh,fvinh?eA5ai:fEjkiuaYg07!iUcchdj8hohViz7X7tcb7ocdheaBa*j4ciaFii6rikeAbif?h3i;5rf`hKf}bii@i^h_ae11b_b{iFjue50*0O110f3=0$hhfojef/gy5Hi-h4bRjm69f;5IgHivj+j$0-j(hWj,110H0v1wjLcxdgcz2%f(fY2*cHd?ki5:cO0D0-0o0s0Z7hdx0O1~9Oj;0CcK0o0zd61jkukw0bkydE1~0)iK0U0Y1~186VdCc%0v0#0)1}0=2TdFg@2Sc%0O0d0,c:0Zdq0b1n1=2rc kVdL6Fdb7i0IdT6.0,8=0;04.