Discussion :

[Gregory.M]

Bonjours ,


j'ai un soucis d'algo...

1. j'ai un tableau avec des noms
2. un commande qui déclenche un random.

ce la doit générer plusieurs groupe de 2 personnes, mais lorsque que l'on réutilise la fonction les noms ne peuvent se retrouver un des noms avec lesquels ils ont déja été.

je n'arrive pas à creer l'algo correspondant à ca.


Avez vous une idée?

[theMonz31]

il suffit que lorsque ton nom est généré, tu le compares aux noms existants et tant que c'est le cas, tu regenères

The Monz, Toulouse

[Gregory.M]

non ce n'est pas possible comme ca par exemple dans mon tableau j'ai:
"A", "B", "C", "D"

1. Random()
A&B
C&D

2. Random()
A&C
B&D

3. Random()
A&D
B&C

voila
la c'est facile mais quand il y a plus de 4 éléments dans le tableau ca devient plus compliqué...

[theMonz31]

en utilisant un dictionnaire pour stocker les resultast du random , il te sera facile de savoir si c'est ok....

il suffit que tu utilises par exemple AB comme clé dans ton dictionnaire

Ou alors, j'ai pas encore tout compris de ce que tu voulais faire

The Monz, Toulouse

[Gregory.M]

Je n'ai pas de dictionnaire.
je fais un script pour Second Life, et il n'y a pas grand chose.
j'ai les commandes basiques de boucles, et variables...

[theMonz31]

tu es dans quel langage ?

[Gregory.M]

lsl (linden script language)

Mais ce n'est pas une question de language, c'est une question d'algo

[Nikoui]

L'algo, tu l'a déjà (cf ton premier poste). Une facon de faire "sans dictionnary" :

A chaque fois que tu génére une série de "couple" tu les stockes dans un coin.
A la prochaine génération, pour chaque couple tu regardes si tu l'a deja généré dans ta liste "de sauvegarde", si oui tu annule ce couple et tu re tente une nouvelle génération, si non tu valide ce couple (et tu l'ajoute dans ta liste de sauvegarde).
Le probleme : quand vas tu vider cette liste de sauvegarde qui va grossir à chaque appel (ou autrement dit, combien d'appel successif peut tu faire avant d'épuiser toutes les solutions).

Par contre, pour cela, il faut que tu sois capable de stocker la liste des couples générés entre 2 appels (et ça, ça depend des possibilité du langage que tu utilises).


Quand tu dis que tu as un problème d'algo, c'est pour la partie ci dessus (ne pas re-générer les même couples lors d'appels successifs) ? ou pour générer les couples lors d'un appel ?

[Gregory.M]

Mon probleme est de ne pas regénérer les memes couple

[Jean-Marc.Bourguet]

Chaque fois que tu tires un nom, tu l'enleves de ton tableau. Si tu ne peux pas, tu copies d'abord le tableau (ou tu crees un tableau d'indices pour prendre moins de place qu'un tableau de chaines).

[pseudocode]

Tu peux conserver pour chaque lettre la liste des lettres qui peuvent encore lui etre associée.

au départ: {A,B,C,D}

Les pairs possible pour chaque lettres sont:
A : [B,C,D]
B : [A,C,D]
C : [A,B,D]
D : [A,B,C]

- Tu fais ton randomize: (A & C), (B & D)

- Tu testes que les pairs sont possibles:
* C dans la liste de A: ok
* B dans la liste de D: ok

A : [B,D]
B : [A,C]
C : [B,D]
D : [A,C]

[Gregory.M]

oui mais la j'ai juste utilisé un exemple, en réalité il ya une petite 10aine de noms...

[pseudocode]

Ca marche aussi. Il suffit de faire des listes plus grandes. Au bout d'un moment ca deviendra plus economique de faire une matrice de co-occurence:

liste: {A,B,C,D,E,F,G,H}

1. randomize: (A & C), (B & D), (E & G), (F & H)

2. marquage dans la matrice

Code :

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

1
2
3
4
5
6
7
8
9
10
 
  A B C D E F G H
A     *
B       *
C *
D   *
E             *
F               *
G         *
H           *

Note: une demi matrice suffit (triangle du haut-droite ou du bas-gauche)

[edfed]

une liste de possibilité par entité semble etre la meilleure.
seulement cette liste doit etre complete du debut à la fin, un champ deja pris dans chaque celulle servira de drapeau
puis avec ce champ, on peu aussi faire un compteur pour savoir depuis combien de temps la relation à eu lieu.
et des que le compteur atteint une certaien valeur, l'entrée est reutilisable.

A: {B,0,C,0,D,0,E,0,F,0,G,0,H,0,J,0,K,0}
apres confrontation de A et B
A: {B,1,C,0,D,0,E,0,F,0,G,0,H,0,J,0,K,0}
apres confrontation de A et F
A: {B,2,C,0,D,0,E,0,F,1,G,0,H,0,J,0,K,0}
au bout d'un temps X = nombres d'adversaires possibles moins une marge pour avoir plus de solutions..
A: {B,X,C,0,D,?,E,?,F,X-1,G,0,H,?,J,?,K,?}
A: {B,0,C,0,D,?,E,?,F,X-1,G,0,H,?,J,?,K,?}
et tout rentre dans l'ordre. on peu reutiliser B car ça fait longtemps qu'on l'a pas vu.

c'est possible aussi avec le graphe ( matrice) du post precedant.

le rnd serait utilisé pour indexer la liste de combinaisons possibles et si l'index pointe sur un adversaire deja utilisé, pointer sur le prochain...

en fait, vu de loin, les tables et la matrice sont la meme chose.

[Jedai]

Ne serait-il pas bien plus simple de faire un shuffle (mélange aléatoire, cf "algorithme de Fisher-Yates") de la liste et ensuite de prendre les éléments deux par deux ? L'algorithme est super-simple à implémenter, et la complexité est excellente (O(n)).

--
Jedaï

[Jean-Marc.Bourguet]

Ne serait-il pas bien plus simple de faire un shuffle (mélange aléatoire, cf "algorithme de Fisher-Yates") de la liste et ensuite de prendre les éléments deux par deux ? L'algorithme est super-simple à implémenter, et la complexité est excellente (O(n)).

Tu fais la meme erreur que moi. Le probleme n'est pas pour faire un tirage, mais plusieurs tels qu'une paire donnee n'apparaisse au maximum que dans un tirage.

[Nikoui]

Ne serait-il pas bien plus simple de faire un shuffle (mélange aléatoire, cf "algorithme de Fisher-Yates") de la liste et ensuite de prendre les éléments deux par deux ? L'algorithme est super-simple à implémenter, et la complexité est excellente (O(n)).

Mais ça ne résoud pas vraiment le problème du posteur : comment faire pour que si on appelle 2 fois de suite cette fonction, on ne retrouve pas à nouveau un couple qu'on aurai déja généré la première fois (parmis tous les couples générés)

[edfed]

fastoche, il faut memoriser les couples genérés, un liste:
chaque item à un id fixe, cet ID est un pointeur vers une structure qui indique quels sont les couples deja genérés avec cet ID.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
par exemple:
 toto = 1
 ouioui = 2
 riri = 3
 fifi = 4
 loulou = 5
 sangoku = 6 ;il va leur mettre la rouste de leur vie!
 
tirages:
.1 dd 3,5,4,2,null
.2 dd 6,4,5,1,null
...

dd ça veu dire definir un dword, 32 bits...

en gros, null, c'est une valeur pour dire que le tirage n'a pas encore eu lieu.
on peu limiter la memoire de tirages pour pouvoir repeter un meme tirage plus tard.
pour ce qui est du tirage au sort, il suffit alors de genrer un nombre aléatoire , tester si il a deja été deja fait, et s'il a deja été fait, incrementer ce nombre et tester jusqu'à ce qu'il soit OK. ok?
sans memoriser les tirages deja fait, il est impossible dedeterminer si ils on eu lieu ou non.