algoritmo para sistema de la selección de ganadores usando diferentes pesos

Question

Estoy tratando de diseñar un algoritmo que hace lo siguiente.

Entrada:

Tengo un juego de llaves (n total) que se asignan a conjunto de propiedades. Las propiedades contienen el peso para cada propiedad y el valor para la propiedad.

Salida:

identificar un conjunto de teclas que están calificados (k total) basado en el conjunto de propiedades y sus respectivos pesos y valores.

Además, los datos debe ser modificado como tal en cada ciclo de la elección de los ganadores de tal manera que las posibilidades de que alguien que no fue elegido sube en el siguiente ciclo (mientras que las posibilidades de que alguien que ha ganado sería como si estuvieran completamente nueva en el sistema).

Esperamos que el tema en cuestión es clara. Básicamente, el valor de la propiedad y el peso respectivo determinarían qué teclas son más propensos a ganar (un valor más alto, con un peso mayor que aumentaría la probabilidad de que la clave de ganar) y, finalmente, el resultado final será la elección de cada uno.

Cualquier entrada sobre cómo se puede hacer esto sería muy apreciado.

Gracias! - Azeem

Answer 1

Considere sus pesos como segmentos de una línea, con la longitud total de línea igual a la suma de los pesos. Escoja un número aleatorio uniforme entre 0 y esa longitud. El ganador es el candidato cuyo segmento el número cae en.

Eliminar que el ganador, y reducir la longitud total de acuerdo a ello. A continuación, repita el proceso con el resto de los candidatos hasta que haya elegido su k.

Después del ciclo, cambiar la escala de los perdedores a ocupar la mayor parte de la longitud original y volver a agregar los ganadores con el pequeño trozo restante se divide en partes iguales entre ellos.

Answer 2

un método no optimizado pero eficaz sería hacer una lista de todos los concursantes, pero índices append adicionales para contestest proporcional al peso.

pseudo está totalmente fuera de contexto de cualquier implementación real, pero debe hacerse una idea.

const int DEFAULT_WEIGHT = 1;
public List<Contestant> items = new List<Contestant>();
public List<Guid> LotteryPool = new List<int>();

public Contestant Roll()
{
     Random rnd = new Random();
     rnd.Seed = DateTime.Now.Ticks;

     // Generate LotteryPool
     foreach(Contestant item in items)
     {
              for(int i = 0; i < item.Weight; i++)
              {
                       LotteryPool.Add(item.Id);
              }

              item.Weight++;
     }

     // Find the contestant matching a random id from the pool.
     Contestant result = FindContestant(LotteryPool[rnd.Next(0, LotterPool.Count]);

     // apply the default weight the winner
     result.Weight = DEFAULT_WEIGHT;

     return result;
}