Discussion :

[petit_chat]

Bonjour,
D'avance merci de l'attention que vous porterez à ce problème. Je suis nul en algo mais pour un développeur ce problème est trivial. Je cherche à programmer en python un script qui produit une playlist. Cette playlist contient des titres de genres musicaux différents (rock, hiphop, musique française, reggae, etc..). Ces genres musicaux ne sont pas tous présents en même proportion: sur la playlist (il y a 34% de musique française, 33% de rock, 12% de hiphop, 7% de reggae, etc...). Je voudrais que mon programme génère une playlist telle que la répartition des genre soit homogène. C'est à dire, par exemple, si j'ai 33% de rock, alors je veux qu'il y ai un titre rock tous les 3 titres. Si j'ai 7% de reggae alors j'aurai un reggae tous les 14 titres à peu près.

Pour simplifier on peut résoudre mon problème à celui-ci plus simple:
On a 100 jetons de 5 couleurs différentes. On a un tableau de 100 cases. Comment répartir dans le tableau les jetons de couleurs différentes de la façon la plus homogène possible ?

Exemple:
50 jetons verts
30 jetons rouges
10 jetons bleus
7 jetons jaune
3 jetons noirs

On peux calculer facilement la fréquence d'un jeton de chaque couleur.
fr(vert) = 100/50 = 2 => un jeton tous les 2 jetons
fr(rouge) = int(100/30) + 100mod30 = 3 reste 10 => un jeton tous les 3 jetons , je ne sais pas traiter le reste
fr(bleus)= 100/10 = 10 => un jeton tous les 10 jetons
fr(jaune)= int(100/7) + 100mod7 = 14 reste 2 => un jeton tous les 14 jetons, comment traiter le reste ?
fr(noir)= int(100/3) + 100mod3 = 33 reste 1 => un jeton tous les 33, que faire du reste ?

Comment construire un tableau qui respecte ces fréquences le mieux possible ? Que faire des restes ? Comment traiter le cas où plusieurs couleurs différentes doivent tomber sur la même case du tableau ? C'est trop complexe pour ma petite tête, je m'y perds. Merci de m'aider.

[mathieu]

ma 1re idée à chaud serait d'utiliser les "cases vides".
si on reprend votre exemple des jetons, après avoir placé les 50 jetons verts, vous placez bien les jetons rouges en comptant seulement les cases vides (50).
par contre 30 jetons sur 50 cases vides ça fait 3 jetons toutes les 5 cases et je ne vois pas trop comment répartir ces 3 jetons. intuitivement je dirais 1 1 0 1 0 mais je ne vois pas comment calculer cela dans le cas général.

[mathieu]

j'avais 3 petits gateaux de noël devant moi donc avant de disparaitre dans ma bouche, ça ma refait penser à cette histoire de 3 jetons.

si on calcule 50 / 30 qui fait environ 1,666, on peut utiliser cela comme base pour la position des jetons rouges qui seront donc aux positions suivantes :

• 1,666
• 3,333
• 5
• 6,666
• 8,333
• 10

en arrondissant à l'entier le plus proche, on a alors le placement 0 1 1 0 1 0 1 1 0 1 ...
et en arrondissant à l'entier supérieur ou inférieur, on a des autres placements mais avec le même motif qui se répète donc je pense que les 3 placements ont la même homogénéité.

[tbc92]

Voici un petit bout de code :

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
func main() {
	tbObjectif := []float64{0.5, 0.3, 0.1, 0.07, 0.03}
	var tbRealise []int
	var nb int
 
	for j := 0; j < 5; j++ {
		tbRealise = append(tbRealise, 0)
	}
 
	for i := 0; i < 150; i++ {
		nb0 := nb
		if nb0 == 0 {
			nb0 = 1
		}
		qChoixBest := 0
		qValeurBest := tbObjectif[0] - float64(tbRealise[0])/float64(nb0)
		for j := 1; j < 5; j++ {
			qValeur := tbObjectif[j] - float64(tbRealise[j])/float64(nb0)
			if qValeur > qValeurBest {
				qValeurBest = qValeur
				qChoixBest = j
			}
		}
		tbRealise[qChoixBest]++
		nb++
		fmt.Println( "étape n° ", i, "  couleur choisie=", qChoixBest, "   nb  pour cette couleur=", tbRealise[qChoixBest])
	}
}

A tout moment, pour chacune des 5 couleurs, on compare l'objectif, et le réalisé. Et on choisit la couleur pour laquelle cet écart (le retard donc) est le plus important.
Forcément, certaines couleurs sont en avance (proportion réalisée supérieur à l'objectif) et d'autres en retard ; la première fois que la couleur n°4 apparaît est au 11ème tirage, alors que la proportion-objectif pour cette couleur est 3%.

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
étape n°  0   couleur choisie= 0    nb  pour cette couleur= 1
étape n°  1   couleur choisie= 1    nb  pour cette couleur= 1
étape n°  2   couleur choisie= 2    nb  pour cette couleur= 1
étape n°  3   couleur choisie= 0    nb  pour cette couleur= 2
étape n°  4   couleur choisie= 3    nb  pour cette couleur= 1
étape n°  5   couleur choisie= 0    nb  pour cette couleur= 3
étape n°  6   couleur choisie= 1    nb  pour cette couleur= 2
étape n°  7   couleur choisie= 0    nb  pour cette couleur= 4
étape n°  8   couleur choisie= 1    nb  pour cette couleur= 3
étape n°  9   couleur choisie= 0    nb  pour cette couleur= 5
étape n°  10   couleur choisie= 4    nb  pour cette couleur= 1
étape n°  11   couleur choisie= 0    nb  pour cette couleur= 6
étape n°  12   couleur choisie= 1    nb  pour cette couleur= 4
étape n°  13   couleur choisie= 0    nb  pour cette couleur= 7
étape n°  14   couleur choisie= 2    nb  pour cette couleur= 2
étape n°  15   couleur choisie= 0    nb  pour cette couleur= 8
étape n°  16   couleur choisie= 1    nb  pour cette couleur= 5
étape n°  17   couleur choisie= 0    nb  pour cette couleur= 9
étape n°  18   couleur choisie= 1    nb  pour cette couleur= 6
étape n°  19   couleur choisie= 0    nb  pour cette couleur= 10
étape n°  20   couleur choisie= 3    nb  pour cette couleur= 2
étape n°  21   couleur choisie= 0    nb  pour cette couleur= 11
étape n°  22   couleur choisie= 1    nb  pour cette couleur= 7
étape n°  23   couleur choisie= 0    nb  pour cette couleur= 12
étape n°  24   couleur choisie= 2    nb  pour cette couleur= 3
étape n°  25   couleur choisie= 0    nb  pour cette couleur= 13
etc

[petit_chat]

merci mathieu et tbc92 de vous intéresser à ce problème. Je suis toujours perplexe mais moins avec vos réponses.
Si on sait calculer l'intervalle moyen entre chaque jeton de chaque couleur alors on peut facilement contrôler si un tableau tout fait est homogène ou non. (on peut même préciser une tolérance). Donc une approche, barbare, je vous l'accorde serai de générer des tableaux aléatoirement jusqu'à ce qu'un tableau convienne. Vous en pensez quoi ?

[tbc92]

Vérifier qu'un tableau convient, ça peut être compliqué.
Si on a un tableau avec 100 jetons, et que la couleur A est supposée peser 10%, quel contrôle tu vas faire ? Y a-t-il (environ) 10% de A sur le total, ou y-a-t-il (environ )10% de A parmi les 50 premiers, et aussi parmi les 50 derniers ?

Si tu veux utiliser le hasard, tu peux effectivement le faire.
Soit en adaptant le code que je proposais, en modifiant par exemple les lignes 16 et 18 avec ... + random(0.15) par exemple. Mais il faut peut être modifier le 0.15, mettre un peu plus au début, et diminuer ce nombre au fur et a mesure qu'on avance

Ou sinon, tu t'appuies sur le hasard ainsi :

Code :

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

1
2
3
4
5
6
7
8
9
for i=0 ; i<100 ; i++ {
  r = random()  // Un nombre aléatoire entre 0 et 1
  if r < 0.5 then val = 0
  if 0.5 <= r < 0.8  then val=1
  if 0.8 <= r < 0.9  then val=2
  if 0.9 <= r < 0.97  then val=3
  if 0.97 <= r   then val=4
  print ( r)
}

Par construction, ta suite vérifie les pourcentages imposés. C'est assez simple à réécrire, pour une liste de couleurs qui peut avoir un nombre quelconque de couleurs, et des seuils quelconques.

[mathieu]

Donc une approche, barbare, je vous l'accorde serai de générer des tableaux aléatoirement jusqu'à ce qu'un tableau convienne.

si on commence à placer les 30 jetons rouges alors les 50 jetons rouges auront beaucoup plus de mal à être réparti. donc je pense (et ça reste à prouver) que l'algorithme qui commence par placer les jetons les plus fréquent produit un placement optimal.
à partir de la, utiliser un placement aléatoire aurait une seule utilité, c'est si la construction du tableau complet est trop grand pour tenir en mémoire.

pour aller plus loin, le fait de connaitre le nombre total de jeton ainsi que le nombre de la couleur la plus fréquente permet de déterminer les cases occupées. donc j'ai l'impression qu'à partir de la liste de fréquence, il doit exister un algorithme qui permet de savoir quel jeton est à une case donnée sans avoir besoin de calculer le tableau complet.