Выберите k случайных элементов из списка, чьи элементы имеют веса - PullRequest
Новая
       83

Выберите k случайных элементов из списка, чьи элементы имеют веса

67 голосов
/ 26 января 2010

Выбор без каких-либо весов (равных вероятностей) прекрасно описан здесь .

Мне было интересно, есть ли способ преобразовать этот подход во взвешенный.

Меня также интересуют и другие подходы.

Обновление: выборка без замена

Ответы [ 14 ]

0 голосов
/ 29 января 2014

Я выкладываю здесь простое решение для выбора 1 элемента, вы можете легко расширить его для k элементов (стиль 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;
    }
}
0 голосов
/ 15 августа 2013

Этот делает именно это с O (n) и без лишнего использования памяти.Я считаю, что это умное и эффективное решение, которое легко перенести на любой язык.Первые две строки предназначены только для заполнения примеров данных в 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;
}
0 голосов
/ 26 января 2010

В вопросе, с которым вы связаны, решение Кайла будет работать с тривиальным обобщением. Сканирование списка и суммирование общего веса. Тогда вероятность выбора элемента должна быть:

1 - (1 - (# необходимо / (вес остался))) / (вес при n). После посещения узла вычтите его вес из общего количества. Кроме того, если вам нужно n и у вас осталось n, вы должны явно остановиться.

Вы можете проверить, что со всем, имеющим вес 1, это упрощает решение Кайла.

Отредактировано: (пришлось переосмыслить, что означает в два раза больше вероятности)

0 голосов
/ 26 января 2010

Я использовал ассоциативную карту (вес, объект). например: 

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

total=10110

посмотреть случайное число от 0 до «итого» и перебирать ключи до тех пор, пока это число не окажется в заданном диапазоне.

Страница:
...