Java 创建没有重复的随机数

Creating random numbers with no duplicates

提问by Woong-Sup Jung

In this case, the MAX is only 5, so I could check the duplicates one by one, but how could I do this in a simpler way? For example, what if the MAX has a value of 20? Thanks.

在这种情况下，MAX 只有 5，所以我可以一一检查重复项，但我怎样才能以更简单的方式做到这一点？例如，如果 MAX 的值为 20 会怎样？谢谢。

int MAX = 5;

for (i = 1 , i <= MAX; i++)
{
        drawNum[1] = (int)(Math.random()*MAX)+1;

        while (drawNum[2] == drawNum[1])
        {
             drawNum[2] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[3] == drawNum[1]) || (drawNum[3] == drawNum[2]) )
        {
             drawNum[3] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[4] == drawNum[1]) || (drawNum[4] == drawNum[2]) || (drawNum[4] == drawNum[3]) )
        {
             drawNum[4] = (int)(Math.random()*MAX)+1;
        }
        while ((drawNum[5] == drawNum[1]) ||
               (drawNum[5] == drawNum[2]) ||
               (drawNum[5] == drawNum[3]) ||
               (drawNum[5] == drawNum[4]) )
        {
             drawNum[5] = (int)(Math.random()*MAX)+1;
        }

}

采纳答案by Jon Skeet

The simplest way would be to create a list of the possible numbers (1..20 or whatever) and then shuffle them with Collections.shuffle. Then just take however many elements you want. This is great if your range is equal to the number of elements you need in the end (e.g. for shuffling a deck of cards).

最简单的方法是创建一个可能数字（1..20 或其他）的列表，然后用Collections.shuffle. 然后只要你想要多少元素就可以了。如果您的范围等于您最终需要的元素数量（例如，用于洗牌），这很好。

That doesn't work so well if you want (say) 10 random elements in the range 1..10,000 - you'd end up doing a lot of work unnecessarily. At that point, it's probably better to keep a set of values you've generated so far, and just keep generating numbers in a loop until the next one isn't already present:

如果您想要（例如）1..10,000 范围内的 10 个随机元素，那效果不佳 - 您最终会做很多不必要的工作。在这一点上，最好保留一组迄今为止生成的值，并继续在循环中生成数字，直到下一个尚未出现：

if (max < numbersNeeded)
{
    throw new IllegalArgumentException("Can't ask for more numbers than are available");
}
Random rng = new Random(); // Ideally just create one instance globally
// Note: use LinkedHashSet to maintain insertion order
Set<Integer> generated = new LinkedHashSet<Integer>();
while (generated.size() < numbersNeeded)
{
    Integer next = rng.nextInt(max) + 1;
    // As we're adding to a set, this will automatically do a containment check
    generated.add(next);
}

Be careful with the set choice though - I've very deliberately used LinkedHashSetas it maintains insertion order, which we care about here.

但是要小心设置选择 - 我非常有意地使用LinkedHashSet它，因为它维护插入顺序，我们在这里关心。

Yet another option is to alwaysmake progress, by reducing the range each time and compensating for existing values. So for example, suppose you wanted 3 values in the range 0..9. On the first iteration you'd generate any number in the range 0..9 - let's say you generate a 4.

另一种选择是通过每次缩小范围并补偿现有值来始终取得进展。例如，假设您想要 0..9 范围内的 3 个值。在第一次迭代中，您将生成 0..9 范围内的任何数字 - 假设您生成一个 4。

On the second iteration you'd then generate a number in the range 0..8. If the generated number is less than 4, you'd keep it as is... otherwise you add one to it. That gets you a result range of 0..9 without 4. Suppose we get 7 that way.

在第二次迭代中，您将生成一个范围为 0..8 的数字。如果生成的数字小于 4，您将保持原样……否则您将向其添加 1。这使您得到的结果范围为 0..9，而没有 4。假设我们以这种方式得到 7。

On the third iteration you'd generate a number in the range 0..7. If the generated number is less than 4, you'd keep it as is. If it's 4 or 5, you'd add one. If it's 6 or 7, you'd add two. That way the result range is 0..9 without 4 or 6.

在第三次迭代中，您将生成一个范围为 0..7 的数字。如果生成的数字小于 4，则保持原样。如果是 4 或 5，你会加一个。如果是 6 或 7，则添加两个。这样结果范围是 0..9 而没有 4 或 6。

回答by Catchwa

Here's how I'd do it

这是我的方法

import java.util.ArrayList;
import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int size = 20;

        ArrayList<Integer> list = new ArrayList<Integer>(size);
        for(int i = 1; i <= size; i++) {
            list.add(i);
        }

        Random rand = new Random();
        while(list.size() > 0) {
            int index = rand.nextInt(list.size());
            System.out.println("Selected: "+list.remove(index));
        }
    }
}

As the esteemed Mr Skeet has pointed out:
If nis the number of randomly selected numbers you wish to choose and Nis the total sample space of numbers available for selection:

正如尊敬的斯基特先生所指出的那样：
如果n是您希望选择的随机选择数字的数量，而N是可供选择的数字的总样本空间：

1. If n<< N, you should just store the numbers that you have picked and check a list to see if the number selected is in it.
2. If n~= N, you should probably use my method, by populating a list containing the entire sample space and then removing numbers from it as you select them.

1. 如果n<< N，您应该只存储您选择的数字并检查列表以查看所选数字是否在其中。
2. 如果n~= N，您可能应该使用我的方法，通过填充包含整个样本空间的列表，然后在选择它们时从中删除数字。

回答by Lavir the Whiolet

There is algorithm of card batch: you create ordered array of numbers (the "card batch") and in every iteration you select a number at random position from it (removing the selected number from the "card batch" of course).

有卡片批次算法：您创建有序的数字数组（“卡片批次”），并在每次迭代中从中随机位置选择一个数字（当然，从“卡片批次”中删除所选数字）。

回答by SSTwinrova

You could use one of the classes implementing the Set interface (API), and then each number you generate, use Set.add() to insert it.

您可以使用实现 Set 接口 ( API)的类之一，然后您生成的每个数字，使用 Set.add() 插入它。

If the return value is false, you know the number has already been generated before.

如果返回值为false，则您知道该数字之前已经生成过。

回答by Martin Thurau

Hereis an efficient solution for fast creation of a randomized array. After randomization you can simply pick the n-th element eof the array, increment nand return e. This solution has O(1) for getting a random number and O(n) for initialization, but as a tradeoff requires a good amount of memory if n gets large enough.

这是快速创建随机数组的有效解决方案。随机化后，您可以简单地选择数组的n第 -th 个元素e，递增n并返回e。该解决方案具有用于获取随机数的 O(1) 和用于初始化的 O(n)，但作为权衡，如果 n 足够大，则需要大量内存。

回答by abdeali chandan

Instead of doing all this create a LinkedHashSetobject and random numbers to it by Math.random()function .... if any duplicated entry occurs the LinkedHashSetobject won't add that number to its List ... Since in this Collection Class no duplicate values are allowed .. in the end u get a list of random numbers having no duplicated values .... :D

而不是做这一切营造一个LinkedHashSet对象，并随机数给它Math.random()的功能....如果出现任何重复的条目中的LinkedHashSet对象不会是号码添加到其列表...因为在这个集合类没有重复值是允许..最后你会得到一个没有重复值的随机数列表......：D

回答by Satheesh Guduri

//random numbers are 0,1,2,3 
ArrayList<Integer> numbers = new ArrayList<Integer>();   
Random randomGenerator = new Random();
while (numbers.size() < 4) {

    int random = randomGenerator .nextInt(4);
    if (!numbers.contains(random)) {
        numbers.add(random);
    }
}

回答by Jim

There is a more efficient and less cumbersome solution for integers than a Collections.shuffle.

对于整数，有一个比 Collections.shuffle 更有效、更简单的解决方案。

The problem is the same as successively picking items from only the un-picked items in a set and setting them in order somewhere else. This is exactly like randomly dealing cards or drawing winning raffle tickets from a hat or bin.

问题与仅从集合中未选择的项目中连续选择项目并在其他地方按顺序设置它们的问题相同。这就像随机发牌或从帽子或垃圾箱中抽取中奖彩票一样。

This algorithm works for loading any array and achieving a random order at the end of the load. It also works for adding into a List collection (or any other indexed collection) and achieving a random sequence in the collection at the end of the adds.

该算法适用于加载任何数组并在加载结束时实现随机顺序。它也适用于添加到 List 集合（或任何其他索引集合）并在添加结束时在集合中实现随机序列。

It can be done with a single array, created once, or a numerically ordered collectio, such as a List, in place. For an array, the initial array size needs to be the exact size to contain all the intended values. If you don't know how many values might occur in advance, using a numerically orderred collection, such as an ArrayList or List, where the size is not immutable, will also work. It will work universally for an array of any size up to Integer.MAX_VALUE which is just over 2,000,000,000. List objects will have the same index limits. Your machine may run out of memory before you get to an array of that size. It may be more efficient to load an array typed to the object types and convert it to some collection, after loading the array. This is especially true if the target collection is not numerically indexed.

它可以通过一个单独的数组来完成，创建一次，或者一个数字排序的集合，比如一个列表，就地。对于数组，初始数组大小需要是包含所有预期值的确切大小。如果您事先不知道可能出现多少个值，也可以使用按数字排序的集合，例如大小不可变的 ArrayList 或 List。它适用于任何大小的数组，最大为 Integer.MAX_VALUE，刚好超过 2,000,000,000。列表对象将具有相同的索引限制。在获得该大小的数组之前，您的机器可能会耗尽内存。在加载数组后，加载类型为对象类型的数组并将其转换为某个集合可能更有效。如果目标集合没有数字索引，则尤其如此。

This algorithm, exactly as written, will create a very even distribution where there are no duplicates. One aspect that is VERY IMPORTANT is that it has to be possible for the insertion of the next item to occur up to the current size + 1. Thus, for the second item, it could be possible to store it in location 0 or location 1. For the 20th item, it could be possible to store it in any location, 0 through 19. It is just as possible the first item to stay in location 0 as it is for it to end up in any other location. It is just as possible for the next new item to go anywhere, including the next new location.

这个算法，正如所写的那样，将创建一个没有重复的非常均匀的分布。非常重要的一个方面是，下一项的插入必须能够达到当前大小 + 1。因此，对于第二项，可以将其存储在位置 0 或位置 1 . 对于第 20 个项目，可以将其存储在 0 到 19 之间的任何位置。第一个项目尽可能留在位置 0，因为它最终会出现在任何其他位置。下一个新项目尽可能去任何地方，包括下一个新位置。

The randomness of the sequence will be as random as the randomness of the random number generator.

序列的随机性将与随机数生成器的随机性一样随机。

This algorithm can also be used to load reference types into random locations in an array. Since this works with an array, it can also work with collections. That means you don't have to create the collection and then shuffle it or have it ordered on whatever orders the objects being inserted. The collection need only have the ability to insert an item anywhere in the collection or append it.

该算法还可用于将引用类型加载到数组中的随机位置。由于这适用于数组，因此它也适用于集合。这意味着您不必创建集合，然后对其进行洗牌或按插入对象的任何顺序对其进行排序。集合只需要能够在集合中的任何位置插入一个项目或附加它。

// RandomSequence.java
import java.util.Random;
public class RandomSequence {

    public static void main(String[] args) {
        // create an array of the size and type for which
        // you want a random sequence
        int[] randomSequence = new int[20];
        Random randomNumbers = new Random();

        for (int i = 0; i < randomSequence.length; i++ ) {
            if (i == 0) { // seed first entry in array with item 0
                randomSequence[i] = 0; 
            } else { // for all other items...
                // choose a random pointer to the segment of the
                // array already containing items
                int pointer = randomNumbers.nextInt(i + 1);
                randomSequence[i] = randomSequence[pointer]; 
                randomSequence[pointer] = i;
                // note that if pointer & i are equal
                // the new value will just go into location i and possibly stay there
                // this is VERY IMPORTANT to ensure the sequence is really random
                // and not biased
            } // end if...else
        } // end for
        for (int number: randomSequence) {
                System.out.printf("%2d ", number);
        } // end for
    } // end main
} // end class RandomSequence

回答by felipe

There is another way of doing "random" ordered numbers with LFSR, take a look at:

还有另一种用 LFSR 做“随机”有序数字的方法，看看：

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

with this technique you can achieve the ordered random number by index and making sure the values are not duplicated.

使用这种技术，您可以通过索引获得有序的随机数，并确保值不重复。

But these are not TRUE random numbers because the random generation is deterministic.

但这些不是真正的随机数，因为随机生成是确定性的。

But depending your caseyou can use this technique reducing the amount of processing on random number generation when using shuffling.

但是根据您的情况，您可以使用此技术减少使用改组时随机数生成的处理量。

Here a LFSR algorithm in java, (I took it somewhere I don't remeber):

这是java中的LFSR算法，（我把它带到了我不记得的地方）：

public final class LFSR {
    private static final int M = 15;

    // hard-coded for 15-bits
    private static final int[] TAPS = {14, 15};

    private final boolean[] bits = new boolean[M + 1];

    public LFSR() {
        this((int)System.currentTimeMillis());
    }

    public LFSR(int seed) {
        for(int i = 0; i < M; i++) {
            bits[i] = (((1 << i) & seed) >>> i) == 1;
        }
    }

    /* generate a random int uniformly on the interval [-2^31 + 1, 2^31 - 1] */
    public short nextShort() {
        //printBits();

        // calculate the integer value from the registers
        short next = 0;
        for(int i = 0; i < M; i++) {
            next |= (bits[i] ? 1 : 0) << i;
        }

        // allow for zero without allowing for -2^31
        if (next < 0) next++;

        // calculate the last register from all the preceding
        bits[M] = false;
        for(int i = 0; i < TAPS.length; i++) {
            bits[M] ^= bits[M - TAPS[i]];
        }

        // shift all the registers
        for(int i = 0; i < M; i++) {
            bits[i] = bits[i + 1];
        }

        return next;
    }

    /** returns random double uniformly over [0, 1) */
    public double nextDouble() {
        return ((nextShort() / (Integer.MAX_VALUE + 1.0)) + 1.0) / 2.0;
    }

    /** returns random boolean */
    public boolean nextBoolean() {
        return nextShort() >= 0;
    }

    public void printBits() {
        System.out.print(bits[M] ? 1 : 0);
        System.out.print(" -> ");
        for(int i = M - 1; i >= 0; i--) {
            System.out.print(bits[i] ? 1 : 0);
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LFSR rng = new LFSR();
        Vector<Short> vec = new Vector<Short>();
        for(int i = 0; i <= 32766; i++) {
            short next = rng.nextShort();
            // just testing/asserting to make 
            // sure the number doesn't repeat on a given list
            if (vec.contains(next))
                throw new RuntimeException("Index repeat: " + i);
            vec.add(next);
            System.out.println(next);
        }
    }
}

回答by blackcatweb

The most efficient, basic way to have non-repeating random numbers is explained by this pseudo-code. There is no need to have nested loops or hashed lookups:

这个伪代码解释了获得非重复随机数的最有效、最基本的方法。不需要嵌套循环或散列查找：

// get 5 unique random numbers, possible values 0 - 19
// (assume desired number of selections < number of choices)

const int POOL_SIZE = 20;
const int VAL_COUNT = 5;

declare Array mapping[POOL_SIZE];
declare Array results[VAL_COUNT];

declare i int;
declare r int;
declare max_rand int;

// create mapping array
for (i=0; i<POOL_SIZE; i++) {
   mapping[i] = i;
}

max_rand = POOL_SIZE-1;  // start loop searching for maximum value (19)

for (i=0; i<VAL_COUNT; i++) {
    r = Random(0, max_rand); // get random number
    results[i] = mapping[r]; // grab number from map array
    mapping[r] = max_rand;  // place item past range at selected location

    max_rand = max_rand - 1;  // reduce random scope by 1
}

Suppose first iteration generated random number 3 to start (from 0 - 19). This would make results[0] = mapping[3], i.e., the value 3. We'd then assign mapping[3] to 19.

假设第一次迭代生成随机数 3 开始（从 0 - 19）。这将使 results[0] = mapping[3]，即值 3。然后我们将 mapping[3] 分配给 19。

In the next iteration, the random number was 5 (from 0 - 18). This would make results[1] = mapping[5], i.e., the value 5. We'd then assign mapping[5] to 18.

在下一次迭代中，随机数为 5（从 0 到 18）。这将使 results[1] = mapping[5]，即值 5。然后我们将 mapping[5] 分配给 18。

Now suppose the next iteration chose 3 again (from 0 - 17). results[2] would be assigned the value of mapping[3], but now, this value is not 3, but 19.

现在假设下一次迭代再次选择 3（从 0 到 17）。结果 [2] 将被分配映射 [3] 的值，但现在，该值不是 3，而是 19。

This same protection persists for all numbers, even if you got the same number 5 times in a row. E.g., if the random number generator gave you 0 five times in a row, the results would be: [ 0, 19, 18, 17, 16 ].

即使您连续 5 次获得相同的号码，这种保护也适用于所有号码。例如，如果随机数生成器连续五次给你 0，结果将是：[ 0, 19, 18, 17, 16 ]。

You would never get the same number twice.

你永远不会得到两次相同的数字。