Discussion :

[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.

Merci

[TheGzD]

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

[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.

[PHPkoala]

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

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

[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

[millie]

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

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.

[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).

[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.

[Médinoc]

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 C :

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
/* 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...

[Emmanuel Delahaye]

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 :

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

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'.]

[Zavonen]

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 :

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
 
#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());
}

[odsen.s]

Bonjour,

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

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
#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.

[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

[odsen.s]

Salut millie,

Alors ça c'est dingue
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).

[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.

[odsen.s]

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

Code :

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

(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.

[Emmanuel Delahaye]

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.

[odsen.s]

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 :

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
#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

[pseudocode]

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 :

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

1
2
/* p est compris entre 0  et N (inclus) */
p=(int) ((N+1)*rand()/(RAND_MAX+1.0));

[O( N )]

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

Millie à la meilleure réponse il me semble.