Discussion :

[sayajin]

Salut comment faire la chose suivante :

- imaginez un tableau de booléen ou toutes les valeurs sont à false et je veux un algo qui de manière aléatoire me mets tout les valeurs à true sans repasser par un index du tableau qui est déjà à true !

[PRomu@ld]

Il y a une chose que je ne comprend pas :

un algo qui de manière aléatoire me mets tout les valeurs à true

Tu veux réelement mettre toutes les cases de ton tableau à true (parce que là, ça n'est pas un problème)

Sinon, quelque soit ta réponse, tu peux toujours stoquer dans une liste ou un arbre tous les indices qui ne sont pas déjà à true, et comme ça tu n'effectue ton opération que sur ces indices là.

(le mieux serait un arbre de recherche et de préférence équilibré)

[pirus]

une methode ultra-simple qui peut s'appliquer sous les deux conditions suivantes:

. la taille de ton tableau doit etre une puissance de 2,
. le degre d'entropie est (tres) faible, mais peut etre satisfaisant selon l'application.

le principe consiste a appliquer un masque XOR sur l'index de ton tableau; soient N la taille du tableau (qui je le repete, doit etre une puissance de deux), X une valeur aleatoire telle que 0 < X < N, et i0 la valeur sequencielle de l'index variant de 0 a N-1, "^" representant l'operateur "ou exclusif".

le resultat de l'operation i0^X te donnera une valeur i1, unique pour chaque valeur de i0, comprise entre 0 et N-1 inclus, et differente de i0 si X != 0.

voici un exemple simple, avec un tableau de 8 elements (N=8) et un masque de valeur 5 (X=5):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 i0           i1 (= i0^5)
----------------------
 0 (000)  ->  5 (101)
 1 (001)  ->  4 (100)
 2 (010)  ->  7 (111)
 3 (011)  ->  6 (110)
 4 (100)  ->  1 (001)
 5 (101)  ->  0 (000)
 6 (110)  ->  3 (011)
 7 (111)  ->  2 (010)

tu peux voir que toutes les valeurs de l'ensemble de depart (les i0) se retrouvent dans l'ensemble d'arrivee (les i1), mais dans un ordre different (la valeur en binaire des index est representee entre parentheses).

le "ou exclusif" ne fait qu'inverser les bits dont la position est donnee dans le masque. exemple 1111 ^ 0011 = 1100 (les deux bits de poids faibles sont inverses, puisqu'ils sont a 1 dans le masque, les autres gardent la meme valeur).

ton code ressemblerait (en C) a quelque-chose comme:

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
 
#define N          256  /* taille du tableau  */
#define X         0x55  /* masque "aleatoire" */
#define FALSE  (bool)0
#define TRUE  (~FALSE)
 
/* definition du type booleen */
typedef unsigned char bool;
 
/* vecteur (tableau) de booleens */
static bool v[N];
 
int i0, i1;
 
/* initialisation des valeurs a FALSE */
for( i0 = 0 ; i0 < N ; ++i0 )
  v[i0] = FALSE;
 
/* initialisation "aleatoire" des valeurs a TRUE */
for( i0 = 0 ; i0 < N ; ++i0 ) {
  i1 = i0 ^ X;
  v[i1] = TRUE;
}

c'est tout. c'est sans doute la methode la plus simple possible, tres souvent employee des qu'il s'agit de faire un "shuffle" sur de longues listes (jeux, listes d'IP a scanner, etc..).

[User]

Salut,

Si j'ai bien compris

Soit t1 ton tableau de boolean (de taille n) avec les valeurs à false.

tu créer 1 autre tableau t2 de n entier contenant les valeurs de 1 à n.

La 1ère fois tu génère 1 nombre aléatoire i entre 1 et n.
Le nombre t2(i) est l'indice de ton tableau t1:
tu fais t1(t2(i))=True
Puis tu supprime t2(i) dans ton tableau t2 et tu redimensionne ce tableau t2 à (n-1) contenant le reste des valeurs. (sert toi eventuellement d'1 autre tableau)

La 2ème étape tu génère 1 nombre aléatoire i entre 1 et (n-1)
Le nombre t2(i) est le 2ème indice de ton tableau t1:
tu fais t1(t2(i))=True
etc..

ceci n fois

de cette manière tu génère à chaque fois un indice t2(i) différent pout t1

@+

[pirus]

je ne sais pas a qui est adresse le message precedant (de 17h03), mais juste dans le cas ou il me concerne, ce n'est pas du tout ca.

la methode que je propose consiste a appliquer une operation logique (XOR) sur l'index, afin de donner l'illusion d'une suite de valeurs desordonnee.

a aucun moment il n'est question d'un second tableau, c'est justement ce que sayajin souhaite eviter.

[User]

@ Pirus

Ce message ne t'est pas destiné, je cherchais juste à comprendre ce que souhaite faire sayajin.

Et je n'ai pas vu dans son message comme tu le dis qu'il souhaite éviter l'utilisation d'1 tableau.

j'ai juste lu:

sans repasser par un index du tableau qui est déjà à true !

que je comprends par générer des index à chaque fois différent des précédents

Ceci dit on peut aussi utiliser une liste d'index à la place du tableau t2, tout dépend du langage. (Mais on doit pouvoir accéder à 1 élément de la liste d'index(tiré au hazard) par 1 index)

Maintenant je ne prétend pas détenir la solution

J'essaie juste de comprendre...

[sayajin]

Bon y'a pas mille solution : faut créer un deuxième tableau qui représentera les index du premier tableau, je mélange ce tableau et je mets à true les valeurs du tableau booléen en prernant pour index les valeurs du tableau mélangé.

Je croyais pouvoir le faire sans utiliser un deuxième tableau mais c'est inévitable !