Выбор случайного элемента из набора - PullRequest
Новая
       93

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

167 голосов
/ 24 сентября 2008

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

Ответы [ 33 ]

0 голосов
/ 24 сентября 2008

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];
0 голосов
/ 11 ноября 2014

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

Object[] arr = set.toArray();

int v = (int) arr[rnd.nextInt(arr.length)];
0 голосов
/ 22 декабря 2013

Ради интереса я написал 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;
        }
    }
}
Страница:
...