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

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

В некотором роде Знаете ли вы:

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

Answer 3

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

Мотивация: мне нужен был набор предметов со свойствами 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 4

Это быстрее, чем цикл for-each в принятом ответе:

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

Конструкция for-each вызывает 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 5

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

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

Answer 6

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

Answer 7

На 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 8

Clojure решение:

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

Answer 9

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

Answer 10

Perl 5

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

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