Trouver la meilleure répartition (A la recherche de l'algorithme) [Résolu]

cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 10:29 - Dernière réponse : cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention
- 24 mars 2006 à 16:01
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.
Afficher la suite 

Votre réponse

17 réponses

Meilleure réponse
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 14:45
3
Merci
Bon,

Soit,

L(ln) : liste de liste (trier dans le sens inverse de la taille des listes)

ln : liste n comportant taille élément.

Et,

R1, R2, liste résultats.



On définit t1 et t2 correspondant à la taille des listes (somme des tailles des ln la comportant).



t1=0 ;

t2=0 ;

i=0

tant que (i< taille de L)

//on choisi dans quelle R ajouter li

if(t1<=t2)

Ajouter li dans R1

t1=t1+taille de li

sinon

Ajouter li dans R2

t2=té+taille de li

Fin si

i=i+1

fin tant que



OK ?

Merci cs_valckar 3

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 96 internautes ce mois-ci

Commenter la réponse de cs_valckar
scaryman 492 Messages postés vendredi 30 janvier 2004Date d'inscription 16 mai 2007 Dernière intervention - 24 mars 2006 à 11:26
0
Merci
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++
Commenter la réponse de scaryman
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 11:44
0
Merci
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.
Commenter la réponse de cs_AlexN
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 11:57
0
Merci
Il faut trier ta list en ordre inverse de taille.
Commenter la réponse de cs_valckar
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 12:04
0
Merci
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 ?
Commenter la réponse de cs_AlexN
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 12:06
0
Merci
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 valueList = new ArrayList(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;

}
Commenter la réponse de cs_valckar
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 12:24
0
Merci
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);
Commenter la réponse de cs_valckar
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 13:42
0
Merci
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.
Commenter la réponse de cs_AlexN
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 13:43
0
Merci
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;
Commenter la réponse de cs_valckar
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 13:48
0
Merci
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 >
Commenter la réponse de cs_AlexN
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 13:50
0
Merci
sigles supérieur et inférieur (< et >)
Commenter la réponse de cs_AlexN
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 13:56
0
Merci
Je t'écris ça differemment.

Pour les <> c'est que l'ont utilise des liste de map de lists, etc...



Tu prends ta liste trié à l’envers L, 2 listes L1 et L2 comme résultats.



Pour tous l’élément E de L (dans l’ordre de tri), j'ajoute E à la liste L1 si somme(L1) >= somme(L2).



Somme() représentant la somme de taille des listes de chaque uple.



OK ?
Commenter la réponse de cs_valckar
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 13:57
0
Merci
Je t'écris ça differemment.

Pour les <> c'est que l'ont utilise des liste de map de lists, etc...



Tu prends ta liste trié à l’envers L, 2 listes L1 et L2 comme résultats.



Pour tous l’élément E de L (dans l’ordre de tri), j'ajoute E à la liste L1 si somme(L1) >= somme(L2).



Somme() représentant la somme de taille des listes de chaque uple.



OK ?
Commenter la réponse de cs_valckar
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 14:27
0
Merci
exemple si j'ai compris :

Start : L 5 4 3 2 1, Somme(L1) 0, Somme(L2) = 0
Step 1 : Somme(L1+5) (5) >Somme(L2) (0)> L1 = (5) et L2 vide
Step 2 : Somme(L1+4) (5+4) >Somme(L2) (0)> L1 = (5,4) et L2 vide
Step 3 : Somme(L1+3) (5+4+3) >Somme(L2) (0)> L1 = (5,4,3) et L2 vide
Etc...

Je crois que je n'ai pas compris...
désolé...
Commenter la réponse de cs_AlexN
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 15:07
0
Merci
L = 10 8 6 4 3 1

1) 0 <0 ?> R1(10), t1 = 10, R2, t2 = 0
2) 10 <0 ?> R1(10), t1 = 10, R2(8), t2 = 8
3) 10 <8 ?> R1(10), t1 = 10, R2(8,6), t2 = 14
4) 10 <14 ?> R1(10, 4), t1 = 14, R2(8, 6), t2 = 14
5) 14 <14 ?> R1 (10, 4, 3), t1 = 17, R2 (8, 6), t2 = 14
6) 17 <14 ?> R1 (10, 4, 3), t1 = 17, R2 (8, 6, 1), t2 = 15


Yipeeee !!!!!

Merci beaucoup Valckar


On m'a proposé une autre solution :

"si tu scannes tes catégories et que tu les tries par ordre de nombre d'éléments du plus petit au plus grand et que tu prends tes catégories par multiple de 2, la 1ere et la nieme la 2eme et la nieme-1 la 3eme et la nieme-2 tu vas ordonner tes colonnes pour avoir toujours un nombre d'élement proche de la moyenne du nombre d'objets.
Bien sur plus le nombre de catégories est grand et plus ton nombre d'objet et proche de la moyenne plus tes colonnes seront équilibrées."

Laquelle est la meilleure a votre avis ?
Commenter la réponse de cs_AlexN
cs_valckar 34 Messages postés jeudi 16 mars 2006Date d'inscription 30 juin 2006 Dernière intervention - 24 mars 2006 à 15:18
0
Merci
La problématique de l'autre solution est que si tu à un élément trés
grand tous seule ça ne marche pas : tu sous entend que ta liste est
bien réparti !



contre exemple : l=16 5 4 3 2 1 la solution est R1(16) R2(5 4 3 2 1)
avec l'autre algo je crois que le résultat serais plus éloigné.



A+
Commenter la réponse de cs_valckar
cs_AlexN 719 Messages postés lundi 5 décembre 2005Date d'inscription 8 janvier 2014 Dernière intervention - 24 mars 2006 à 16:01
0
Merci
ok
encore merci pour toutes ces précisions

salut
Commenter la réponse de cs_AlexN

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.