Algorithme de répartition de groupes sur 2 colonnes

Bonjour à tous

Je suis toujours dans mon trip, et j’en viens à vouloir répartir du contenu sur deux colonnes.

J’ai des éléments qui sont répartis dans des sous-catégories. L’idée serait d’avoir des blocs par catégorie, avec les sous-catégories sur deux colonnes. Juste afin d’illustrer :

+---------------+---------------+
|          Catégorie 1          |
+---------------+---------------+
| Catégorie 1.1 | Catégorie 1.3 |
+===============+===============+
| Elément 1.1.1 | Element 1.3.1 |
+---------------+---------------+
| Elément 1.1.2 | Element 1.3.2 |
+===============+---------------+
| Catégorie 1.2 | Element 1.3.3 |
+===============+---------------+
| Elément 1.2.1 | Element 1.3.4 |
+---------------+---------------+
| Elément 1.2.2 |               |
+---------------+---------------+

+---------------+---------------+
|          Catégorie 2          |
+---------------+---------------+
| Catégorie 2.1 | Catégorie 2.3 |
+===============+===============+
| Elément 2.1.1 | Element 2.3.1 |
+===============+---------------+
| Catégorie 2.2 | Element 2.3.2 |
+===============+---------------+
| Elément 2.2.1 | Element 2.3.3 |
+---------------+---------------+
| Elément 2.2.2 |               |
+---------------+---------------+
| Elément 2.2.3 |               |
+---------------+---------------+

Est-ce que quelqu’un connaît un algorithme qui permet de faire ce genre de répartition ?

Merci d’avance

Je ne connais pas d'algorithme, mais c'est une problématique qui m'intéresse aussi ! Je pensais faire ce genre de truc avec LuaTeX lorsque j'en trouverai le temps.

Je vois comment faire en CSS mais la question est taguée PHP, du coup comment est censé être généré le rendu ?

Ben j'ai une liste d'éléments triés par sous-catégories, et j'aimerais les rendre sous forme de blocs par sous-catégorie. Mais ça implique à mon avis de savoir le nombre d'éléments par groupe avant de commencer à les afficher, à moins que ta solution par CSS puisse fonctionner ?

C'est évidemment en lien avec mon sujet sur les veuves et orphelines, et ça concerne la partie des compétences, pour être précis.

Tout ça, c'est pour du Symfony, en fait, j'ajoute le tag

Le module column est fait pour ça.

Comme d'habitude, attention au support http://caniuse.com/#feat=multicolumn

Ça ne va pas changer l'ordre de mes données dans le flux, est c'est en fait là mon problème : comment faire en sorte de ne pas avoir deux sous-catégories à deux éléments à gauche parce qu'en premier dans le flux, et une sous-catégorie avec sept éléments à droite ?

Tu voudrais quoi dans ce cas alors ?

En fait, un algorithme qui fait que, en fonction

• d'un nombre d'ensembles variable
• ensembles non scindables et de tailles aussi variable
• ensembles dont on doit voir tous les éléments

les répartisse en deux parties que ces dernières soient représentées côte à côte sans qu'un côté prenne plus de place en hauteur que l'autre du fait d'un nombre total d'éléments pas identique.

Imaginons que j'aie cinq groupes, l'un avec 8 éléments, un avec 6, deux avec 3 et un avec 4. J'aimerais savoir si quelqu'un connaît un algorithme qui permet de faire en sorte que je n'aie pas 14 (8 + 6 parce que les premiers) éléments d'un côté et 10 de l'autre quand il est possible d'avoir 12 (8 + 4) et 12 (6 + 3 + 3).

L'ordre des groupes n'est pas nécessairement important, j'aimerais juste les répartir uniformément en fonction du nombre d'éléments qu'ils contiennent.

Du coup si je reprends ton exemple il faudrait 6 éléments à gauche et 5 à droite ? Ça contredirait le deuxième exemple de ton premier post non ?

En fait oui, mais j'ai oublié qu'il y avait le nom du groupe qui entrait aussi en ligne de compte  (on imagine que ça ajoute un élément par groupe, mais c'est encore constant, donc le souci n'est pas beaucoup plus complexe)

Au final, il y a minimum 2 éléments par groupe, dira-t-on.

Edit

'tain, c'est dire si j'arrive à réfléchir à la chose, encore heureux que je me voie obligé de l'expliquer par écrit 

On va faire plus simple ; est-ce que ça convient : http://jsfiddle.net/bLL0dtn1/ ?

EDIT: ah je n'avais pas vu que tu avais édité ton exemple -_-

Du coup c'est encore plus simple non ? http://jsfiddle.net/gr42kaq1/

C'est dans l'idée, oui.

Mais le problème n'est pas à l'affichage en lui-même, c'est au niveau du tri ou de l'ordre des groupes. Parce que là, si je déplace le groupe 1.1 après le 1.3, juste pour changer l'ordre par rapport à leur taille, j'obtiens la première colonne où j'ai les deux premiers groupes et donc 9 éléments, puis la seconde avec seulement 2.

Et tant qu'il n'y a que trois groupes, ça risque encore d'aller, mais si j'en ai plus dans une catégorie, c'est là que ça devient ennuyeux.

Edit

Et dans ton second fiddle, il y a un élément d'un groupe de la première colonne qui se perd dans la seconde, j'aimerais pouvoir éviter (oui, je suis chiant)

Après quelques tests il semble que l'implémentation de break-before, break-after et widows ne soit pas à la hauteur de ta volonté ; j'ai bien peur qu'il n'y ait aucune solution CSS. Par contre tu peux jeter un coup d’œil au pseudo-code si ça t'amuse

je verrais ça comme ça :
1. connaître la taille de chaque colonne = somme des éléments divisée par 2
2. vérifier si un groupe a un nombre d’éléments supérieur ou égal à la longueur
- si oui la 1^ère colonne contient ce groupe, les autres vont dans l'autre (c'est le cas le plus simple)
- si non prendre le groupe qui a le plus d'éléments et chercher le groupe qui permet d'atteindre la taille de la colonne
- si aucun groupe ne convient, continuer en additionnant la taille des groupes avec 2 puis 3 puis x groupes, jusqu'à ce que la 1^ère colonne soit remplie

PS : c'est un problème de maths, ton truc, avec des ensembles et des sous-ensembles

C'est ce que j'avais à l'idée, mais j'avais l'impression que ce serait relativement lourd. Enfin, pour l'instant, il n'y a pas d'autre proposition que celle-ci.

Oui, mais comme je pensais que c'était un problème courant par rapport à ma situation, et n'ayant rien trouvé de concluant avant de venir ici, je l'ai placé dans PHP.

Peut-être qu'en cherchant du "purement mathématique", je trouverais quelque chose, en effet…

Coucou,

Je verrais bien un algorithme glouton pour résoudre ton problème.

1. ON admettra que tu connais la taille de chaque groupe, sinon ce n'est même pas la peine
2. Trie tes groupes en ordre décroissant de taille
3. Tant qu'il y a encore des groupes à placer, prend le premier de la liste (le plus gros non encore placé) et mets-le dans la colonne la moins remplie.

Si on reprend ton exemple avec 8 6 4 3 3, ça donnerait donc :

1. 8, 0
2. 8, 6
3. 8, 6+4
4. 8+3, 6+4
5. 8+3, 6+4+3

Ce qui donne une colonne à 11 et l'autre à 13; ce n'est pas la solution optimale mais je pense que ce n'est quand même pas si mal que ça.

Une implémentation telle que tu la proposes, avec une vérification de la différence entre les deux groupes résultants, permettrait éventuellement de corriger ce souci d'optimisation.

Le souci, c'est qu'on a des algorithmes pour minimiser, des algorithmes pour maximiser, mais apparemment pas d'algorithme pour répartir  (c'est d'ailleurs là le truc, il y en a peut-être, mais ce n'est pas le bon terme), qui plus est vérifier le caractère optimal de la répartition…

En fait, on pourrait considérer qu'il s'agit d'un graphe dont on doit prendre en compte à la fois les poids des sommets (représentant les tailles des petits groupes) et ceux des arrêtes créés (représentant la différence entre les deux sommets de l'arrête), afin de pouvoir tenter de corriger une répartition qui ne serait pas optimale

Plus simplement dans mon cas, je me rends compte dois faire en sorte de m'approcher le plus possible de la moitié du nombre total d'éléments.
Si j'avais trois colonnes, ce serait le tiers, quatre, le quart, etc..

Petit question : tu récupères tes données sous quelle forme (elles ressemblent à quoi côté PHP) ?

Parce qu'avec une boucle ou deux tu peux largement répartir assez grossièrement tout ça je pense…

En fait, vu que c'est Doctrine qui est derrière cela, j'ai une collection plate des éléments (sous forme d'entités) à afficher, collection ordonnée selon la sous-catégorie desdits éléments

Ok, donc tu peux facilement boucler pour les grouper par catégorie déjà.

Ensuite tu boucles sur les catégories que tu viens de mettre en place dont tu peux compter les éléments et donc déterminer combien tu dois afficher par colonne (la moitié du total).

Sinon, au pire, tu peux voir ce que des plugins comme Masonry peuvent faire, mais je suis pas sûr que l'ordre soit conservé…

N.B. : pense aussi à la sémantique, si tu coupes des listes en plein milieu pour changer de colonne ça risque de faire bizarre

Oui, ça c'est OK 
Mais ma solution actuelle est crade, et elle ne me permet pas la répartition optimale que je souhaiterais avoir.

Je peux aussi avoir le compte par catégorie avant de les afficher, ça ajoute juste une dimension au tableau, cf. ici

C'est un plug-in JavaScript, non ?
Non pas que ça me gêne, mais je n'y avais pas pensé, je vais jeter un œil 

Oui, c'est justement le problème, en fait. Il ne me faut pas répartir uniquement les éléments (sans quoi j'utiliserais probablement du CSS comme l'a proposé MatTheCat), mais les groupes qui les contiennent.

Edit

D'après ce que j'ai pu voir, Masonry ne trie pas les éléments pour les répartir, il conserve l'ordre du flux.