Partition équilibrée (1)
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.
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].
Malgré sa facilité d'énonciation, ce problème est complexe. On utilise dans cet exercice un algorithme glouton pour le résoudre :
-
on trie la liste initiale
listepar ordre décroissant ; -
on crée deux listes vides
liste_1etliste_2; -
on ajoute successivement chaque nombre de la liste triée
listeà la listeliste_1ouliste_2en choisissant à chaque fois celle dont la somme des éléments est la plus petite. En cas d'égalité des sommes, on ajoute le nombre à la listeliste_1.
Cette approche gloutonne est facile à mettre en œuvre mais elle n'est pas toujours optimale. Elle peut en effet générer des listes dont les sommes sont proches mais pas les plus proches possibles. Pour obtenir une solution optimale dans tous les cas, on peut utiliser une méthode par programmation dynamique, (voir exercice partition equilibrée 2 )
1er exemple : solution optimale
On considère la liste [10, 8, 5, 7, 9, 5]. La liste triée est [10, 9, 8, 7, 5, 5].
Les insertions successives sont décrites ci-dessous :
| Valeur insérée | liste_1 |
liste_2 |
Remarque |
|---|---|---|---|
| État initial | [] |
[] |
|
10 |
[10] |
[] |
Insertion dans liste_1 |
9 |
[10] |
[9] |
Insertion dans liste_2 |
8 |
[10] |
[9, 8] |
Insertion dans liste_2 |
7 |
[10, 7] |
[9, 8] |
Insertion dans liste_1 |
5 |
[10, 7, 5] |
[9, 8] |
Insertion dans liste_1 |
5 |
[10, 7, 5] |
[9, 8, 5] |
Insertion dans liste_2 |
Les deux listes [10, 7, 5] et [9, 8, 5] ont la même somme totale de 22. La solution est donc optimale.
2nd exemple : solution non optimale
On considère désormais la liste [3, 3, 3, 4, 5]. La liste triée est [5, 4, 3, 3, 3].
Les insertions successives sont décrites ci-dessous :
| Valeur insérée | liste_1 |
liste_2 |
Remarque |
|---|---|---|---|
| État initial | [] |
[] |
|
5 |
[5] |
[] |
Insertion dans liste_1 |
4 |
[5] |
[4] |
Insertion dans liste_2 |
3 |
[5] |
[4, 3] |
Insertion dans liste_2 |
3 |
[5, 3] |
[4, 3] |
Insertion dans liste_1 |
3 |
[5, 3] |
[4, 3, 3] |
Insertion dans liste_2 |
Les deux listes [5, 3] et [4, 3, 3] ont des sommes différentes : 8 pour liste_1 et 10 pour liste_2.
Cette solution n'est pas optimale. La réponse optimale serait [5, 4] et [3, 3, 3] qui donnent des sommes égales à 9.
Compléter le code de la fonction partition qui prend en paramètre une liste de nombres nommée liste et qui renvoie le tuple composé des deux listes liste_1 et liste_2 obtenues par l'algorithme glouton décrit plus haut.
La liste passée en paramètre est triée à l'aide de la méthode sort. La valeur du paramètre reverse est fixée à True afin d'effectuer un tri suivant l'ordre décroissant.
Exemples
>>> liste = [10, 8, 5, 7, 9, 5]
>>> partition(liste)
([10, 7, 5], [9, 8, 5])
>>> liste = [5, 4, 3, 3, 3]
>>> partition(liste)
([5, 3], [4, 3, 3])
>>> liste = [5, 4]
>>> partition(liste)
([5], [4])
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)