algorithm - repetir - Seleccione k elementos aleatorios de una lista cuyos elementos tienen pesos

macro para generar numeros aleatorios excel

Question

La selección sin pesos (probabilidades iguales) está bellamente descrita here .

Me preguntaba si hay una manera de convertir este enfoque en uno ponderado.

También estoy interesado en otros enfoques también.

Actualización: muestreo sin reemplazo

Answer 1

Al presentar aquí una solución simple para escoger 1 artículo, puedes expandirlo fácilmente para k artículos (estilo Java):

double random = Math.random();
double sum = 0;
for (int i = 0; i < items.length; i++) {
    val = items[i];
    sum += val.getValue();
    if (sum > random) {
        selected = val;
        break;
    }
}

Answer 2

Aquí hay una implementación de Go de geodns :

package foo

import (
    "log"
    "math/rand"
)

type server struct {
    Weight int
    data   interface{}
}

func foo(servers []server) {
    // servers list is already sorted by the Weight attribute

    // number of items to pick
    max := 4

    result := make([]server, max)

    sum := 0
    for _, r := range servers {
        sum += r.Weight
    }

    for si := 0; si < max; si++ {
        n := rand.Intn(sum + 1)
        s := 0

        for i := range servers {
            s += int(servers[i].Weight)
            if s >= n {
                log.Println("Picked record", i, servers[i])
                sum -= servers[i].Weight
                result[si] = servers[i]

                // remove the server from the list
                servers = append(servers[:i], servers[i+1:]...)
                break
            }
        }
    }

    return result
}

Answer 3

En la pregunta a la que se vinculó, la solución de Kyle funcionaría con una generalización trivial. Escanee la lista y sume los pesos totales. Entonces la probabilidad de elegir un elemento debería ser:

1 - (1 - (# necesario / (peso a la izquierda))) / (peso en n). Después de visitar un nodo, reste su peso del total. Además, si necesita ny tiene n izquierda, debe detenerse explícitamente.

Puedes verificar que con todo teniendo peso 1, esto se simplifica a la solución de Kyle.

Editado: (tuvo que replantearse qué significaba el doble de posibilidades)

Answer 4

Esto hace exactamente eso con O (n) y sin uso de memoria en exceso. Creo que esta es una solución inteligente y eficiente fácil de transportar a cualquier idioma. Las primeras dos líneas son solo para completar los datos de muestra en Drupal.

function getNrandomGuysWithWeight($numitems){
  $q = db_query(''SELECT id, weight FROM theTableWithTheData'');
  $q = $q->fetchAll();

  $accum = 0;
  foreach($q as $r){
    $accum += $r->weight;
    $r->weight = $accum;
  }

  $out = array();

  while(count($out) < $numitems && count($q)){
    $n = rand(0,$accum);
    $lessaccum = NULL;
    $prevaccum = 0;
    $idxrm = 0;
    foreach($q as $i=>$r){
      if(($lessaccum == NULL) && ($n <= $r->weight)){
        $out[] = $r->id;
        $lessaccum = $r->weight- $prevaccum;
        $accum -= $lessaccum;
        $idxrm = $i;
      }else if($lessaccum){
        $r->weight -= $lessaccum;
      }
      $prevaccum = $r->weight;
    }
    unset($q[$idxrm]);
  }
  return $out;
}

Answer 5

He hecho esto en Ruby

https://github.com/fl00r/pickup

require ''pickup''
pond = {
  "selmon"  => 1,
  "carp" => 4,
  "crucian"  => 3,
  "herring" => 6,
  "sturgeon" => 8,
  "gudgeon" => 10,
  "minnow" => 20
}
pickup = Pickup.new(pond, uniq: true)
pickup.pick(3)
#=> [ "gudgeon", "herring", "minnow" ]
pickup.pick
#=> "herring"
pickup.pick
#=> "gudgeon"
pickup.pick
#=> "sturgeon"

Answer 6

He implementado un algoritmo similar a la idea de Jason Orendorff en Rust here . Mi versión también admite operaciones masivas: inserte y elimine (cuando desee eliminar un grupo de elementos dados por sus identificadores, no a través de la ruta de selección ponderada) de la estructura de datos en O(m + log n) tiempo donde m es el número de elementos para eliminar yn la cantidad de elementos almacenados.

Answer 7

Muestreo sin reemplazo con recursión: solución elegante y muy corta en c #

// cuántas formas podemos elegir 4 de 60 estudiantes, para que cada vez que elijamos diferentes 4

class Program
{
    static void Main(string[] args)
    {
        int group = 60;
        int studentsToChoose = 4;

        Console.WriteLine(FindNumberOfStudents(studentsToChoose, group));
    }

    private static int FindNumberOfStudents(int studentsToChoose, int group)
    {
        if (studentsToChoose == group || studentsToChoose == 0)
            return 1;

        return FindNumberOfStudents(studentsToChoose, group - 1) + FindNumberOfStudents(studentsToChoose - 1, group - 1);

    }
}

Answer 8

Sé que esta es una pregunta muy antigua, pero creo que hay un buen truco para hacerlo en O (n) tiempo si aplica un poco de matemáticas.

La distribución exponencial tiene dos propiedades muy útiles.

1. Dadas n muestras de diferentes distribuciones exponenciales con diferentes parámetros de velocidad, la probabilidad de que una muestra dada sea el mínimo es igual a su parámetro de velocidad dividido por la suma de todos los parámetros de velocidad.

2. Es "sin memoria". Entonces, si ya conoce el mínimo, entonces la probabilidad de que cualquiera de los elementos restantes sea de 2 ° a min es la misma que la probabilidad de que si se eliminaba el min verdadero (y nunca se generaba), ese elemento sería el nuevo min. Esto parece obvio, pero creo que debido a algunos problemas de probabilidad condicional, podría no ser cierto para otras distribuciones.

Usando el hecho 1, sabemos que la elección de un solo elemento se puede hacer generando estas muestras de distribución exponencial con un parámetro de velocidad igual al peso, y luego eligiendo el que tenga un valor mínimo.

Usando el hecho 2, sabemos que no tenemos que volver a generar las muestras exponenciales. En su lugar, solo genere uno para cada elemento y tome los elementos k con las muestras más bajas.

Encontrar la k más baja se puede hacer en O (n). Use el algoritmo Quickselect para encontrar el elemento k-ésimo, luego simplemente tome otro pase a través de todos los elementos y dé como resultado un valor inferior al k-ésimo.

Una nota útil: si no tiene acceso inmediato a una biblioteca para generar muestras de distribución exponencial, puede hacerlo fácilmente: -ln(rand())/weight

Answer 9

Si desea elegir x elementos de un conjunto ponderado sin reemplazo, de modo que los elementos se elijan con una probabilidad proporcional a sus ponderaciones:

import random

def weighted_choose_subset(weighted_set, count):
    """Return a random sample of count elements from a weighted set.

    weighted_set should be a sequence of tuples of the form 
    (item, weight), for example:  [(''a'', 1), (''b'', 2), (''c'', 3)]

    Each element from weighted_set shows up at most once in the
    result, and the relative likelihood of two particular elements
    showing up is equal to the ratio of their weights.

    This works as follows:

    1.) Line up the items along the number line from [0, the sum
    of all weights) such that each item occupies a segment of
    length equal to its weight.

    2.) Randomly pick a number "start" in the range [0, total
    weight / count).

    3.) Find all the points "start + n/count" (for all integers n
    such that the point is within our segments) and yield the set
    containing the items marked by those points.

    Note that this implementation may not return each possible
    subset.  For example, with the input ([(''a'': 1), (''b'': 1),
    (''c'': 1), (''d'': 1)], 2), it may only produce the sets [''a'',
    ''c''] and [''b'', ''d''], but it will do so such that the weights
    are respected.

    This implementation only works for nonnegative integral
    weights.  The highest weight in the input set must be less
    than the total weight divided by the count; otherwise it would
    be impossible to respect the weights while never returning
    that element more than once per invocation.
    """
    if count == 0:
        return []

    total_weight = 0
    max_weight = 0
    borders = []
    for item, weight in weighted_set:
        if weight < 0:
            raise RuntimeError("All weights must be positive integers")
        # Scale up weights so dividing total_weight / count doesn''t truncate:
        weight *= count
        total_weight += weight
        borders.append(total_weight)
        max_weight = max(max_weight, weight)

    step = int(total_weight / count)

    if max_weight > step:
        raise RuntimeError(
            "Each weight must be less than total weight / count")

    next_stop = random.randint(0, step - 1)

    results = []
    current = 0
    for i in range(count):
        while borders[current] <= next_stop:
            current += 1
        results.append(weighted_set[current][0])
        next_stop += step

    return results

Answer 10

Si desea generar grandes matrices de enteros aleatorios con reemplazo , puede usar la interpolación lineal por partes. Por ejemplo, usando NumPy / SciPy:

import numpy
import scipy.interpolate

def weighted_randint(weights, size=None):
    """Given an n-element vector of weights, randomly sample
    integers up to n with probabilities proportional to weights"""
    n = weights.size
    # normalize so that the weights sum to unity
    weights = weights / numpy.linalg.norm(weights, 1)
    # cumulative sum of weights
    cumulative_weights = weights.cumsum()
    # piecewise-linear interpolating function whose domain is
    # the unit interval and whose range is the integers up to n
    f = scipy.interpolate.interp1d(
            numpy.hstack((0.0, weights)),
            numpy.arange(n + 1), kind=''linear'')
    return f(numpy.random.random(size=size)).astype(int)

Esto no es efectivo si quiere muestrear sin reemplazo.

Answer 11

Si el muestreo es con reemplazo, use la técnica de selección de rueda de ruleta (a menudo utilizada en algoritmos genéticos):

1. ordenar los pesos
2. calcular los pesos acumulados
3. elige un número al azar en [0,1]*totalWeight
4. encuentre el intervalo en el cual este número cae
5. selecciona los elementos con el intervalo correspondiente
6. repetir k veces

Si el muestreo no tiene reemplazo, puede adaptar la técnica anterior eliminando el elemento seleccionado de la lista después de cada iteración, luego re-normalizando los pesos para que su suma sea 1 (función de distribución de probabilidad válida)

Answer 12

Usé un mapa asociativo (peso, objeto). por ejemplo:

{
(10,"low"),
(100,"mid"),
(10000,"large")
}

total=10110

busque un número aleatorio entre 0 y ''total'' e itere sobre las teclas hasta que este número encaje en un rango determinado.

Answer 13

Si el muestreo es con reemplazo, puede usar este algoritmo (implementado aquí en Python):

import random

items = [(10, "low"),
         (100, "mid"),
         (890, "large")]

def weighted_sample(items, n):
    total = float(sum(w for w, v in items))
    i = 0
    w, v = items[0]
    while n:
        x = total * (1 - random.random() ** (1.0 / n))
        total -= x
        while x > w:
            x -= w
            i += 1
            w, v = items[i]
        w -= x
        yield v
        n -= 1

Esto es O ( n + m ) donde m es el número de elementos.

¿Por qué funciona esto? Se basa en el siguiente algoritmo:

def n_random_numbers_decreasing(v, n):
    """Like reversed(sorted(v * random() for i in range(n))),
    but faster because we avoid sorting."""
    while n:
        v *= random.random() ** (1.0 / n)
        yield v
        n -= 1

La función weighted_sample es solo este algoritmo fusionado con un recorrido de la lista de items para seleccionar los elementos seleccionados por esos números aleatorios.

Esto a su vez funciona porque la probabilidad de que n números aleatorios 0 .. v todos sean menores que z es P = ( z / v ) ⁿ . Resuelve para z , y obtienes z = vP ^{1 / n} . Sustituyendo un número aleatorio para P elige el número más grande con la distribución correcta; y podemos simplemente repetir el proceso para seleccionar todos los otros números.

Si el muestreo no tiene reemplazo, puede colocar todos los elementos en un montón binario, donde cada nodo almacena en caché el total de los pesos de todos los elementos en ese subheap. La construcción del montón es O ( m ). Seleccionar un elemento aleatorio del montón, respetando los pesos, es O (log m ). La eliminación de ese elemento y la actualización de los totales en caché también es O (log m ). Entonces puede elegir n elementos en el tiempo O ( m + n log m ).

(Nota: "peso" significa que cada vez que se selecciona un elemento, las posibilidades restantes se eligen con una probabilidad proporcional a sus ponderaciones. No significa que los elementos aparecen en el resultado con una probabilidad proporcional a sus ponderaciones).

Aquí hay una implementación de eso, abundantemente comentada:

import random

class Node:
    # Each node in the heap has a weight, value, and total weight.
    # The total weight, self.tw, is self.w plus the weight of any children.
    __slots__ = [''w'', ''v'', ''tw'']
    def __init__(self, w, v, tw):
        self.w, self.v, self.tw = w, v, tw

def rws_heap(items):
    # h is the heap. It''s like a binary tree that lives in an array.
    # It has a Node for each pair in `items`. h[1] is the root. Each
    # other Node h[i] has a parent at h[i>>1]. Each node has up to 2
    # children, h[i<<1] and h[(i<<1)+1].  To get this nice simple
    # arithmetic, we have to leave h[0] vacant.
    h = [None]                          # leave h[0] vacant
    for w, v in items:
        h.append(Node(w, v, w))
    for i in range(len(h) - 1, 1, -1):  # total up the tws
        h[i>>1].tw += h[i].tw           # add h[i]''s total to its parent
    return h

def rws_heap_pop(h):
    gas = h[1].tw * random.random()     # start with a random amount of gas

    i = 1                     # start driving at the root
    while gas >= h[i].w:      # while we have enough gas to get past node i:
        gas -= h[i].w         #   drive past node i
        i <<= 1               #   move to first child
        if gas >= h[i].tw:    #   if we have enough gas:
            gas -= h[i].tw    #     drive past first child and descendants
            i += 1            #     move to second child
    w = h[i].w                # out of gas! h[i] is the selected node.
    v = h[i].v

    h[i].w = 0                # make sure this node isn''t chosen again
    while i:                  # fix up total weights
        h[i].tw -= w
        i >>= 1
    return v

def random_weighted_sample_no_replacement(items, n):
    heap = rws_heap(items)              # just make a heap...
    for i in range(n):
        yield rws_heap_pop(heap)        # and pop n items off it.