Génération de nombre aléatoire avec contrainte

Version imprimable

24/04/2023, 05h34
jreeman

Génération de nombre aléatoire avec contrainte

Bonjour,

j'aimerais générer disons k nombres réels entre 0 et un entier N, sous la contrainte que les k nombres générés satisfont que leur somme fasse N.

Comment feriez-vous ?

Merci,
24/04/2023, 12h59
PhilippeGibault

https://docs.oracle.com/javase/8/doc...il/Random.html
24/04/2023, 13h07
jreeman

Il ne s'agit pas juste de tirer des nombres aléatoires, la somme des nombres tirés doit être égale à N.

Après, je n'ai donné que la classe nécessaire. Ensuite, il suffit d'un peu d'algorithmique (bon, il y a un piège si il reste 1 à la somme).

Soit pour le traitement:

Code:

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
 
package com.developpez;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
 
public class Generation {
 
	private Generation() {
 
	}
 
	public static List<Integer> genereNombres(int total){
		List<Integer> lReturn = new ArrayList<>();
 
		int reste = total;
		int genere;
		Random random = new Random();
 
		while(reste > 0) {
			genere = (reste > 1)? random.nextInt(reste):reste;
			reste -= genere;
			lReturn.add(genere);
		}
 
		return lReturn;
	}
}

Et pour tester la classe:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
package com.developpez;
 
import java.util.List;
 
public class MainGenere {
 
	public static void main(String[] args) {
		verifie(Generation.genereNombres(10));
		verifie(Generation.genereNombres(50));
		verifie(Generation.genereNombres(100));
	}
 
	public static void verifie(List<Integer> list) {
		Integer somme = list.stream().mapToInt(i -> i).sum();
		System.out.println();
		System.out.println("Généré : "+list.toString());
		System.out.println("Somme = "+somme);
		System.out.println();
	}
}

Au pire, ça m'aura fait un exercice...

24/04/2023, 18h28
jreeman

Je ne vois pas comment faire pour que la somme des valeurs générées vaut par N (par exemple 3).
24/04/2023, 20h52
thelvin

C'est des maths, pas de la programmation.

On pourra remarquer que si k = 1, alors il n'y a pas d'aléatoire possible. Le nombre "choisi" doit être égal à N et puis c'est tout.

De même, si k = 2, quel que soit le premier nombre A qu'on tire, le deuxième nombre n'est pas aléatoire, il doit être égal à N - A. Du coup il s'agit plutôt de tracer un segment de 0 à N et de tirer au hasard un point sur ce segment. Ensuite, on obtient deux nombres en prenant les longueurs des deux segments de part et d'autre de ce point.

A partir de cette considération, on peut imaginer de nombreuses manières de partitionner au hasard en k sous-segments le segment 0 à N. Tout dépend de ce qu'on veut.

Personnellement je tirerais (k - 1) points au hasard sur le segment, puis je les trierais dans l'ordre, et je prendrais les longueurs des segments de gauche à droite. Ça me semble être le tirage aléatoire le plus uniforme. Mais ce n'est pas forcément ce qu'on veut.
25/04/2023, 02h34
bouye

Citation:

Envoyé par jreeman

Il ne s'agit pas juste de tirer des nombres aléatoires, la somme des nombres tirés doit être égale à N.

Oui ben tu tires ton nombre aléatoire et tu vérifies la condition après et si elle n'est pas vérifiée tu continues de tirer... bref do { [...] } while (<test>).
Puisque K est connu, un for() fait aussi bien l'affaire et on dispose de conditions d’arrêt supplémentaire.

A chaque fois que tu tires un nombre, tu déduis ce nombre que tu viens de tirer de la valeur max (reste0 = N, reste1 = reste0 - tirage0, etc.).
Le nombre généré le plus récent est stockée dans une liste/un tableau.
A partir du moment ou ton reste vaut 0, tous les autres nombres a tirer valent 0.
Si tu arrives au Keme nombre (indice K-1) sans que la somme vaut N/le resteK-1 vaut 0, du coup le dernier nombre est pas aléatoire mais vaut resteK-1.
Rien de bien complique.
25/04/2023, 02h53
jreeman

J'ai oublié de dire que je voulais une loi uniforme et avec ta méthode je ne suis pas bien sûr que ça le soit.
25/04/2023, 03h59
bouye

Bon je suis un peu a cote de la plaque en maths et en stats depuis le temps mais en faisant un grand nombre de série et en moyennant les résultats ça devrait pas retourner une valeur proche de N/K ?
Peut-etre une grosse c*** de ma part : faire K tirages aleatoires sur une valeur de N/K puis repartir ce qu'il reste de N - Somme(tirages) aléatoirement sur les valeurs tirées ?
25/04/2023, 04h48
jreeman

Par exemple je tire k=3 nombres entre 0 et N=6 (maximum) et je veux que la somme vaille N=6.

Je tire un premier nombre entre 0 et 6, par exemple 4, donc je dois encore tirer un nombre entre 0 et 2 pour pas que ça dépasse 6, j'obtiens 1, la somme fait 4+1=5, donc le dernier nombre vaut 1 pour que ça fasse 6 pile poil.

Je crois en effet qu'avec ça on a bien une loi uniforme.
25/04/2023, 06h37
bouye

C'est donc exactement ce qui t'as été décrit plus haut. C'est pas vraiment comme ça que j'ai compris le sens d'une loi uniforme.
25/04/2023, 06h55
jreeman

Si c'est cela sauf que tu dois penser pas en dimension 1et ne pas mélanger entre les probalités et les valeurs des variables dont la somme fait une constante N.

Si par exemple X=(a, b, c) une variable aléatoire, chaque réalisation de X par exemple avec N=3 : X=(1, 1, 1) ou X=(0, 2, 1) ou X=(0, 1, 2) ou X=(3, 0, 0) ou X=(π/2, e/2, (6-π-e)/2) etc... ont tous la même chance d'être tiré, c'est uniforme.

Par ailleurs, toujours sur cet exemple, a, b, c sont des réels donc c'est une loi uniforme continue pas discrète.
25/04/2023, 12h26
thelvin

J'ai pas compris pourquoi un message a été effacé. Il me semble pourtant qu'il donnait la solution qui semble correcte.

A noter que ce que j'ai dit plus haut respecte les contraintes voulues :

- somme des "nombres tirés" égale à N, normal c'est par construction
- l'espérance de chaque nombre tiré est N/k
- tous les nombres tirés ont le même écart type, qui est non-nul

Par contre, elle ne fait que k-1 générations aléatoires pour obtenir la génération de k nombres, ce qui fait moins d'entropie qu'on attendrait normalement pour k nombres, et un écart type bizarre même si non nul.

Du coup, il me semble que la meilleure solution était dans le message effacé.
25/04/2023, 12h44
jreeman

Quel message ?
Ce que tu as dit plus haut où ?
25/04/2023, 13h43
thelvin

Citation:

Envoyé par jreeman

Quel message ?

Le tien, celui que tu as effacé. Il n'y en a qu'un, tu sais.

Citation:

Envoyé par jreeman

Ce que tu as dit plus haut où ?

Là :

Citation:

Envoyé par thelvin

C'est des maths, pas de la programmation.

On pourra remarquer que si k = 1, alors il n'y a pas d'aléatoire possible. Le nombre "choisi" doit être égal à N et puis c'est tout.

De même, si k = 2, quel que soit le premier nombre A qu'on tire, le deuxième nombre n'est pas aléatoire, il doit être égal à N - A. Du coup il s'agit plutôt de tracer un segment de 0 à N et de tirer au hasard un point sur ce segment. Ensuite, on obtient deux nombres en prenant les longueurs des deux segments de part et d'autre de ce point.

A partir de cette considération, on peut imaginer de nombreuses manières de partitionner au hasard en k sous-segments le segment 0 à N. Tout dépend de ce qu'on veut.

Personnellement je tirerais (k - 1) points au hasard sur le segment, puis je les trierais dans l'ordre, et je prendrais les longueurs des segments de gauche à droite. Ça me semble être le tirage aléatoire le plus uniforme. Mais ce n'est pas forcément ce qu'on veut.
25/04/2023, 19h36
jreeman

Celui où je disais où je tirais k nombre entre 0 et 1 et je les divise par leur somme et je multiplie par N. Oui c'est le plus simple selon moi. Je l'ai effacé car ce n'étais pas votre méthode du coup j'ai douté et pensé que c'était faux, mais en effet je pense que c'est le mieux.