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

Question

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

Answer 1

int size = myHashSet.size(); 
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this 
int i = 0; 
for(Object obj : myhashSet) 
{ 
    if (i == item) 
     return obj; 
    i++; 
} 

Answer 2

Поскольку вы сказали, "Решения для других языков также приветствуется", вот версия для Python:

>>> import random 
>>> random.choice([1,2,3,4,5,6]) 
3 
>>> random.choice([1,2,3,4,5,6]) 
4 

Answer 3

В Java:

Set<Integer> set = new LinkedHashSet<Integer>(3); 
set.add(1); 
set.add(2); 
set.add(3); 

Random rand = new Random(System.currentTimeMillis()); 
int[] setArray = (int[]) set.toArray(); 
for (int i = 0; i < 10; ++i) { 
    System.out.println(setArray[rand.nextInt(set.size())]); 
} 

Answer 4

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

В psuedocode -

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

Answer 5

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

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

Функции Мерсенна Twister лучше, но нет MT эквивалент array_rand в PHP.

Answer 6

PHP, используя MT:

$items_array = array("alpha", "bravo", "charlie"); 
$last_pos = count($items_array) - 1; 
$random_pos = mt_rand(0, $last_pos); 
$random_item = $items_array[$random_pos]; 

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

Несколько связанных Знаете ли вы:

Есть полезные методы в java.util.Collections для перетасовки целых коллекций: Collections.shuffle(List<?>) и Collections.shuffle(List<?> list, Random rnd).

Answer 9

Perl 5

@hash_keys = (keys %hash); 
$rand = int(rand(@hash_keys)); 
print $hash{$hash_keys[$rand]}; 

Вот один из способов сделать это.

Answer 10

Icon имеет тип набора и оператор случайного элемента, унарный «?», Так что выражение

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

будет производить случайное число между 1 и 5.

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

Answer 11

В 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 12

В шепелявила

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

Answer 13

Если вы хотите сделать это на Java, вам следует рассмотреть возможность копирования элементов в какую-то коллекцию произвольного доступа (например, ArrayList). Поскольку, если ваш набор невелик, доступ к выбранному элементу будет дорогим (O (n) вместо O (1)). [ed: list copy также O (n)]

В качестве альтернативы вы можете искать другую реализацию Set, которая более точно соответствует вашим требованиям. ListOrderedSet из Commons Collections выглядит многообещающим.

Answer 14

Clojure решение:

(defn pick-random [set] (let [sq (seq set)] (nth sq (rand-int (count sq))))) 

Answer 15

К сожалению, это не может быть сделано эффективно (лучше, чем 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 16

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

Boost docs полезны здесь, чтобы объяснить это, даже если вы не используете 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 17

после прочтения этой нити, лучше я мог бы написать это:

static Random random = new Random(System.currentTimeMillis()); 
public static <T> T randomChoice(T[] choices) 
{ 
    int index = random.nextInt(choices.length); 
    return choices[index]; 
} 

Answer 18

Быстрое решение для Java с использованием ArrayList и HashMap: [элемент -> индекс].

Мотивация: Мне нужен был набор предметов с RandomAccess свойствами, особенно для выбора случайного предмета из набора (см. Метод pollRandom). Случайная навигация в двоичном дереве неточна: деревья не идеально сбалансированы, что не приведет к равномерному распределению.

public class RandomSet<E> extends AbstractSet<E> { 

    List<E> dta = new ArrayList<E>(); 
    Map<E, Integer> idx = new HashMap<E, Integer>(); 

    public RandomSet() { 
    } 

    public RandomSet(Collection<E> items) { 
     for (E item : items) { 
      idx.put(item, dta.size()); 
      dta.add(item); 
     } 
    } 

    @Override 
    public boolean add(E item) { 
     if (idx.containsKey(item)) { 
      return false; 
     } 
     idx.put(item, dta.size()); 
     dta.add(item); 
     return true; 
    } 

    /** 
    * Override element at position <code>id</code> with last element. 
    * @param id 
    */ 
    public E removeAt(int id) { 
     if (id >= dta.size()) { 
      return null; 
     } 
     E res = dta.get(id); 
     idx.remove(res); 
     E last = dta.remove(dta.size() - 1); 
     // skip filling the hole if last is removed 
     if (id < dta.size()) { 
      idx.put(last, id); 
      dta.set(id, last); 
     } 
     return res; 
    } 

    @Override 
    public boolean remove(Object item) { 
     @SuppressWarnings(value = "element-type-mismatch") 
     Integer id = idx.get(item); 
     if (id == null) { 
      return false; 
     } 
     removeAt(id); 
     return true; 
    } 

    public E get(int i) { 
     return dta.get(i); 
    } 

    public E pollRandom(Random rnd) { 
     if (dta.isEmpty()) { 
      return null; 
     } 
     int id = rnd.nextInt(dta.size()); 
     return removeAt(id); 
    } 

    @Override 
    public int size() { 
     return dta.size(); 
    } 

    @Override 
    public Iterator<E> iterator() { 
     return dta.iterator(); 
    } 
} 

Answer 19

В 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 20

List asList = new ArrayList(mySet); 
Collections.shuffle(asList); 
return asList.get(0); 

Answer 21

Как насчет

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

Answer 22

Для удовольствия я написал RandomHashSet на основе выборки отбраковки. Это немного взломанно, так как HashMap не позволяет нам напрямую обращаться к его таблице, но он должен работать нормально.

В нем не используется дополнительная память, а время поиска O (1) амортизируется. (Потому что java HashTable плотен).

class RandomHashSet<V> extends AbstractSet<V> { 
    private Map<Object,V> map = new HashMap<>(); 
    public boolean add(V v) { 
     return map.put(new WrapKey<V>(v),v) == null; 
    } 
    @Override 
    public Iterator<V> iterator() { 
     return new Iterator<V>() { 
      RandKey key = new RandKey(); 
      @Override public boolean hasNext() { 
       return true; 
      } 
      @Override public V next() { 
       while (true) { 
        key.next(); 
        V v = map.get(key); 
        if (v != null) 
         return v; 
       } 
      } 
      @Override public void remove() { 
       throw new NotImplementedException(); 
      } 
     }; 
    } 
    @Override 
    public int size() { 
     return map.size(); 
    } 
    static class WrapKey<V> { 
     private V v; 
     WrapKey(V v) { 
      this.v = v; 
     } 
     @Override public int hashCode() { 
      return v.hashCode(); 
     } 
     @Override public boolean equals(Object o) { 
      if (o instanceof RandKey) 
       return true; 
      return v.equals(o); 
     } 
    } 
    static class RandKey { 
     private Random rand = new Random(); 
     int key = rand.nextInt(); 
     public void next() { 
      key = rand.nextInt(); 
     } 
     @Override public int hashCode() { 
      return key; 
     } 
     @Override public boolean equals(Object o) { 
      return true; 
     } 
    } 
} 

Answer 23

Это быстрее, чем для-каждого цикла в принятом ответе:

int index = rand.nextInt(set.size()); 
Iterator<Object> iter = set.iterator(); 
for (int i = 0; i < index; i++) { 
    iter.next(); 
} 
return iter.next(); 

для-каждая конструкция требует Iterator.hasNext() на каждом цикле, но так как index < set.size(), что проверка не нужна над головой. Я видел повышение скорости на 10-20%, но YMMV. (Кроме того, это компиляция без необходимости добавлять дополнительный оператор возврата.)

Обратите внимание, что этот код (и большинство других ответов) может применяться к любой коллекции, а не только к набору. В общей форме метода:

public static <E> E choice(Collection<? extends E> coll, Random rand) { 
    if (coll.size() == 0) { 
     return null; // or throw IAE, if you prefer 
    } 

    int index = rand.nextInt(coll.size()); 
    if (coll instanceof List) { // optimization 
     return ((List<? extends E>) coll).get(index); 
    } else { 
     Iterator<? extends E> iter = coll.iterator(); 
     for (int i = 0; i < index; i++) { 
      iter.next(); 
     } 
     return iter.next(); 
    } 
} 

Answer 24

вы также можете передать набор для использования массива массива будет, вероятно, работать на малых масштабах я вижу цикл в наиболее голосовавшем ответе является O (N) равно

Object[] arr = set.toArray(); 

int v = (int) arr[rnd.nextInt(arr.length)]; 

Answer 25

Это совпадает с принятым ответом (Khoth), но с ненужными size и i переменными удалены.

int random = new Random().nextInt(myhashSet.size()); 
    for(Object obj : myhashSet) { 
     if (random-- == 0) { 
      return obj; 
     } 
    } 

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

Answer 26

Решение выше говорит в терминах задержки, но не гарантирует равную вероятность выбора каждого выбранного индекса.
Если это необходимо учитывать, попробуйте отбор проб коллектора.http://en.wikipedia.org/wiki/Reservoir_sampling.
Collections.shuffle() (как предложено несколькими) использует один такой алгоритм.

Answer 27

Если вы действительно хотите выбрать «любой» объект из Set, без каких-либо гарантий по случайности, проще всего взять первый, возвращенный итератором.

Set<Integer> s = ... 
    Iterator<Integer> it = s.iterator(); 
    if(it.hasNext()){ 
     Integer i = it.next(); 
     // i is a "random" object from set 
    } 

Answer 28

Самый простой с Java 8 является:

outbound.stream().skip(n % outbound.size()).findFirst().get() 

, где n это случайное число. Конечно, он имеет меньшую производительность, чем при использовании for(elem: Col)

Answer 29

Общее решение, использующее ответ Khoth в качестве отправной точки.

/** 
* @param set a Set in which to look for a random element 
* @param <T> generic type of the Set elements 
* @return a random element in the Set or null if the set is empty 
*/ 
public <T> T randomElement(Set<T> set) { 
    int size = set.size(); 
    int item = random.nextInt(size); 
    int i = 0; 
    for (T obj : set) { 
     if (i == item) { 
      return obj; 
     } 
     i++; 
    } 
    return null; 
} 

Answer 30

Если заданный размер невелик, то с помощью массивов это можно сделать.

int random; 
HashSet someSet; 
<Type>[] randData; 
random = new Random(System.currentTimeMillis).nextInt(someSet.size()); 
randData = someSet.toArray(); 
<Type> sResult = randData[random]; 

Answer 31

С Guava мы можем сделать немного лучше, чем ответ Khoth в:

public static E random(Set<E> set) { 
    int index = random.nextInt(set.size(); 
    if (set instanceof ImmutableSet) { 
    // ImmutableSet.asList() is O(1), as is .get() on the returned list 
    return set.asList().get(index); 
    } 
    return Iterables.get(set, index); 
} 

Answer 32

Просто хочу, чтобы оставить это здесь:

random.choice(your_set) 

не против змея.

Answer 33

Если вы не против 3-й библиотеки партии, то Utils библиотека имеет IterableUtils, что имеет метод randomFrom (Iterable итерации), которая будет принимать набор и возвращает случайный элемент из него

Set<Object> set = new HashSet<>(); 
set.add(...); 
... 
Object random = IterableUtils.randomFrom(set); 

It находится в Центральном репозитории Maven по адресу:

<dependency> 
    <groupId>com.github.rkumsher</groupId> 
    <artifactId>utils</artifactId> 
    <version>1.0</version> 
</dependency>