Discussion :

[4Ur3L]

Bonjour à tous !

J'aurais besoin de votre aide sur un algorithme ... Ca fait 2 jours que je suis dessus, mais toujours aucune piste valable.

Voilà, j'ai un vecteur de nombre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

v <- c(118080, 130195, 199047, 84722, 97613, 214886)

Mon objectif est de combiner ces nombres dans 3 vecteurs, dont le total de chaque vecteur sera quasiment équivalent.
En plus clair, par exemple, à partir du vecteur v, je vais former

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
v1 <- c(118080, 84722, 97613)     # somme = 300415
v2 <- c(130195, 199047)           # somme = 329242
v3 <- c(214886)                   # somme = 214886

Ici, on voit que cette combinaison n'est pas idéale car les sommes varient fortement entre les vecteurs. Bon but est de minimiser cet écart entre les sommes de chaque vecteur.

Une combinaison meilleure serait (mais ce n'est peut-être pas la meilleure) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
v1 <- c(118080, 130195)     # somme = 248275
v2 <- c(199047, 97613)      # somme = 296660
v3 <- c(84722, 214886)      # somme = 299608

Car la variation entre les sommes est plus faible.

Voilà voilà ..
Est-ce que quelqu'un aurait une idée sur comment trouver la combinaison idéale permettant de diminuer au maximum la variation entre les sommes de chaque vecteur ?

PS : les 3 vecteurs finaux doivent contenir au moins 1 nombre.

Grand merci à tout ceux qui tenteront de répondre ... parce que moi j'suis perdu !
J'espère avoir correctement expliqué mon problème, mais si vous avez des questions, n'hésitez pas !

[pitipoisson]

Bonjour,

Dans l'énoncé de ton problème, rien n'indique qu'on puisse faire appel à une méthode d'optimisation qui dispense de tester toutes les combinaisons possibles (ou bien si ça existe, ce n'est pas dans mes cordes).

La méthode de brute consiste à

1. identifier toutes les combinaisons de 1, 2 et 3 ayant la même longueur que ton vecteur v.
2. choisir et calculer un critère de répartition de tes sommes.
3. identifier la combinaison qui minimise ce critère.

Voici un exemple avec au choix trois critères (intuitivement, j'aurais tendance à dire que les deux premiers doivent être équivalents... mais dans le cas présent, les trois donnent le même résultat) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
v <- c(118080, 130195, 199047, 84722, 97613, 214886)
 
##################################################
## Identification des différentes
## combinaisons possibles :
 
## Toutes les combinaisons d'indices (d'affectation à un des trois vecteurs) :
combinaisons <- combn(rep(1:3, each=length(v)), length(v))
 
dim(combinaisons)
 
## On ne conserve que les combinaisons contenant les trois indices :
combinaisons <- combinaisons[ , apply(combinaisons,
                                      2,
                                      function(x)
                                  {
                                      length(unique(x)) >= 3
                                  })]
 
combinaisons <- unique(combinaisons, MARGIN=2) # Et on supprime les doublons.
 
dim(combinaisons)
 
##################################################
## Différents critères à minimiser...
 
## (1) Carré des écarts à la moyenne (mu) :
mu <- sum(v)/3                          # Moyenne de la somme par vecteur.
 
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v, mu)
                 {
                     sum(tapply(v, IND, # Somme...
                                function(x, mu)
                            {
                                (sum(x) - mu)^2 # ...du carré des écarts à la moyenne
                            }, mu=mu))
                 }, v=v,  mu=mu)
 
 
## (2) Calcul de la somme((distances entre sommes) au carré) pour chaque combinaison :
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v)
                 {
                     sum(dist(tapply(v, IND, sum))^2)
                 }, v=v)
## => visiblement équivalent à (1) (à vérifier de façon formelle) mais plus compact !
 
## (3) écart entre min et max :
comb.critere <- apply(combinaisons,
                     2,
                     function(IND, v)
                 {
                     diff(range(tapply(v, IND, sum)))
                 }, v=v)
 
##################################################
## Identification de la combinaison optimale :
 
## Indice de la (première) combinaison qui minimise le critère :
comb.optim <- which.min(comb.critere)
 
## Combinaison correspondante :
combinaisons[ , comb.optim]
 
## Et les sommes correspondantes.
tapply(v, combinaisons[ , comb.optim], sum)

[pitipoisson]

L'identification des différentes combinaisons possibles paraît faux.
Je vais y jeter un œil un peu plus tard.

[pitipoisson]

Où avais-je la tête ?!

Voilà qui devrait être mieux pour la première partie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
##################################################
## Identification des différentes
## combinaisons possibles :
library(gtools)
 
## Toutes les combinaisons d'indices (d'affectation à un des trois vecteurs) ; l'ordre d'apparition compte => permutations :
combinaisons <- t(permutations(3, length(v), 1:3, repeats=TRUE))
 
dim(combinaisons)
 
## On ne conserve que les combinaisons contenant les trois indices :
combinaisons <- combinaisons[ , apply(combinaisons,
                                      2,
                                      function(x)
                                  {
                                      length(unique(x)) >= 3
                                  })]
 
dim(combinaisons)

[4Ur3L]

Waoow, merci bien !

Je regarde ça dès que j'ai un peu de temps.