从集合中挑选一个随机元素

Question

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

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

使用a ArrayList和a HashMap:[element - > index] 快速解决Java问题.

动机:我需要一组具有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.(此外,这可以编译而无需添加额外的return语句.)

请注意,此代码(以及大多数其他答案)可以应用于任何集合,而不仅仅是Set.在通用方法形式中:

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)).[编辑:列表副本也是O(n)]

或者,您可以查找更符合您要求的另一个Set实现.Commons Collections 的ListOrderedSet看起来很有前途.

Answer 6

在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 7

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

Answer 8

这与接受的答案（Khoth）相同，但删除了不必要的变量size和i变量。

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

尽管消除了上述两个变量，但上述解决方案仍然是随机的，因为我们依赖于 random（从随机选择的索引开始）0在每次迭代中递减。

Answer 9

在Java 8中：

static <E> E getRandomSetElement(Set<E> set) {
    return set.stream().skip(new Random().nextInt(set.size())).findFirst().orElse(null);
}

Answer 10

Java 8+ 流：

    static <E> Optional<E> getRandomElement(Collection<E> collection) {
        return collection
                .stream()
                .skip(ThreadLocalRandom.current()
                .nextInt(collection.size()))
                .findAny();
    }

基于Joshua Bone的回答，但略有改动：

• 忽略 Streams 元素顺序以略微提高并行操作的性能
• 使用当前线程的 ThreadLocalRandom
• 接受任何集合类型作为输入
• 返回提供的Optional而不是null