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

.128013oèPf8gbr1a3tv!=uàn9xsc)7qR/p0Od; lk5:+Fy2éChwT6e[(S]_im.4-050F0W0m0k0$0I0v0H0w0I0k0v0v0p010m0$0C010406050v0q0%0%0k0i0O040Z0b0I0q0~0b0s0H020k0%0C0G0H0A0W180i0z0q0W0v050B1517191b130C04051G1z1J0B1G130F0$0n0?0^0`0|0^0s0g0q0k0g0W0*0C0O0m0S1i0H0S0$0g0S0I1/0S0m11050.0h0I0W1S0_0{011.1:1=1:0m1{1}1_0m0i1H1*0?1e0v0C0k0s0|0P011 1U010e0:0W0s1m0W1_2h2j2o212r1}2u0%2w040a0H0d0i0b0C0b0v0$1h1j0,2f0i0i0W0w2R1z2y0s1H0B1*2%2b2d2c1`0F2A1V0$0s2t2O1_1P1R0@202;2?0s0b2`1_0C2W1H2#2%37142i1j2|2p300i180I1_0k1-2W0e0|030#0#0w310W1=2 0b0*0l0*0j110H0j1z0k383b123a2z3d213f3h3j3l0W3n013p3r3t3v2@3y0*2m040H0P3F3H2j3J2#2:013O0k3i1H3k0S3m3o3q3s0,3Y303!0l3C0l3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0)3C0)451A473K3c1T3N0b3g3=3Q3_3S3{3W3~4k403z0K3C0K4q37483b3/4c4A4g3V3}3u4G3x3z0V3C0V4M4s494v4b4x3P3@3R3T4U4j3w3!0y3C0y4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0f3C0f4{2$4}4u2}504y4d4f4C4h4E4W580*0t3C0t5d3-4P4a5i4-4e4/4D4V3 4Y3A0D110j0D5v5f4Q515k5C5n5E4X3!0j3B045W5v1K351z2`2*0F2d2/5y4V2_1Q1H340W363I463,054V5@2z0$0F0|3q2#5V3Q5 615o5F640H2E0W675T5q5X454)5h0J110,0e5_2$4t3/0T3C6p5}5g3e0e111x0m3r0$0i0w0q0^6E0W6v6r5y10040Y6L6j3e6m0$0v2b0$0h1g0$1i6R5x4 6O0x0L6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0B3G0H790H6M4 0s110C0W0i0v1i2?1y6/2$7b6S210b110p6v7p6(5h6O0X6%4~5h7e045=300%7v7c6k110e4x7J7q4b7f2W7H7P7x2p0b6t042=7V7C6T041P6W0i6Y6!6$7n6w3/6O0!6-7B1j6|0#633z424.7{6f6 426b2v7357831_773%7a7K7(5=0%0$7h6K7:7w7%7r7t7$6x3N7f7h7j0s7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0*4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0k0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110s0h0#8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0*a03*7a9R3/6l040T1.1}8@996m6B8:9N8k9W8J8_0o9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0*5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0saD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0Mbw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0m0q0ia@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0B5|5#5?5%5:1z0m5*cD2-2(0k1|cA0B5(1F7;5yaA0#0e0k0J0W0#0S7 1r1t1v1x0HaG391M3J1G0E1j0kb{0/0m0H0C0q0H0Q0g3=1s2tc?2t0n6V1!7h0H0q2?0H0h0b0q0@1~5{3t047N0i1z5|0H0k0n2X0H7j0i0~1~2j0~0w0 0Q1~2P0H0^0Hcn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^2dcJ1}3/d(251@282G1`2-2e3s0;3b2l2n5y2C2t2v2xa/2q2s6c110dd#7/c*2)cG2,5+dW4X0v5/2{4 5F325;5$c*csa|4R534TbX4?0)3A3CbL3G7^8,5P4S5m4;a33xeA3$3(5McdeHeweJey3ZeA7 0H448beFe5ev5B545D9?eM8(3%4pe#aHeG5jeI55b/40eA9q0H4Le;b6e?5A5le_9-8R0*9^0H4$f04(e%eSe)exe`e-a00H4`fc4|eRe@eTf5e,f7aM0H5cfn5efpf35ReKaUf7ba0H5ufy5wb 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|bvgOb38Bgkay7G0b7IgR5yafdibIa#gWgYare57Y117#gZbm8 gncpec9|e58LbMgkbO0sf77 6{9,f^3yf`bTeWh5gH9D8,7S1s9caqbEa,8`g%8~7ggL8wgNgU9f04gTg_b 9Y8HhqaEb4gu6qf.9ng eA8Sh2h7f}4ngEh4hH8bb?hc7F8ugMhk01gQg+gJazheaCg|hu7`b%9oe|gAfif79v72b+ez0*9qbjc87(3S0e2X0~g2hYgPa-i14Q0hcf2tgqcjgq8-90coa?i9gshB7;g~f79^hIh=h89/h;gBil9BhQe5g#7Og:bx7!hVg-7!crhhe%i6040i2j1#ig6Pib6A0eh}2Y0$i0iGb 8_0*hVbKiNgth%gv5~h*hFa9h-gFi-hMfPeAaahPbkh`g(hThoiCi3iWeugma=93hya_8AiPhShn2?iNb54sb$gxh+aQbbi/5ai;fEeAaWi^bkg07!iVcchRhm8vjbiz7X7tcb7ocdhdaBa*j5ciaFii6rikeAbif?h3i=5rh6iof}bijqi_hbiw11b_b{iFjviw0w110N3=0vhgfojff/gy5Hi.h4bRjm69f;5Ihai`0|b^0-j)hV0Jj-040U0i1wjMcxdgcz2%f(fY2*cHd?kj5:cO0R0-0H0W0u7hdx0w1~9Oj;0%cK0H0rd61jkvkx0$kzdE1~0giK0C0S1~186VdCc%0i0c0g1}0=2TdFg@2Sc%0w0k0,c:0udq0$1n1=2rc kWdL6Fdb7i0(dT6.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

.128013oèPf8gbr1a3tv!=uàn9xsc)7qR/p0Od; lk5:+Fy2éChwT6e[(S]_im.4-050F0W0m0k0$0I0v0H0w0I0k0v0v0p010m0$0C010406050v0q0%0%0k0i0O040Z0b0I0q0~0b0s0H020k0%0C0G0H0A0W180i0z0q0W0v050B1517191b130C04051G1z1J0B1G130F0$0n0?0^0`0|0^0s0g0q0k0g0W0*0C0O0m0S1i0H0S0$0g0S0I1/0S0m11050.0h0I0W1S0_0{011.1:1=1:0m1{1}1_0m0i1H1*0?1e0v0C0k0s0|0P011 1U010e0:0W0s1m0W1_2h2j2o212r1}2u0%2w040a0H0d0i0b0C0b0v0$1h1j0,2f0i0i0W0w2R1z2y0s1H0B1*2%2b2d2c1`0F2A1V0$0s2t2O1_1P1R0@202;2?0s0b2`1_0C2W1H2#2%37142i1j2|2p300i180I1_0k1-2W0e0|030#0#0w310W1=2 0b0*0K0*0j110H0j1z0k383b123a2z3d213f3h3j3l0W3n013p3r3t3v2@3y0*2m040H0P3F3H2j3J2#2:013O0k3i1H3k0S3m3o3q3s0,3Y303!0l3C0l3*2!3I133.3M0|3;3?053^3`3U3|3X2=3Z3z0)3C0)451A473K3c1T3N0b3g3=3Q3_3S3{3W3~4k403z0K3C0K4q37483b3/4c4A4g3V3}3u4G3x3z0V3C0V4M4s494v4b4x3P3@3R3T4U4j3w3!0y3C0y4%3,4O3L4*3:4,4z4.4B4:4i4F4?3z0f3C0f4{2$4}4u2}504y4d4f4C4h4E4W580*0t3C0t5d3-4P4a5i4-4e4/4D4V3 4Y3A0D110j0D5v5f4Q515k5C5n5E4X3!0j3B045W5v1K351z2`2*0F2d2/5y4V2_1Q1H340W363I463,054V5@2z0$0F0|3q2#5V3Q5 615o5F640H2E0W675T5q5X454)5h0J110,0e5_2$4t3/0T3C6p5}5g3e0e111x0m3r0$0i0w0q0^6E0W6v6r5y10040Y6L6j3e6m0$0v2b0$0h1g0$1i6R5x4 6O0x0L6v134r5`3.6601623b3!3$5B6=565p4l3#2n6c6e4=6 6`0B3G0H790H6M4 0s110C0W0i0v1i2?1y6/2$7b6S210b110p6v7p6(5h6O0X6%4~5h7e045=300%7v7c6k110e4x7J7q4b7f2W7H7P7x2p0b6t042=7V7C6T041P6W0i6Y6!6$7n6w3/6O0!6-7B1j6|0#633z424.7{6f6 426b2v7357831_773%7a7K7(5=0%0$7h6K7:7w7%7r7t7$6x3N7f7h7j0s7l7_7=117A7:8e218h115L8C7Q017?7^8I4P7{7}0*4n80606?685U4m71868V824H8R8a788d8J7E0,6W2=0k0.6J8q3/7s047u8l8D7R7)6V6X6Z2Z8N8n0|7z8y5y7E8g8i2W986)117@7:6.396;8U6@2j3!4J8T876~8%4J852F9s694I8)8c798}3:110s0h0#8.0~2u8=2W7m378m8r0|8_8{9Q9E8F5Y8M9k8O9m7|6^4Z659%8$5G4!9w6d8#748%4!2%3G9j5^9l678Q4^9r9=888%4^9:9y8X0*a03*7a9R3/6l040T1.1}8@996m6B8:9N8k9W8J8_0o9V3Iadal7F2W8h8j9e7y116,9i8y8P9)0*5aa16}9zaL8Z9xa29t5GaMabac8+7W8s7)an9M0/9d8|as8pa+a!8~7*917.0saD2p97949S9Fa$8/a(8?a{8z049h4NaI9%8Q5saN8W5q5sa6aTaPbaaXaYax7d9G9I9Kaoa)1xak4 9Ubt7Dbn9Ja%8;br9Paw9E8_0Mbw2p9Y3EaHb2aJ9o3z5K9+a76g5IbfaOa8bR9_3JbNb8aK5WbSbgbY3BbWbc6 b)b!ac9Eaf2W0m0q0ia@a.95a}9Hbza bB6JbD3,bl5h9Uavc79E9H112Da^216O6Qb2aya;7,926#b}9#b 6*9!5^0B5|5#5?5%5:1z0m5*cD2-2(0k1|cA0B5(1F7;5yaA0#0e0k0J0W0#0S7 1r1t1v1x0HaG391M3J1G0E1j0kb{0/0m0H0C0q0H0Q0g3=1s2tc?2t0n6V1!7h0H0q2?0H0h0b0q0@1~5{3t047N0i1z5|0H0k0n2X0H7j0i0~1~2j0~0w0 0Q1~2P0H0^0Hcn7-2R6b006Bc@0_0?6E6G6I2Wc(1K3J2`3/1W1Yd41%1)1+1j231;1?1^2dcJ1}3/d(251@282G1`2-2e3s0;3b2l2n5y2C2t2v2xa/2q2s6c110dd#7/c*2)cG2,5+dW4X0v5/2{4 5F325;5$c*csa|4R534TbX4?0V3A3CbL3G7^8,5P4S5m4;a33xeA3$3(5McdeHeweJey3ZeA7 0H448beFe5ev5B545D9?eM8(3%4pe#aHeG5jeI55b/40eA9q0H4Le;b6e?5A5le_9-0*eA9^0H4$f04(e%eSe)exe`e-a00H4`fc4|eRe@eTf5e,f7aQ3%5cfn5efpf35ReKaUfuba0H5ufy5wb 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|bvgOb38Bgkay7G0b7IgR5yafdibIa#gWgYare57Y117#gZbm8 gncpec9|e58LbMgkbO0sfu7 6{9,f^0*8472b+ezh59Bb?8,7S1s9caqbEa,8`g%8~7ggL8wgNgU9f04gTg_b 9Y8HhraEb4gu6qf.9ng eA8Sh2bTeW8(gEh4hI8bhce%gK8v2?hl01gQg+gJazhfaCg|hv7`b%9oe|gAfifu9vh7gBh:hbgIeu6A0e0e2X0~g2hZgPa-i14Q0hcf2tgqcjgq8-90coa?i9gshC7;g~fu9^hJh8hL9/h=h/f8h^9D8Jg#7Og:bx7!hWg-7!crhie%i6040i2j1#ig6Pibh{h}2Y0$i0iGb 8_0*hWbKiNgth(gv5~h+hGa9h.gFi,hNfPeAaahQbkc88f8ugMiCi3iVh`g=a=93hza_8AiP7Fi{hpiNb54sb$gxh,fvinh?eA5ai:fEjkiuaYg07!iUcchdj8hohViz7X7tcb7ocdheaBa*j4ciaFii6rikeAbif?h3i;5rf`hKf}bii@i^h_ae11b_b{iFjue50J0w110N3=0vhhfojef/gy5Hi-h4bRjm69f;5IgHivj+j$0-j(hWj,110U0i1wjLcxdgcz2%f(fY2*cHd?ki5:cO0R0-0H0W0u7hdx0w1~9Oj;0%cK0H0rd61jkukw0$kydE1~0giK0C0S1~186VdCc%0i0c0g1}0=2TdFg@2Sc%0w0k0,c:0udq0$1n1=2rc kVdL6Fdb7i0(dT6.0,8=0;04.