Bonjour, V’la le problème : j’ai un ensemble de paires du genre (catégorie1, 3 objets), (catégorie 2, 6 objets), (catégorie 3, 18 objets),… (catégorie n, m objets). N n’est pas connu d’avance, pas plus que le nombre M d’objets que contient chaque catégorie. Je cherche un algorithme qui me permettrait de calculer la répartition de ces paires en deux sous ensembles le plus « équilibré ». C’est-à-dire donnant des sommes de poids (nombre d’objets) de chaque sous ensemble dont le rapport est le plus proche de 1. Par exemple : Cat1, 2 Cat2 3 Cat3, 5 Cat4 1 Pourrait me donner comme solution (Cat1, Cat2) et (Cat3, Cat4) parce que 2+3 / 5 +1 est proche de 1 ou encore (Cat1, Cat2, Cat4) et (Cat3) parce que 2+3+1 / 5 est proche de 1 mais pas (Cat1, Cat2, Cat3) et (Cat4) parce que (2+3+5) / 1 est moins proche de 1 que les autres solutions Mais à quoi ça sert ? Ayant extrait des données par catégorie d’une base de données, je souhaiterais les présenter sur deux colonnes, classées par catégorie mais également avec une présentation correcte, c’est-à-dire sur deux colonnes « équilibrées » PS : Je ne suis pas une tête en mathématique, alors si vous avez une solution ayez pitié de me la présenter dans un langage pas trop complexe. Ou alors dites-moi direct « Oublies si t’as pas bac +15 et deux ou trois thèses en préparation». Merci pour votre aide.

Salut
Il ne faut pas etre particulierement fort en math (bien que l'algorithmique ce n'est pas grand chose d'autre) pour faire de la prog.
Je n'ai pas vraiment de réponse à ton problème mais un début de piste, c'est d'additionner tous les objets ensemble et de diviser ce nombre par le nombre de catégories. Ensuite, tant que tu ne dépasses pas ce nombre (ou alors de peu), tu pourrais ajouter les catégories dans la 1ère colonne.
Ensuite, tu mettrais ce qui reste dans la 2e colonne.

Je sais bien que ce n'est pas (du tout) optimal mais ce n'est qu'un début de piste.

Voila
A++

Salut tu le dis bien toi même : "bien que l'algorithmique ce n'est pas grand chose d'autre" La solution que tu me proposes est celle que j'utilise pour l'instant. Mais si la catégorie qui est à la frontière des deux colonnes contient beaucoup d'objets, les colonnes deviennent completement désequilibrées. Cette méthode présuppose que lorsque je "coupe en deux", la catégorie frontière est "gentille" et contient un nombre d'objets appropriés pour faire une bonne répartition. Malheureusement c'est loin d'être toujours le cas. Merci tout de même.

Il faut trier ta list en ordre inverse de taille.

Bonjour Valckar Ok je trie la liste que j'ai donné en exemple en ordre inverse de taille : (Cat 3, 5), (Cat2, 3) (Cat1, 2) (Cat4, 1) Et après ? Qu'est-ce que je fais ?

Je n'ais pas testé mais le code devrait ressembler à ça :

public List<Map<Object, List<Object>>> reparti(Map<Object, List<Object>> map)
    {
        SortedSet<Entry<Object, List<Object>>> sortedSet = new TreeSet<Entry<Object, List<Object>>>(new Comparator<Entry<Object, List<Object>>>()
        {

            public int compare(Entry<Object, List<Object>> o1, Entry<Object, List<Object>> o2)
            {
                return o2.getValue().size() - o1.getValue().size();
            }
        });
        sortedSet.addAll(map.entrySet());
        List<Map<Object, List<Object>>> result = new ArrayList<Map<Object, List<Object>>>(2);
        result.add(new HashMap<Object, List<Object>>());
        result.add(new HashMap<Object, List<Object>>());
        List<Integer> valueList = new ArrayList<Integer>(2);
        valueList.add(0);
        valueList.add(0);
        int index = 0;
        for (Entry<Object, List<Object>> entry : sortedSet)
        {
            index = valueList.get(0) <= valueList.get(1) ? 0 : 1;
            result.get(index).put(entry.getKey(), entry.getValue());
            valueList.set(index, valueList.get(index) + 1);
        }
        return result;
    }

Si tu veus tester :

Map<Object, List<Object>> uple = new HashMap<Object, List<Object>>();
        Random r = new Random();
        for (int i = 0; i < 100; i++)
        {
            int taille = r.nextInt(10);
            List<Object> list = new ArrayList<Object>(taille);
            for (int n = 0; n < taille; n++)
            {
                list.add(n);
            }
            uple.put("c"+i, new ArrayList<Object>(list));
        }
        List<Map<Object, List<Object>>> list = new retpartition().reparti(uple);
        int result = 0;
        for (List l : list.get(0).values())
        {
            result += l.size();
        }
        System.out.println("list 1" + result);
        result = 0;
        for (List l : list.get(1).values())
        {
            result += l.size();
        }
        System.out.println("list 2" + result);

Valckar ou quelqu'un ayant compris sa solution : Je ne connais pas très bien java. J'ai posté ici parce qu'il n'existe pas de catégorie "recherche d'algorithme". Pourrais-tu me traduire ta solution sans "langage dependance". Si (expression) alors (instruction)... Merci Sinon tant pis.

Une petite erreur
a la place de
                        valueList.set(index, valueList.get(index) + entry.getValue().1);
il faut lire
                        valueList.set(index, valueList.get(index) + entry.getValue().size());

et a la place de
                        return o2.getValue().size() - o1.getValue().size();
il faut lire
                        int result = o2.getValue().size() - o1.getValue().size();
                        if(result==0)result = 1;
                        return result;

PS : je trouvais que dans le LISP y'avait trop de parenthèses. Je vais finir par penser que dans le java y'a trop de < et de >