如何从集合中随机选取一个元素? 我特别感兴趣的是从a中随机选取一个元素 Java中的HashSet或LinkedHashSet。 也欢迎其他语言的解决方案。


当前回答

Java 8最简单的方法是:

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

其中n是一个随机整数。当然,它的性能不如使用for(elem: Col)

其他回答

上述解决方案从延迟的角度讲,但不能保证每个索引被选中的概率相等。 如果需要考虑这一点,可以尝试储层取样。http://en.wikipedia.org/wiki/Reservoir_sampling。Collections.shuffle()(正如少数人建议的那样)使用这样的算法。

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

如果你真的只想从Set中选择“任意”对象,而不保证随机性,最简单的方法是使用迭代器返回的第一个对象。

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

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();
    }
}

以霍斯的答案为起点的通用解决方案。

/**
 * @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;
}