question sur random

Version imprimable

01/06/2007, 10h12
PHPkoala

question sur random

Bonjour,

Je me permet de vous écrire pour vous demander s'il existe un moyen de faire un rand avec les numéros qui ne seront pas reutilisable.

Exemple :

je souhaite faire un tirage de 10 boules numérotées de 1 à 10 tirées au hasard

si je tire une boule je souhaite faire en sorte que au prochain rand le numéro ne puisse pas être retiré et ainsi de suite.

Merci
01/06/2007, 10h18
TheGzD

En quoi est-ce un problème de C ? :kill:
01/06/2007, 10h34
odsen.s

Salut,

J'avais eu à faire ça une fois.
En fait, dès qu'un nombre était tiré, je le posais dans une pile.
Ensuite, je générais des nombres aléatoires que je ne retenais que s'il n'existaient pas dans la pile.
Ainsi, j'avais à chaque fois des nombres nouveaux.

Ceci dit, il existe peut-être une méthode plus rapide.
01/06/2007, 10h46
PHPkoala

Citation:

Envoyé par TheGzD

En quoi est-ce un problème de C ? :kill:

heu je bosse sur du C donc j ai pensé que j'aurai besoin d'aide des gens qui font du C

odsen.s j'avais aussi pensé à ca mais comme ca doit être un programme sur un serveur qui envoie des données par socket ca serait trop lourd
01/06/2007, 10h53
amine_en_france

stoque tes resukats dans un tableau et a chaque tirage verifie si le resulat tiré existe deja, si c le cas reintère
01/06/2007, 10h59
millie

Vos méthodes ne sont pas du tout optimisé, il y a des méthodes beaucoup plus rapide.

Citation:

je souhaite faire un tirage de 10 boules numérotées de 1 à 10 tirées au hasard

Crée un tableau de taille 10 que tu remplis de 1 à 10.
Génère un nombre p entre 0 et 9.
Fais une permutation de tab[0] tab[p]
Génère un nombre p entre 0 et 8
Fais une permutation de tab[1] tab[p+1]
....

C'est très efficace et rapide car linéaire à tous les coups, contrairement à vos méthodes qui étaient quadratique en espérance.
01/06/2007, 13h49
InOCamlWeTrust

Il y a beaucoup plus simple : si le nombre que tu viens de tirer grâce à rand est déjà sorti, tu en tires un deuxième, et ainsi de suite.

On ne reprogramme pas ce genre de fonctions (difficiles à faire, d'ailleurs).
01/06/2007, 13h55
millie

oui, et comment sais tu si il est déjà sorti ? Il faut les stocker et donc reparcourir des listes.
Le programme peut ne pas se finir, c'est un algorithme de type Las vegas que tu proposes d'espérance quadratique.

Autant utiliser un algorithme comme je l'ai proposé qui s'exécute en temps linéaire à coup sûr.

Pareil que Millie, autant partir d'un tableau et le mélanger.

Mais je préfère mélanger non pas avec des permutations, mais un tri:

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
30
31
32
33
34
35
36
37
/* Attention : Code compilé mais non testé */
#include <stdio.h>
#include <stdlib.h>
 
struct mel
{
	int nb;
	int rnd;
};
 
int compare(const void *pcva, const void *pcvb)
{
	const struct mel * pcA = pcva;
	const struct mel * pcB = pcvb;
 
	return pcA->rnd - pcB->rnd;
}
 
void Tirage(void)
{
	struct mel tab[10];
	int i;
 
	/* Initialisation et melange */
	for(i=0 ; i<10 ; i++)
	{
		tab[i].nb = i;
		tab[i].rnd = rand();
	}
	qsort(tab, 10, sizeof(tab[0]), compare);
 
	/* Affichage */
	for(i=0 ; i<10 ; i++)
	{
		printf("%d\n", tab[i].nb);
	}
}

Je n'ai pas fait de test poussé, mais je pense qu'un tableau ainsi mélangé aurait une meilleure distribution...

02/06/2007, 00h29
Emmanuel Delahaye
Citation:

Envoyé par PHPkoala

Bonjour,

Je me permet de vous écrire pour vous demander s'il existe un moyen de faire un rand avec les numéros qui ne seront pas reutilisable.

Exemple :

je souhaite faire un tirage de 10 boules numérotées de 1 à 10 tirées au hasard

si je tire une boule je souhaite faire en sorte que au prochain rand le numéro ne puisse pas être retiré et ainsi de suite.

Problème d'algo très simple.

Créer un tableau avec les 10 nombres triés
Mélanger le tableau (shuffle)
Lire séquenciellement le tableau.

Pour mélanger, faire ceci au moins 10 fois le nombre d'éléments (ici 10, soit 100 fois)
Code:

1 2 3 4 5 6 1 - tirer un nombre a entre 0 et 9 faire 2 - tirer un nombre b entre 0 et 9 tant que a et b sont egaux 3 - inverser tab[a] et tab[b]
[-mod- Rien de ceci n'a à voir avec le langage C. Déplacé sur 'algorithmes'.]

Permutations d'un ensemble
Une permutation d'un ensemble est par définition, une bijection de cet ensemble sur lui-même. Les n premiers entiers écrits dans un ordre différent représentent une permutation de cet ensemble. Le nombre total des permutations pour un ensemble à n éléments est factorielle n.
Les permutations interviennent dans de nombreux exemples:
Arrivée possible des n chevaux d'une course .
Résultat d'un 'battage' de cartes
Du point de vue du modèle il s'agit du tirage avec ordre de n éléments parmi n.
Modéliser une permutation revient donc à tirer un premier entier entre 1 et n, puis un deuxième qui ne soit pas le premier et ainsi de suite. La méthode qui consiste à faire un tirage aléatoire et à le rejeter s'il n'est pas bon est à rejeter car plus on approche de la fin et plus les tirages sont difficiles.
On peut s'intéresser aux 'points fixes' (éléments restant en place). Curieusement la probabilité d'existence de tels points fixes ne dépend pas du nombre total des éléments (voir exercice pb de Bernoulli Euler).
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 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 #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 100 int T[N]; void init ( int A[], int n) // initialisation avec des nombres négatifs { int i; for (i=0; i<n; i++) A[i]=-1; } void showT () // pour voir la permutation {int i ; for (i=0; i<N; i++) printf("%3d", T[i]); printf("\n"); } int freeplace (int index) // index étant un entier recherche la première place libre de rang index dans le tableau T { int i; int j = 0; for (i=0; i<N; i++) {if (T[i]<0) j++; if (j==index) return i;} return 0; } int random (int k) // retourne un entier alétoire entre 1 et k { return 1+rand()%k;} void fillT() // remplit le tableau avec une permuation aléatoire {int i; int j; srand( (unsigned)time( NULL ) ); for (i=0; i<N; i++) {j=random(100-i); T[freeplace(j)]=i+1; } } int inplace () // calcule le nombre de points fixes {int i; int result=0; for (i=0; i<N; i++) if (T[i]==i+1) result++; return result; } void main () { init (T, N) ; fillT(); showT(); printf("%d\n", inplace()); }

Bonjour,

Je viens d'essayer la méthode proposée par millie :

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
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 9
 
int main(void)
{
   size_t i;
   int tab[N+1] = {0};
 
   srand(time(NULL));
 
   /* initialisation du tableau */
   for(i = 0; i < N+1; ++i)
   {
      tab[i] = i;
   }
 
   /* melange */
   for(i = 0; i < N+1; ++i)
   {
      int temp;
      int p = (int)(rand() / (double)RAND_MAX * (N-i));
 
      temp = tab[i];
      tab[i] = tab[p+i];
      tab[p+i] = temp;
   }
 
   /* affichage du résultat */
   for(i = 0; i < N+1; ++i)
   {
      printf("%d : %d\n", (int)i, tab[i]);
   }
 
   return 0;
}

Seulement, si vous testez, vous vous rendrez compte que tab[0] vaut au final toujours 2. Y a-t-il une solution à ce problème ? Ca vient peut-être de mon programme et pas de l'algo proposé ?

Merci.

03/06/2007, 12h29
millie

Remplace : int p = (int)((double) rand() / (double)RAND_MAX * (N-i));

Par : int p = rand() % (N+1-i);

Il est également possible d'utiliser une méthode plus efficace étant donné que la distribution n'est pas terrible en utilisant l'opérateur modulo :
http://c.developpez.com/faq/c/?page=..._random_bornes
03/06/2007, 12h39
odsen.s

Salut millie,

Alors ça c'est dingue 8O
Avec la méthode via l'opérateur modulo, le problème n'apparaît pas, mais il apparaît avec la méthode de mon programme et avec la méthode de Jean-Marc (cf ton lien).
03/06/2007, 12h50
millie

J'ai l'impression que son générateur me donne toujours le même premier chiffre... Par exemple, en démarrant et en affichant alea(9), j'obtiens toujours la même chose au premier coup...

Je n'ai pas trouvé pourquoi.
03/06/2007, 12h57
odsen.s

Même expérience chez moi... et pour

Code:

(int)((double) rand() / (double)RAND_MAX * (N-i))

c'est aussi le même chiffre qui sort en premier.
(Et avec cette méthode, je ne vois pas ce qui peut faire que ça soit toujours le même nombre qui sorte en premier !)

EDIT : ça y est j'ai compris, le premier nombre renvoyé par la fonction rand() n'est pas le même, mais comme l'éxécution du programme génère des "graines" proches les unes des autres (j'ai fait les tests dans la même minute), le premier nombre renvoyé par rand() varie peu (9647, 9650, 9658...), ce qui fait qu'avec cette méthode on a toujours le même arrondi.

Je vais chercher une méthode pour corriger le problème.

EDIT2 : j'ai trouvé une solution : au lieu de faire un srand(time(NULL)), faire un srand(time(NULL)*1000), ainsi la graine choisie est plus différente entre deux éxécution qu'avant, et on des des premiers nombres générés différents.
03/06/2007, 13h19
Emmanuel Delahaye

Citation:

Envoyé par odsen.s

EDIT2 : j'ai trouvé une solution : au lieu de faire un srand(time(NULL)), faire un srand(time(NULL)*1000), ainsi la graine choisie est plus différente entre deux éxécution qu'avant, et on des des premiers nombres générés différents.

Intéressant. J'avais résolu ce problème en ignorant le premier tirage, mais cette solution est effectivement préférable.

Citation:

J'avais résolu ce problème en ignorant le premier tirage, mais cette solution est effectivement préférable.

Pourquoi est-ce préférable ? Ignorer le premier tirage ne suffisait pas ?

J'ai rencontré un deuxième problème, toujours avec le même algo : le dernier chiffre est toujours le même (ce qui paraît logique). J'ai corrigé comme ceci (traitement spécial pour le dernier chiffre) :

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
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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 9
 
int main(void)
{
   size_t i;
   int tab[N+1] = {0};
 
   srand(time(NULL)*1000);
 
   /* initialisation du tableau */
   for(i = 0; i < N+1; ++i)
   {
      tab[i] = i;
   }
 
   /* melange */
   for(i = 0; i < N+1; ++i)
   {
      int p;
      int temp;
 
      if(i == N)
      {
         /* p est compris entre 0 et N */
         p = (int)(rand() / (double)RAND_MAX * N);
 
         /* on permute tab[N] et tab[p] */
         temp = tab[N];
         tab[N] = tab[p];
         tab[p] = temp;
      }
 
      else
      {
         /* p est compris entre 0 et N-i */
         p = (int)(rand() / (double)RAND_MAX * (N-i));
 
         /* on permute tab[p+i] et tab[i] */
         temp = tab[i];
         tab[i] = tab[p+i];
         tab[p+i] = temp;
      }
   }
 
 
   /* affichage du résultat */
   for(i = 0; i < N+1; ++i)
   {
      printf("%d : %d\n", (int)i, tab[i]);
   }
 
   return 0;
}

Commentaires, autres méthodes bienvenus ;)

03/06/2007, 19h34
pseudocode
Citation:

Envoyé par odsen.s

J'ai rencontré un deuxième problème, toujours avec le même algo : le dernier chiffre est toujours le même (ce qui paraît logique).

Commentaires, autres méthodes bienvenus ;)

Ah! la joie des piquets et des intervalles...
Code:

1 2 /* p est compris entre 0 et N (inclus) */ p=(int) ((N+1)*rand()/(RAND_MAX+1.0));
03/06/2007, 20h40
O( N )

Question déjà vu ici http://www.developpez.net/forums/sho...d.php?t=191130
mais pas en C :aie:

Millie à la meilleure réponse il me semble. :king:
03/06/2007, 22h34
Médinoc

Le coup du rand() qui donne toujours la première valeur, il me semble qu'il a déjà été évoqué sur le forum...

Un truc genre un "bug connu de la libc"...
09/06/2007, 21h23
acx01b

bonjour

à mon avis la méthode de millie est la meilleure tant que l'alphabet n'est pas trop grand

car dans son algo il s'agit de fabriquer séquentiellement un arrangement de plus en plus grand sur l'alphabet, qui mènera à la fin à une permutation aléatoire de l' ensemble

sur un alphabet (ordonné!) dont la taille tend vers l'infini, il faudra faire autrement:

taille de l'aphabet = n
nb_tires = 0

faire tirage {
r = random entre 1 et n-nb_tires
k = nbr d'elements dans le tableau inférieurs au r ieme element de l'alphabet
r += k
mettre r dans le tableau tout en gardant le tableau trié
nb_tires += 1
retourner le r ieme element de l'alphabet
}

est je pense une solution correcte
11/06/2007, 09h11
ol9245
La question revient en effet à générer une permuation aléatoire d'un ensemble 1,2,3,...N. une fosi la permutation faite, il suffit de prendre dans l'odre les éléments du tableau permuté.
l'algo pour cela est absolument codifié
Code:

1 2 3 4 pour i = 1 à N-1 tirer un entier j aléatoire dans [i N] permuter les éléments i et j next
on vérifie qu'il y a bien selon cet algo N! sorties possibles, ce qui correspond effectivement au nombre de permutations possible. donc ce programme tout simple garatit que toutes les permutations sont équiprobables.

Note, en matlab, il y a une instruction pour cela : randperm

OL