Trouver la meilleure répartition (A la recherche de l'algorithme)
Résolu
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
-
24 mars 2006 à 10:29
cs_AlexN Messages postés 694 Date d'inscription lundi 5 décembre 2005 Statut Membre Dernière intervention 8 janvier 2014 - 24 mars 2006 à 16:01
cs_AlexN Messages postés 694 Date d'inscription lundi 5 décembre 2005 Statut Membre Dernière intervention 8 janvier 2014 - 24 mars 2006 à 16:01
A voir également:
- Algorithme de répartition
- Algorithme de prim - Forum C / C++ / C++.NET
- Code maroc algorithme - Forum C
- Algorithme loto excel gratuit ✓ - Forum Visual Basic
- Algorithme de horner - Forum C / C++ / C++.NET
- Algorithme minmax - Forum VB.NET
17 réponses
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 14:45
24 mars 2006 à 14:45
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 ?
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 ?
scaryman
Messages postés
492
Date d'inscription
vendredi 30 janvier 2004
Statut
Membre
Dernière intervention
16 mai 2007
12
24 mars 2006 à 11:26
24 mars 2006 à 11:26
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++
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++
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 11:44
24 mars 2006 à 11:44
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.
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.
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 11:57
24 mars 2006 à 11:57
Il faut trier ta list en ordre inverse de taille.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 12:04
24 mars 2006 à 12:04
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 ?
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 ?
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 12:06
24 mars 2006 à 12:06
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;
}
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;
}
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 12:24
24 mars 2006 à 12:24
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);
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);
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 13:42
24 mars 2006 à 13:42
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.
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.
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 13:43
24 mars 2006 à 13:43
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;
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;
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 13:48
24 mars 2006 à 13:48
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 >
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 13:50
24 mars 2006 à 13:50
sigles supérieur et inférieur (< et >)
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 13:56
24 mars 2006 à 13:56
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 ?
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 ?
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 13:57
24 mars 2006 à 13:57
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 ?
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 ?
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 14:27
24 mars 2006 à 14:27
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é...
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é...
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 15:07
24 mars 2006 à 15:07
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 ?
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 ?
cs_valckar
Messages postés
34
Date d'inscription
jeudi 16 mars 2006
Statut
Membre
Dernière intervention
30 juin 2006
24 mars 2006 à 15:18
24 mars 2006 à 15:18
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+
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+
cs_AlexN
Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
19
24 mars 2006 à 16:01
24 mars 2006 à 16:01
ok
encore merci pour toutes ces précisions
salut
encore merci pour toutes ces précisions
salut
