Partition équilibrée⚓︎

Si les éléments d'une liste de longueur $n$ sont répartis entre deux listes liste_1 et liste_2 de longueurs respectives $n_1$ et $n_2$, ($n_1+n_2=n$), on dit que liste_1 et liste_2 réalisent une partition de la liste initiale.

On dispose d'une liste de $n$ nombres entiers strictement positifs, et on souhaite répartir ces $n$ nombres en deux listes telles que les sommes respectives des éléments des deux listes soient les plus proches possibles.

Cette partition d'une liste en deux listes s'appelle une partition équilibrée. L'ordre des éléments dans chaque liste n'a aucune importance.

Par exemple, avec la liste [10, 8, 5, 7, 9, 5], une partition équilibrée est obtenue avec les deux listes [10, 7, 5] et [8, 9, 5].

Remarque

On peut envisager un algorithme glouton mais ce type de méthode ne fournit pas la solution optimale dans tous les cas (voir l'exercice partition equilibrée 1 ).

La méthode utilisée ici est la programmation dynamique.

Programmation dynamique⚓︎

La fonction sum renvoie la somme des éléments d'une liste: sum(liste) est la somme des éléments de liste. La fonction abs renvoie la valeur absolue d'un nombre.

Si somme a pour valeur sum(liste) et si liste_1 est une liste constituée d'éléments de liste qui réalise le minimum des abs(sum(liste_i) - somme/2) où liste_i est une liste quelconque constituée d'éléments de liste, alors la liste liste_1 et la liste liste_2 dont les éléments sont ceux de liste qui ne sont pas dans liste_1, constituent une partition équilibrée de liste.

La solution n'est pas toujours unique. Par exemple avec liste = [3, 2, 2, 1, 1, 1], une partition équilibrée est obtenue avec les deux listes [3, 2] et [2, 1, 1, 1] ou avec les deux listes [3, 1, 1] et [2, 2, 1].

Principe de l'algorithme:

on parcourt la liste et pour chaque élément liste[i] on prend une décision entre les deux possibilités suivantes:

soit on choisit de prendre liste[i] et dans ce cas:

on le place dans liste_1; on continue avec la sous-liste restante liste[i+1:] et la somme somme/2-liste[i]

soit on choisit de ne pas prendre liste[i] et dans ce cas:

on continue avec la sous-liste restante liste[i+1:] et la somme somme/2

à chaque étape, on fait le choix qui minimise abs(sum(liste_1) - somme/2)

cas de base: liste de longueur 1 ou 0

Question 1

Compléter le code de la fonction partition qui prend en paramètre une liste de nombres nommée liste et qui renvoie la liste liste_1 obtenue par l'algorithme décrit plus haut.

Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0ly n7apSr1-me,(P2=4:+twki9][5h)6050j0C0L0v0O0q0b0s0i0q0v0b0b0H010L0O0w010406050b0k0B0B0v0y0r040x0d0q0k0:0d0t050o0`0|0~100^0w04191g051j0o1j1l1g0^0j0O0m0(0*0,0.0T0O0n0T0q1z0T0L0?050Z0h0q0C1u0+0-011y1A1C1A0L1I1K1G0L0h0d0j101H0y1h0L0T0(130b0w0v0t0.0G011M1w010l0#0C0t0v0B0C1G1.1:1^1O1{1K1~200?0a0s0F0y0d0w0d0b0O160t0s0X1,0y0y0C0i2l19230t1h0o1*2y0L1(1%1)0j250.1C0t1}2i1G1r1t0)1N2I0O2K0t1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0y0}0q0?0z2v2*0@2)242,1O2.2:0?0G2@1:2_2w2H012~0v2;040c322x0^352|0.383a0I3d342*363j0?0S3m3f3o3h370d2/390?0V3t2`2+1v2}3y2 040u3D3g3G3i3I3A040f3M3v3O3x3z3a0P3m1i2!192O2B0j2F360i1!211h3)1k3%2(1a2^053.0X2#3V2R010N0?0X0l3#3N400M0?0s463 2-0l0?1/0y0:2u3_333E360=040E4c2{3W0t0?1C0b0L0C4s3F404p0D3m4b472-0?0b4B4o0?0U0J3t0s4S4H4d1O42040O454l2x4U4t400t0h4w1}4M3w4p4r4#3~4(4J044x4z4.3W4p0U4G4n3w0d0?020q0L0g0H504I1O0B0O2=4|4D0?4Q4=064T5m4%4C1_4X2r0L0k0y184=5o3p4w0O4y4A5k5m514u0?4z4y0e2?5x5G405304595N5b0.4p0R5g4^4`5D2(5U015W5Y5c5e040p5*5V0?0Q0Q5a4V0.5Q0K5@4@2}4g0~4j0O175/5(0?4;5$5^375A5C645)4=5O1_5d5f6f5%4p0J0Q4F5T694v044L6k695Q0A646s5!6d0?5X6v5}0.6i5-6C040Q4 5E4T6g5~045J0L0e316q6G015Q5S2$5y3w6s4h61636F5p1O4:6z6b4{6-4N046E686Y6I5M6{6.5:046n6p6$6Q3i4K6K6N2$5l6P5%4X4Z5|70374+040v0h6u6 6^673`5%4*4K0{6K7r4m7t5I0C5K6~7s694~7h366x7I6(786@4/4O7L3W5Q55577R4)7k7m7o7F6Y6:7O4u7k1b7x6;6S7C6U6W7p7P047a2^6%7S0?6y6X7i6s7!7z7G4O5j7b5n7d695r0Y5u5w757A7.7D4R886Y4X0C0$5#7#7i6m8i8776410?5s8c7W4^6T6V3D0o3|0C2y2Z8G3(1s3*2B2D2z1Z1#2B7m1K2y3)0^0o0X0Z0#0b04.

On peut tester ce programme avec des listes de quelques nombres, mais en augmentant la taille de la liste on constate très rapidement un problème de coût. Comme d'habitude en programmation dynamique, le coût élevé a pour cause de nombreuses résolutions des mêmes sous-problèmes. Il s'agit donc de mémoriser les solutions des sous-problèmes plutôt que les recalculer plusieurs fois.

Dans une approche ascendante, on résout les sous-problèmes depuis les plus petits jusqu'aux plus grands et on utilise un tableau tab pour stocker les résultats.

Soit s la somme des éléments de la liste initiale,

tab[i][j] pour i allant de 1 à n et j allant de 1 à s , bornes incluses, a la valeur True si on peut trouver des éléments parmi les éléments d'indice 0 à i-1 de somme j et la valeur False sinon.

Pour calculer tab[i][j], on utilise les résultats obtenus pour les valeurs plus petites de iet j.

On peut construire le tableau avec une première ligne pour l'ensemble vide, en indiquant ensuite les indices des éléments de liste en colonne, les sommes de 0 à la somme totale s en ligne. Pour remplir le tableau, on utilise la formule: tab[i][j] = tab[i-1][j] or tab[i-1][j-vi] où vi est la valeur de liste[i-1].

On cherche ensuite dans la dernière ligne du tableau la valeur de m telle que tab[len(liste)][m] vaut True, m étant la somme la plus proche de s//2 inférieure ou égale à s//2

Question 2

Compléter le code de la fonction tableau qui prend en paramètre une liste de nombres nommée liste et qui renvoie le tableau tab et le nombre m obtenus comme décrit ci-dessus.

Évaluations restantes : 10/10

.128013s3o8bcdufvg/T0ly n7apS.r1F-me,(P2=4:+jtwki9][5h)6050h0D0N0u0Q0p0b0r0g0p0u0b0b0I010N0Q0v010406050b0i0C0C0u0y0q040w0d0p0i0=0d0s050m0|0~10120`0v041b1i051l0m1l1n1i0`0h0Q0k0*0,0.0:0V0Q0l0V0p1B0V0N0^050#0f0p0D1w0-0/011A1C1E1C0N1K1M1I0N0f0d0h121J0y1j0N0V0*150b0v0u0s0:0H011O1y010j0%0D0s0u0C0D1I1:1=1`1Q1}1M20220^0a0r0G0y0d0v0d0b0Q180s0r0Z1.0y0y0D0g2n1b250s1j0m1,2A0N1*1)1+0h270:1E0s1 2k1I1t1v0+1P2K0Q2M0s1$1u1I0v2t1j2y2A2(0{1;2o2S1{2X0y0 0p0^0r0z2x2,0_2+262.1Q2:2=2@0H2`1=2|2y2J01310u2?040r0c352z0`382 0:3b3d0r0J3h372,393n2@0U3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0t3I3k3L3m3N3F3e0e3R3A3T3C3E3o0R3Z2~3#3v040z0o3*3K2T3$3O0z2_1c2{3z3+3?3-0z343{363}3=2/3V3d0z3g433i3J3u480^0z3q4c3s3~473%4h3x4k1k2$1b2Q2D0h2H390g1$231j4v1m4t2*4r4A0Z2%3!3?0P0^0Z0j3r4e3B0O2@4S3S3 0j0^1X0D0u0i4X4M1{0@040F4*4m300^1E0b0N0D4:461Q4-0W0K3y0r520r4T3,0^0b3r544Y1{0d0^0I59553 0f570}4{394-4/4r5b4=044@4_5m3B4~51535h2/4#0u0f5g5r0:5d045f4k5a4+4}0^0T0T5w3#0P0g0^0A3c0b4`5M5B1Q4O040j3D5G5O3m0^0Q5-4;5I4V042V5=4|3m5j040y1=0l5#2*5H015o5T3 57685c0^0L6b1Q0C0Q4h6f0:4~0S0S5z525%5/041K6k665Q6v6h0^3:5q5.6w040S5S6C5?016z046B646D4-6o5$655J5L2(5N6J5V0^0n0y0i632{6X5|010g0z0^030r0d0f4_0s0Q0y0r0o0r0u0k2u0r0p001 5!0C1L1N0k0Q0Z6p6*395)5+0y5{3u5:7i3B0d5^5`6S6D0s5~600s626v676I6+7s4?1 7x0^5p6O6J0s4?0Q4^6(366r6E0W4 7c537d3B7J5t1B2M7l3#6U7#5i7K4^7E4.6v7X6u7z5n6x7;7W7k7@3#6Q0W7T5A657X1U7!7`3?4-6H7H7A7*5v844,7?887j5_7,6n7(6c5K8k5(5W046#6%7~6q657f5,7q7I0^0M8n5@5:1a8y7A7t617N2z7P7y8f7^04588c1Q5J6e8S0:6L3`8O7{0^7S4k067U8*7 6D5)0Q4R8G8g7:8!858e2{7P7X5;8W6E6G7.8A8i8C016U6V6)7P6Z8q6$8K4L6J4-508(8+9j8,8z7Y0l838@8d04878`80928~8U917Y7M7,9t7O9v8h8~6Q6R6W7P7%8;3B9a8r9d8)9j8{5D5F9x0^0x9z0u0v0v1 0h7,7G9u7r7K9o9d8M8$7c9U040C949M9K9F8R9|6D5J0m0m946L422(9S8u8-0^0O1A1M9`5^2X0N947/5E9C7.5~2a9*9z5u9:656m9D8L9F9_9H0^0S9ha79k9@az9 6J9{98ay9`0^0Ba46i3.9?8v0^2t0N0i0y8FaI896talaA040Eaj0^aH3|1b4J0D2A2#a=4u1u4w2D2F2B1#1%2D5E1M2A4v0`0m0Z0#0%0b04.

Après avoir obtenu le tableau, on peut construire une partition équilibrée de la liste.

Question 3

Compléter le code de la fonction partition2 qui prend en paramètres:

une liste de nombres nommée liste;
un indice i initialisé à len(liste) lors de l'appel de la fonction;
le tableau t obtenu avec la fonction tableau de la question 2;
un entier v initialisé, lors de l'appel de la fonction, avec la valeur de m obtenue avec la fonction tableau de la question 2;
une liste nommée liste_1, initialisée par défaut à None, dans laquelle on ajoute successivement les éléments choisis et qui est renvoyée à la fin.

Évaluations restantes : 10/10

.128013s3o_8bcdufvg/0ly n7apS.r1-me,(P2=4:Ntwki9][5h)6050i0C0L0u0O0p0b0r0h0p0u0b0b0H010L0O0v010406050b0j0B0B0u0y0q040w0d0p0j0:0d0s050n0`0|0~100^0v04191g051j0n1j1l1g0^0i0O0l0(0*0,0.0T0O0m0T0p1z0T0L0?050Z0g0p0C1u0+0-011y1A1C1A0L1I1K1G0L0g0d0i101H0y1h0L0T0(130b0v0u0s0.0G011M1w010k0#0C0s0u0B0C1G1.1:1^1O1{1K1~200?0a0r0F0y0d0v0d0b0O160s0r0X1,0y0y0C0h2l19230s1h0n1*2y0L1(1%1)0i250.1C0s1}2i1G1r1t0)1N2I0O2K0s1!1s1G0v2r1h2w2y2$0_1/2m2Q1_2V0y0}0p0?0r0z2v2*0@2)242,1O2.2:2=0G2^1:2`2w2H012 0u2;040r0c332x0^362}0.393b0r0I3f352*373l2=0S3p3h3r3j380d2/3a2=0V3w2{2+1v2~3B303c0t3G3i3J3k3L3D3c0f3P3y3R3A3C3m0P3X2|3Z3t040z0o3p1i2!192O2B0i2F370h1!211h3?1k3;2(1a2_053{0X2#3Y2R010N0?0X0k3/3Q4a0M2=4g492-0k0?1/0y0:2l3243343H370=040E4l3)4a0s0?1C0b0L0C4C3I4a4z0D3p0r4x3z4F040O4L4y0?4P4v2x4R4h2-0?0L4X3z4O4Q4S3*0?0l4,3Z4.4#3c4:4E4G0O4I0C0e2@4`4|1_0d0?0H4@4a0N0h0?0K174K544(1O4z0U0J3w0r5p4%4m1O4c4V4f4`5r4D4)044H4J524/5j0.0d4j4V0b5F5s0.5c5e5g5a1_4z5n4`065q5Y5y4M5A5C51532$5!375704595x555k0?0R0Q4Q5q5X5q5;5O0?0O5w5*5}385 5M5z1O5-0H5/625G010B0O0?3.5i5N015U5o5Z5p635u2r0L0j0y185:6d4U5%5E5W5Y6q5 612_5+4T4*5S5=040R6L3k656j675H0?0A6P6e6g3,6X4z0Q6O6S5#2~4=6#0?0Q5V2$5{6o6E046s6u6w6c6k4U4q4s0O174u2(6d4z4B6)3s4~506-044!6|6T644V6X5-6W783z6f0?5)44754Z666*6Q044+7m4^7t6x6}6,7z4N7B7f7v7h6A7q4w7s040U6n6p6d5u0C1C6G346I4;7x7c6(747D7i7F566V6X7o6!7+6M6%6X4U4?7;6U047l7(7g6z4 4J7$7@6R7~7J7k7.6Z7M2x636$6/7R5Z6380506B865,0?0x84040u0v0v1}0i7c778m6J5B815h8z7A6N8q4W7`01888J7/8b487g6$7Q6C6o7Z5b0?6_6v7u79046 2k710s737r6k768q5%7c7e6H8i858,7g8L8E4a8N8;8!8A7y8|5T7H8?6y7E93687-8J8j828J4z7%8_7J4U8I997{7}9i378~9f6.8=7Y8@8B8k8O8d0?8S6;19460C2y2Z9G3=1s3@2B2D2z1Z1#2B0u1J9J0n3?0^9W0Y0!0$04.