Sélection aléatoire pondérée avec et sans remplacement

En réponse à un défi de programmation, nous recherchons des algorithmes efficaces pour la sélection aléatoire pondérée à partir d'une liste, avec et sans remplacement.

Sélection pondérée avec remplacement

Une méthode efficace pour la sélection pondérée avec remplacement est la Méthode d'alias. Cette technique crée un ensemble de compartiments de taille égale pour chaque élément pondéré. En utilisant des opérations sur bits, nous pouvons indexer efficacement ces bacs sans recourir à la recherche binaire. Chaque compartiment stocke un pourcentage unique représentant la limite entre les éléments pondérés d'origine.

Prenons l'exemple de cinq éléments avec des poids égaux : (a, b, c, d, e).

Mise en œuvre de la méthode d'alias

1. Normaliser les poids : divisez chaque poids par le total pour obtenir une somme de 1,0.
2. Déterminez la plus petite puissance de 2 supérieure ou égale au nombre d'éléments (ici, 8).
3. Attribuez une partition vide à chaque élément.

4. Répétez les étapes suivantes jusqu'à ce que tous les poids soient distribués :

   • Placez autant d'éléments ayant le moins de poids restant dans une partition vide.
   • Si une partition n'est pas remplie, ajoutez l'élément restant le plus lourd.

Pour notre exemple, après plusieurs itérations, nous avons la partition suivante :

• p1 : {a, 1.0}
• p2 : {a, b, 0.6}

Sélection d'exécution

1. Générer un nombre aléatoire entre 0 et 1.
2. Déplacez le nombre aléatoire pour trouver l'index de partition.
3. Si la partition est divisée, utilisez la partie décimale du nombre décalé pour décider quel élément renvoyer.

Sélection pondérée sans remplacement

Alors que les algorithmes comme la méthode du réservoir pondéré existe pour une sélection non pondérée sans remplacement, ce problème reste non résolu.