Algorithme de répartition de groupes sur 2 colonnes

Groupes de tailles variables, pas ordonnés par taille

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
+---------------+---------------+
|          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 |               |
+---------------+---------------+

Les sous-catégories peuvent avoir un nombre variable d'éléments, les catégories parent n'en ont jamais.
L'idée est donc de répartir les sous-catégories en fonction de leur nombre d'éléments afin d'avoir deux colonnes avec le nombre de lignes minimisé.

Ce n'est pas simplement répartir des éléments en groupes égaux (parce que ça, je devrais pouvoir m'en sortir), mais des sous-groupes de taille variable en sous-groupes plus grands et avec une différence d'effectif total minimisée.
Si jamais, ce que j'aimerais savoir, c'est s'il y a un algorithme déjà existant pour ordonner les sous-catégories afin qu'elles soient par la suite réparties sur deux colonnes de manière plus ou moins homogène

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

Merci d'avance

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

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

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

Ç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 ?

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

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.

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

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  ^^

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

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)

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0

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 :D

Édité par MatTheCat

+0 -0

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

Édité par Amrom

+1 -0
Auteur du sujet

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.

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

Amrom

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…

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0

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.

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+2 -0
Auteur du sujet

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..

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Auteur du sujet

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

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Staff

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

Édité par viki53

Auteur du sujet

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

viki53

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.

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).

viki53

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

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é…

viki53

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  :)

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

viki53

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.

Édité par Ymox

Evitez qu'on vous dise de les lire : FAQ PHP et Symfony 2Tutoriel WAMP • Cliquez 👍 pour dire merci • Marquez vos sujets résolus

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte