# 从固定人口长度生成随机唯一数字的问题

go评论135阅读模式

Problem to generate random unique numbers from fixed population length

# 问题

Here's the translation of the code-related portion:

1轮：

List result = new ArrayList(sample);

int perm[] = new int[population]

public List generateRandomNumbers(int population, Set setListStringSeen, int sample)
{
for (int i = 0; i < sample; i++)
{
// 生成在 i 和 population-i 之间的随机整数
k = i + (int) (Math.random() * (population - i));

`````` if(setListStringSeen.contains(k))
{
// 这里的问题是：当我在这里检查，如果新生成的数字
// 已经被看到，我需要再次生成一个新数字。但在这种情况下，
// 下一个数字还需要再次检查，因为它也可能已经被看到。
// 如何结束这个检查循环呢？

k = i + (int) (Math.random() * (population - i));

if(setListStringSeen.contains(k))
{
System.out.println("我们之前已经选择过这个数字");
}

}

int t = perm[k];
perm[k] = perm[i];
perm[i] = t;
``````

}

for (int i = 0; i < sample; i++)
{
}

``````在1轮结束时，将生成的所有数字添加到HashSet中：
``````

return result;
}

I have a problem here which is: I need to generate random numbers given a fixed length, and every time I generate those numbers, I need to check if it was already seen or not.

Example: my fixed population size is 2.000.000. So, for example, in the first round of my algorithm, my sample size is 400.000. I need to generate 400.000 over 2.000.000. After generating those random numbers, I save them in a HashSet.

In a second rand of my algorithm, let's say I want to generate 20.000 random numbers, but I need to check with those 20.000 numbers was already seen or not by looking at the HashSet (which contains the 400.000 initial numbers from the 1 round).

This is what I got so far:

``````1 round:
population size: 2.000.000
sample: 400.000
List&lt;Integer&gt; result = new ArrayList&lt;Integer&gt;(sample);

I save the numbers in a variable called perm[],so :
int perm[] = new int[population]

public List&lt;Integer&gt; generateRandomNumbers (int population, Set&lt;Integer&gt; setListStringSeen, int sample)
{
for (int i = 0; i &lt; sample; i++)
{
// random integer between i and population-i
k = i + (int) (Math.random() * (population - i));

if(setListStringSeen.contains(k))
{
// the problem here is: when I check here and if the newly generated number
// was already see, I need to generate again a new number. But in this case,
// the next number need to be checked again, because it could be seen too.
// how can I end up this loop of checking?

k = i + (int) (Math.random() * (population - i));

if(setListStringSeen.contains(k))
{
System.out.println(&quot;we&#39;ve choose this number once before&quot;);
}

}

int t = perm[k];
perm[k] = perm[i];
perm[i] = t;

}

for (int i = 0; i &lt; sample; i++)
{
}

at the end of 1 round, I add all the generated numbers in a HashSet:

return result;

}
``````

Now let's go to the 2 round:
let's say we want to generate 20.000 new numbers:
what I want is, check if those numbers the will be generated (in the second round) was already seen before by checking the Hashset variable. Any idea on how to do it?

# 答案1

``````while (set.add(random.nextInt(2000000)) != true);
``````

``````List<Integer> sample = IntStream.rangeClosed(0, 2000000)
.boxed().collect(Collectors.toList());
Collections.shuffle(sample);
``````

You can use:

``````while (set.add(random.nextInt(2000000)) != true);
``````

to add it to the set and it will add it uniquely

Another option could be to create a total sample set in class scope of 2mil and then shuffle it and just pull from the list so you never get the same number twice:

``````List&lt;Integer&gt; sample = IntStream.rangeClosed(0, 2000000)
.boxed().collect(Collectors.toList());
Collections.shuffle(sample)
``````

# 答案2

``````// 从0到总体大小获取整数列表
final List<Integer> integers = Stream.iterate(0, n -> n + 1)
.limit(population)
.collect(Collectors.toList());
// 整数列表将包含[0, 1, 2, .... n]

// 然后对它们进行洗牌
Collections.shuffle(integers);
// 整数列表将会类似于[3, 66, 44, .... n]的随机顺序
``````

You should generate the random numbers beforehand, so you are certain they are not repeated.

An easy way of doing this is to obtain a list of integers and then shuffle it.

For example:

``````// Obtain a list of integers from 0 to the size of population - 1
final List&lt;Integer&gt; integers = Stream.iterate(0, n -&gt; n + 1)
.limit(population)
.collect(Collectors.toList());
// integers will have have [0, 1, 2, .... n]

// Then shuffle them
Collections.shuffle(integers);
// integers will have have something like [3, 66, 44, .... n] randomly
``````

# 答案3

``````public static void main(String args[]) {
Random rand = new Random();

int populationSize = 20;
int sampleSizeFirstRound = 10;

Set<Integer> sample = rand.ints(1, populationSize)
.distinct()
.limit(sampleSizeFirstRound)
.boxed()
.collect(Collectors.toSet());

int sampleSizeSecondRound = 6;
Set<Integer> sampleSecondRound = rand.ints(1, populationSize)
.distinct()
.boxed()
.filter(i -> !sample.contains(i))
.limit(sampleSizeSecondRound)
.collect(Collectors.toSet());

System.out.println(sample);
System.out.println(sampleSecondRound);
}
``````

If you are using Java 8 or higher, you could do something like below:

``````public static void main(String args[]) {
Random rand = new Random();

int populationSize =  20;
int sampleSizeFirstRound =  10;

Set&lt;Integer&gt; sample = rand.ints(1,populationSize)
.distinct()
.limit(sampleSizeFirstRound)
.boxed()
.collect(Collectors.toSet());

int sampleSizeSecondRound =  6;
Set&lt;Integer&gt; sampleSecondRound = rand.ints(1,populationSize)
.distinct()
.boxed()
.filter(i -&gt; !sample.contains(i))
.limit(sampleSizeSecondRound)
.collect(Collectors.toSet());

System.out.println(sample);
System.out.println(sampleSecondRound);
}
``````

To make it more manageable I have kept the sizes of the samples small. Adapt them as needed.

• 本文由 发表于 2020年7月31日 23:31:05
• 转载请务必保留本文链接：https://go.coder-hub.com/63194819.html
• java
• random

go 93

go 99

go 42

go 51