Wybierz K losowe elementy z listy, których elementy mają wagi

Jeśli próbkowanie jest zastępowane, możesz użyć tego algorytmu (zaimplementowanego tutaj w Pythonie):

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

To jest O (n + m) gdzie m jest liczbą pozycji.

Dlaczego to działa? opiera się na następującym algorytmie:

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

Funkcja weighted_sample jest właśnie tym algorytmem połączonym z krokiem listy items, aby wybrać elementy wybrane przez te losowe liczby.

Jeżeli pobieranie próbek jest bez replacement, możesz umieścić wszystkie elementy w stercie binarnej, gdzie każdy węzeł buforuje całkowitą wagę wszystkich elementów w tym nagłówku. Budowa sterty to O (m ). Wybór losowego elementu ze sterty, z uwzględnieniem wag, wynosi O (log m ). Usunięcie tego elementu i aktualizacja sumy w pamięci podręcznej jest również o (log m ). Więc możesz wybrać N elementy w O ( m + N log M) Czas.

(Uwaga: "waga" tutaj oznacza, że każdy kiedy element jest wybrany, pozostałe możliwości są wybierane z prawdopodobieństwem proporcjonalnym do ich wagi. Nie oznacza to, że elementy pojawiają się na wyjściu z prawdopodobieństwem proporcjonalnym do ich wagi.)

Oto implementacja tego, obszernie skomentował:

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.

Jeśli próbkowanie jest zastępowane, użyj techniki wyboru koła ruletki (często stosowanej w algorytmach genetycznych):

1. sortowanie wag
2. Oblicz wagę skumulowaną
3. Wybierz losową liczbę w [0,1]*totalWeight
4. znajdź przedział, w którym ta liczba spada do
5. wybierz elementy z odpowiednim interwałem
6. powtórz k razy

Jeśli próbkowanie jest bez wymiany, można dostosować powyższe technika poprzez usunięcie wybranego elementu z listy po każdej iteracji, a następnie ponowną normalizację wag tak, aby ich suma wynosiła 1 (ważna funkcja rozkładu prawdopodobieństwa)

I ' ve done this in 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"

Jeśli chcesz wygenerować duże tablice losowych liczb całkowitych z zamiennikiem , możesz użyć fragmentarycznej interpolacji liniowej. Na przykład, używając 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)

Nie jest to skuteczne, jeśli chcesz pobrać próbkę bez wymiany.

Oto implementacja Go z 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
}

Jeśli chcesz wybrać x elementów ze zbioru ważonego bez zastępowania tak, że elementy są wybierane z prawdopodobieństwem proporcjonalnym do ich wagi:

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

W pytaniu, z którym się łączyłeś, rozwiązanie Kyle ' a będzie działać z trywialnym uogólnieniem. Zeskanuj listę i zsumuj całkowitą wagę. Wtedy prawdopodobieństwo wyboru elementu powinno wynosić:

1 - (1 - (#potrzebne / (waga po lewej))) / (waga przy n). Po odwiedzeniu węzła odjmij jego wagę od sumy. Ponadto, jeśli potrzebujesz n i masz N w lewo, musisz przestać wyraźnie.

Możesz sprawdzić, że wszystko ma wagę 1, to upraszcza rozwiązanie kyle ' a.

Edytował: (had aby przemyśleć, co dwa razy bardziej prawdopodobne oznacza)

Ten robi dokładnie to Z O (n) i bez nadmiernego zużycia pamięci. Uważam, że jest to sprytne i wydajne rozwiązanie łatwe do przeniesienia na dowolny język. Pierwsze dwie linie służą tylko do wypełnienia przykładowych danych w Drupalu.

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;
}

Umieszczam tutaj proste rozwiązanie do wybierania 1 elementu, można go łatwo rozbudować o elementy K (styl 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;
    }
}

Zaimplementowałem algorytm podobny do idei Jasona Orendorffa w Rust Tutaj . Moja wersja dodatkowo obsługuje operacje zbiorcze: insert I remove (jeśli chcesz usunąć kilka elementów podanych przez ich ID, a nie przez ważoną ścieżkę wyboru) ze struktury danych w czasie O(m + log n), gdzie m oznacza liczbę elementów do usunięcia, a n liczbę elementów w przechowywanych.

Sampling wihout replacement with recursion-eleganckie i bardzo krótkie rozwiązanie w c#

/ / na ile sposobów możemy wybrać 4 z 60 uczniów, tak że za każdym razem wybieramy inne 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);

    }
}

Użyłem mapy asocjacyjnej (waga,obiekt). na przykład:

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

total=10110

Zerknij na losową liczbę od 0 do 'total' i powtarzaj nad kluczami, aż ta liczba zmieści się w danym zakresie.