java - 如何避免使用 java 随机函数重复和零？

Question

我有一个包含 100 个元素的数组，我想打印出 20 个随机元素而不重复或有零。

我已经成功地从 1000 个数字中随机打印出 20 个数字，但我无法阻止它打印出重复项和/或零。有什么帮助吗？!

这是代码:-

import java.util.Random;


public class MyClass {
    public static void main(String args[]) {
        int[] persons = new int[1000];
        int[] person  = new int[20];
        Random random = new Random();

        for (int i = 0; i < person.length; i++)
        {
            person[i] = random.nextInt(persons.length);
            System.out.println(person[i]);
        }
    }
}

Answer 1

_{这个问题可能会打破 APH 记录(每小时回答数)，第一个小时内有 8 个回答。通常，这是一个不好的迹象，但令人惊讶的是，我没有找到我希望将此问题重复的问题。}

不幸的是，大多数“简单”的答案在实践中可能有严重的缺陷。最重要的是，所提出的解决方案要么对某些设置效率低下，要么采用无法证明 Total Correctness 的技术。 - 即，可能无法证明算法会终止。这是指将随机数添加到 Set 并使用此 Set 跟踪不同元素数量的方法已被选中。因此，例如，在这段代码中

Set<Integer> set = new HashSet<Integer>();
Random random = new Random(0);  
while (set.size() < sampleSize) {
    set.add(min + rand.nextInt(max));
}

循环可能永远不会终止。您根本无法证明会选择 20 个不同的数字。 Random 实例可能会在第一次调用时返回 0。它可能会在第二次调用中返回 0。在第三个电话中.... you can never be sure.

---

当然，“在实践中”，循环通常迟早会终止，但这取决于参数:当要求在 0 到 10 之间选择 20 个不同的随机数时，它不会终止。这同样适用于类似的技术，例如

int[] ints = new Random(0).ints(0, 10).distinct().limit(20).toArray();

所以应该仔细检查参数，以确保它们在这方面是有效的。

---

经常以各种形式建议的另一个选项是在预先填充了可供选择的项目的列表上使用 Collections#shuffle。这可能适用于您的情况，该列表可能只有 100 或 1000 个元素。但是填充一个列表，比如说 100000000 个元素太耗费内存，洗牌这个列表太耗时。

---

一般来说，有一种相当通用的技术可以解决这个问题。它被称为 Reservoir Sampling .

_{(请注意，关于水库采样的实现存在一些问题，但似乎并未提出将其作为这项非常通用的任务的解决方案)}

这是 Java 中水库采样的实现。对于给定的样本大小和范围，它按升序返回所需范围内的(随机的、唯一的)整数集合:

/**
 * Creates a collection with the given size, containing random values 
 * between the given minimum value (inclusive) and maximum value
 * (exclusive). The resulting collection will contain the values
 * in ascending order. 
 *  
 * @param size The size of the returned collection
 * @param min The minimum value (inclusive)
 * @param max The maximum value (exclusive)
 * @param random The random number generator
 * @return The collection
 * @throws IllegalArgumentException If the requested size is larger than
 * the difference between the maximum value and the minimum value
 */
public static Collection<Integer> randomSample(
    int size, int min, int max, Random random)
{
    if (size > max - min)
    {
        throw new IllegalArgumentException(
            "Can not create a sample of size "+size+
            " with values between "+min+" and "+max);

    }
    Set<Integer> set = new LinkedHashSet<Integer>(size);
    int n = size;
    for (int i = 0; i < max - min; i++)
    {
        double d = (double) size / ((max - min) - i);
        if (random.nextDouble() < d)
        {
            set.add(i + min);
            n--;
        }
        if (n <= 0)
        {
            break;
        }
    }
    return set;
}        

_{(如果此实现有任何缺陷或不足，请在评论中给我留言)。}

这可以作为类似任务的构建 block 。例如，在您的情况下，您可以创建一个随机样本的索引，并使用它来选择所需的元素:

int persons[] = new int[1000];
int sample[]  = new int[20];
Collection<Integer> indices = randomSample(20, 0, 1000);
int n = 0;
for (Integer index : indices) 
{
    sample[n] = index;
    n++;
}

对于其他情况，您可能希望根据返回的索引创建一个列表并打乱该列表。但在这种情况下，只有(小的)样本需要打乱，而不是包含所有可能输入的(可能很大的)列表。