Algorithme de tirage avec équilibre ?

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.

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

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.

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.

Bonjour,

Citation:

---

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.

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 :

Citation:

---

Envoyé par Javadoc

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

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.

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 ! :D


Cordialement,


A.D.

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.

Le plus judicieux selon moi est de le faire à la fin dans une méthode séparé, pour bien séparer ce test du reste.
Il se ra plu simple à enlever après coups. Et ton nombre de tirage n'implique pas un grand nombre de calcule. Au pire, va perdre un peu de temps genre 200ms ? Ce n'est pas forcement ta priorité. L'optimisation est toujours à voir après coup.

Cordialement,
Patrick Kolodziejczyk.

Merci pour vos réponses :)

J'ai ajouté un test en toute fin d'algo qui va rechercher les potentielles "combinaisons doublons" et remplacer, pour chaque doublon, un seul élément de cette combinaison par un des éléments les moins représentés, puis re-tester l'unicité jusqu'à ce que ce soit ok (où qu'on ait fait trop de tests).
Mais c'est vrai qu'a priori, vu les grandeurs en jeu ici, il risque peu d'y avoir vraiment beaucoup de "combinaisons doublons", et pour les cas de tests que j'ai réalisés pour le moment, cela ne rallonge effectivement pas vraiment le temps de calcul.

@Flodelarab: Merci de ta remarque, mais c'est justement un peu ma problématique. Dans ce cas, que recommanderais-tu pour "tirer une combinaison que tu sais unique" ? J'ai du mal à saisir où tu veux en venir... Merci d'avance !


[EDIT]

Autre question : dans une telle configuration, si j'utilise mon plan d'expériences ainsi créé pour présenter NC éléments (parmis les NE possibles) à chaque individu et leur demande de donner leur avis sur chaque élément vu (par exemple avec une échelle en 3 points), comment faire pour évaluer la "qualité" de l'information que je vais récolter ? Y a-t-il un indicateur particulier qui soit utilisable dans un tel cas (j'imagine que cela dépend aussi du type d'analyse qu'on souhaite réaliser ensuite ? pour le moment je n'ai rien de précis en tête si ce n'est un "bête" classement...) ?
Egalement, dans la configuration que j'envisageais dans mon exemple, je m'assurais de prendre pour NE, NC et NI des valeurs telles que chaque élément (parmis les NE possibles) est vu au minimum Nexpo=50 fois sur l'ensemble des individus. Comment évaluer ce choix ou encore l'influence de l'augmentation/diminution de ce paramètre (Nexpo) ?

Merci d'avance ! :)


Cordialement,


A.D.