Discussion :

[A. D.]

Bonjour à tous,

Voici ma problèmatique (les valeurs données le sont à titre indicatif et sont susceptibles de changer) :

Je dispose d'un ensemble d'éléments NE=500 à présenter à un ensemble d'individus NI=1500. Je souhaite que chaque individu voit NC=50 éléments parmis les NE.
Je suis donc à la recherche d'un algorithme qui me permettrait de tirer des ensemble de NC=50 éléments parmis les NE=500 pour chacun de mes individus de sorte qu'au global, sur l'ensemble des individus, chaque élément soit vu un nombre similaire de fois (équilibre).

Je connais quelques modèles de plan d'expériences mais ils ne m'ont pas semblé convenir à ce cas précis et j'ai eu du mal à trouver quels mots-clés utiliser pour une recherche.
Je m'adresse donc à vous, si ce genre de problématique vous parle, je suis intéressée par toutes vos suggestions.

Merci d'avance !


Cordialement,


A.D.

[picodev]

Bonjour,

À première vue je tenterais une approche naïve. Chaque élément doit être réparti sur NEI=NE*NI/NC individus. Donc pour chaque élémént je choisi NEI individus distincts aléatoirement parmi ceux qui ont le moins d'éléments et je leur attribue l'élément en cours. En supposant qu'il y a un nombre suffisant d'individus, d'éléments, etc ...

[kolodz]

Sa chant que Ni >> à Ne, je me demande pourquoi tu ne fait pas un tirage sans remis, jusqu'au moment où tu n'as plus d'éléments dans Ne. A ce moment là, tu remets en "jeu" l'ensemble des éléments de Ne.

Si tu as peur qu'un groupe de 10 individues ne soit pas en mesure de déterminer Ne facilement (car 10*50 = 500 = Ne = Un tirage complet). Il t'es possible de faire les 1500 tirages de 50 éléments. Ainsi tu aura une liste de 1500 tirage de 50 éléments que tu n'aura plus qu'à mélanger avant de distribuer pour t'assurer que personne ne détermine ton Ne facilement.

Il t'es possible de faire des groupes de tirage plus petit genre 100 tirage de 50 (ce qui fait 10 fois Ne). Et refaire un nouveau 100 tirage de 50 quand il aura besoin de plus.

C'est d'ailleurs ce que font les casinos pour le poker quand il mélange plusieurs paquet de carte pour faire la pioche.

Cordialement,
Patrick Kolodziejczyk.

[A. D.]

Re-bonjour,

Tout d'abord merci à tous les deux pour vos réponses

Je me demandais s'il n'existait pas des algorithmes "prêts à l'emploi" pour ce genre de "tirage avec équilibre", ce qui m'aurait évité de l'écrire moi-même (si j'avais un "nom" d'algo, j'aurais pu chercher s'il existait déjà dans un des packages de mon langage de programmation...). Si jamais vous avez des noms à me donner, cela dit je suis preneuse ^^

Du coup, j'ai écris un petit programme en suivant le conseil de kolodz, à savoir tirage aléatoire sans remise et re-remplissage de la pile une fois vide (ou presque). Je me suis assurée de faire ça de telle sorte qu'un même individu ne pourra pas tomber plusieurs fois sur le même élément (dans le cas où le nombre d'éléments à tirer NC n'est pas un multiple du nombre total d'éléments NE).

-> Ma dernière question est la suivante : comment tester de manière "maligne" qu'aucun des individus ne voit exactement la même sélection de NC éléments (l'ordre n'a pas d'importance, ie. [ 1 , 2 , 5 ] et [ 5 , 1 , 2 ] sont considérées comme la même sélection) ?
En effet, je ne vois pas a priori de manière "simple" et pas trop "coûteuse en temps" de faire un tel test...

Merci d'avance !


Cordialement,


A.D.

[Flodelarab]

Bonjour,

En effet, je ne vois pas a priori de manière "simple" et pas trop "coûteuse en temps" de faire un tel test...

Ben moi, j'en vois une facile: toujours tirer un nombre strictement supérieur à son voisin de gauche ! Ainsi 5-2-1 n'existera pas.

[A. D.]

Merci pour le retour Flodelarab

En fait l'ordre n'est pas vraiment un problème (je peux trier facilement les éléments), c'était juste afin de préciser les différents cas possibles d'égalité de "combinaisons".

Ma question était plutôt, comment s'assurer que je n'aurais pas deux individus avec exactement la même sélection de NC éléments ? Et par extension, comment tester/vérifier que ce n'est pas le cas ?


Merci d'avance !


Cordialement,


A.D.

[A. D.]

Merci kolodz pour ta réponse

Je me demandais juste s'il n'y avait pas une manière plus "fine" ou "maligne" que de tester tous les "Set" entre eux.
Si je choisis de faire un tel test, tu penses qu'il est plus judicieux de le faire tout à la fin (car il est très peu probable d'avoir un nombre élevé de combinaisons dupliquées) ou bien au fur et à mesure du remplissage (mais cela implique un nombre de tests bien plus conséquent) ?

Merci de ton aide en tout cas !


Cordialement,


A.D.

[Flodelarab]

J'en remets une couche: la façon "maligne", comme tu dis, n'est pas de tester que la combinaison est unique mais de tirer une combinaison que tu sais unique. Personne n'a parler de trier en ordre croissant.

[kolodz]

Il faudrait que tu compare les "Set" un à un.
En fonction du langage que tu utilise cela est plus ou moins facilité. Par exemple en Java tu as l'interface Set qui dispose de la méthode equals(Object o). Celle-ci retourne vraie si :

Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set).

Tout les langages qui propose un minimum d'API standard propose un équivalant.

Il ne reste "plus" qu'à faire un boucle de vérification sur les différents set. Mais, un vrai random doit laisser ce genre possibilité. Enigma est tombé justement pour une bêtise de ce style ! (A savoir qu'une lettre ne pouvait pas être crypté entant qu'elle-même.)

Source :
http://docs.oracle.com/javase/7/docs...lang.Object%29