Выбор случайного элемента из набора

Question

Как выбрать случайный элемент из набора? Я особенно заинтересован в выборе случайного элемента из HashSet или LinkedHashSet в Java. Решения для других языков также приветствуются.

Answer 1

C ++. Это должно быть достаточно быстро, так как оно не требует итерации по всему набору или сортировки. Это должно работать "из коробки" с большинством современных компиляторов, если они поддерживают tr1 . Если нет, возможно, вам придется использовать Boost.

Документы Boost здесь полезны, чтобы объяснить это, даже если вы не используете Boost.

Хитрость заключается в том, чтобы использовать тот факт, что данные были разделены на сегменты, и быстро идентифицировать случайно выбранный интервал (с соответствующей вероятностью).

//#include <boost/unordered_set.hpp>  
//using namespace boost;
#include <tr1/unordered_set>
using namespace std::tr1;
#include <iostream>
#include <stdlib.h>
#include <assert.h>
using namespace std;

int main() {
  unordered_set<int> u;
  u.max_load_factor(40);
  for (int i=0; i<40; i++) {
    u.insert(i);
    cout << ' ' << i;
  }
  cout << endl;
  cout << "Number of buckets: " << u.bucket_count() << endl;

  for(size_t b=0; b<u.bucket_count(); b++)
    cout << "Bucket " << b << " has " << u.bucket_size(b) << " elements. " << endl;

  for(size_t i=0; i<20; i++) {
    size_t x = rand() % u.size();
    cout << "we'll quickly get the " << x << "th item in the unordered set. ";
    size_t b;
    for(b=0; b<u.bucket_count(); b++) {
      if(x < u.bucket_size(b)) {
        break;
      } else
        x -= u.bucket_size(b);
    }
    cout << "it'll be in the " << b << "th bucket at offset " << x << ". ";
    unordered_set<int>::const_local_iterator l = u.begin(b);
    while(x>0) {
      l++;
      assert(l!=u.end(b));
      x--;
    }
    cout << "random item is " << *l << ". ";
    cout << endl;
  }
}

Answer 2

Значок имеет тип набора и оператор случайного элемента, унарный "?", Поэтому выражение

? set( [1, 2, 3, 4, 5] )

выдаст случайное число от 1 до 5.

Случайное начальное число инициализируется равным 0 при запуске программы, поэтому для получения разных результатов при каждом запуске используется randomize()

Answer 3

К сожалению, это невозможно сделать эффективно (лучше, чем O (n)) ни в одном из контейнеров набора стандартной библиотеки.

Это странно, поскольку очень легко добавить случайную функцию выбора к хэш-наборам, а также к двоичным наборам. В не разреженном хэш-наборе вы можете использовать случайные записи, пока не получите удар. Для двоичного дерева вы можете выбрать случайным образом между левым или правым поддеревом, с максимумом O (log2) шагов. Я реализовал демо-версию ниже:

import random

class Node:
    def __init__(self, object):
        self.object = object
        self.value = hash(object)
        self.size = 1
        self.a = self.b = None

class RandomSet:
    def __init__(self):
        self.top = None

    def add(self, object):
        """ Add any hashable object to the set.
            Notice: In this simple implementation you shouldn't add two
                    identical items. """
        new = Node(object)
        if not self.top: self.top = new
        else: self._recursiveAdd(self.top, new)
    def _recursiveAdd(self, top, new):
        top.size += 1
        if new.value < top.value:
            if not top.a: top.a = new
            else: self._recursiveAdd(top.a, new)
        else:
            if not top.b: top.b = new
            else: self._recursiveAdd(top.b, new)

    def pickRandom(self):
        """ Pick a random item in O(log2) time.
            Does a maximum of O(log2) calls to random as well. """
        return self._recursivePickRandom(self.top)
    def _recursivePickRandom(self, top):
        r = random.randrange(top.size)
        if r == 0: return top.object
        elif top.a and r <= top.a.size: return self._recursivePickRandom(top.a)
        return self._recursivePickRandom(top.b)

if __name__ == '__main__':
    s = RandomSet()
    for i in [5,3,7,1,4,6,9,2,8,0]:
        s.add(i)

    dists = [0]*10
    for i in xrange(10000):
        dists[s.pickRandom()] += 1
    print dists

Я получил [995, 975, 971, 995, 1057, 1004, 966, 1052, 984, 1001] в качестве выхода, поэтому швы распределения хорошие.

Я боролся с той же самой проблемой для себя, и я еще не решил, стоит ли выигрыш в производительности этого более эффективного выбора, который стоит затрат на использование коллекции на основе Python. Конечно, я мог бы уточнить это и перевести на C, но для меня это слишком много сегодня:)

Answer 4

Разве вы не можете просто получить размер / длину набора / массива, сгенерировать случайное число от 0 до размера / длины, а затем вызвать элемент, индекс которого совпадает с этим числом? Я уверен, что в HashSet есть метод .size ().

в псевдокоде -

function randFromSet(target){
 var targetLength:uint = target.length()
 var randomIndex:uint = random(0,targetLength);
 return target[randomIndex];
}

Answer 5

PHP, предполагая, что "set" является массивом:

$foo = array("alpha", "bravo", "charlie");
$index = array_rand($foo);
$val = $foo[$index];

Функции Mersenne Twister лучше, но в PHP нет эквивалента MT для array_rand.

Answer 6

In lisp

(defun pick-random (set)
       (nth (random (length set)) set))

Answer 7

Решение Javascript;)

function choose (set) {
    return set[Math.floor(Math.random() * set.length)];
}

var set  = [1, 2, 3, 4], rand = choose (set);

Или альтернативно:

Array.prototype.choose = function () {
    return this[Math.floor(Math.random() * this.length)];
};

[1, 2, 3, 4].choose();

Answer 8

В Mathematica:

a = {1, 2, 3, 4, 5}

a[[ ⌈ Length[a] Random[] ⌉ ]]

Или, в последних версиях, просто:

RandomChoice[a]

---

Это получило отрицательное голосование, возможно, из-за отсутствия объяснения, поэтому вот один из них:

Random[] генерирует псевдослучайное число с плавающей точкой между 0 и 1. Это умножается на длину списка, а затем функция потолка используется для округления до следующего целого числа. Этот индекс затем извлекается из a.

Поскольку функциональность хеш-таблицы часто выполняется с помощью правил в Mathematica, а правила хранятся в списках, можно использовать:

a = {"Badger" -> 5, "Bird" -> 1, "Fox" -> 3, "Frog" -> 2, "Wolf" -> 4};

Answer 9

In C #

        Random random = new Random((int)DateTime.Now.Ticks);

        OrderedDictionary od = new OrderedDictionary();

        od.Add("abc", 1);
        od.Add("def", 2);
        od.Add("ghi", 3);
        od.Add("jkl", 4);


        int randomIndex = random.Next(od.Count);

        Console.WriteLine(od[randomIndex]);

        // Can access via index or key value:
        Console.WriteLine(od[1]);
        Console.WriteLine(od["def"]);

Answer 10

Как насчет

public static <A> A getRandomElement(Collection<A> c, Random r) {
  return new ArrayList<A>(c).get(r.nextInt(c.size()));
}