生成唯一的随机数

Question

如何生成9个介于1到9之间的随机数，且不重复，一个接一个地生成。就像这样： 假设第一个随机数生成的是4，那么下一个随机数必须在[1, 9] - {4}内。 我的第一种方法是将每个随机生成的数字添加到一个集合中，以避免重复。但是，在更糟糕的情况下，例如我们已经生成了6个数字并且还需要生成3个数字时，该过程会变得有点慢。而当范围从[1, 9]更改为[1, 1000]时，这种方法听起来就不正确了。 有人能提出另一种方法吗？

- gonephishing

---

你可以将刚选择的数字与末尾的数字交换，假装在下一步中你将从一个长度减少了一个元素的数组中进行选择。 - j_random_hacker

生成一个数字并记录其“频率”..如果“频率> 0”，则生成另一个随机数并执行“加”、“减”或进行某些数学运算以获得另一个数字..尽管这也将是非常繁忙的工作。 - rock321987

你需要生成一个排列并从中选择。如果可以将所有内容保存在内存中，请进行洗牌。 - odedsh

生成数组：int set[9]={1,2,3,4,5,6,7,8,9}，并在循环中执行for(i=0;i<9;i++)，交换set[i]和set[j]，其中j是随机数<0，8>，这是O(N)，我认为这是可以接受的。 - Spektre

Answer 1

从排序的数组开始（通过循环轻松创建）；然后通过交换每个数组元素与另一个（随机选择的）元素来进行洗牌。为避免评论中讨论的偏差，其他元素的索引必须等于或高于第一个元素的索引。 如果索引相等，则元素不会被交换。（此答案的原始版本包含一句关于元素可能被交换回来的话，但现在已经过时，因为这不能再发生了。）

- Erich Kitzmueller

---

实际上，这个看似正确的算法 实际上是非随机地洗牌。 - j_random_hacker

为了获得一个无偏的洗牌结果，你需要确保每个元素只能与随机选择的后续元素或它本身（即不交换）进行交换。 - j_random_hacker

@j_random_hacker：哇，谢谢你提供的信息！ - Erich Kitzmueller

不客气 :) 这不是一个大的改变，所以如果你更新了你的答案，我会+2。 - j_random_hacker

Answer 2

如果您不想自己实现算法来完成您想要的操作，可以使用Java库中已经实现的一种简单方法。您可以创建一个集合（一个已排序的List），其中包含Integer（从start到end，例如在您的例子中，start=1且end=9），然后使用Collections.shuffle(list);方法进行随机排列，例如：

static List<Integer> randArray(int start, int end) { //specify start/end
    List<Integer> randList=new ArrayList<>(end-start+1); //create list
    for (int k=start;k<=end;k++) { //generate integers in order
        randList.add(k); //add integers to the list
    }        
    Collections.shuffle(randList); //reoder randomly the list
    return randList; //return the list with items in random order
}

< p > shuffle 方法只是随机重新排列列表中的项目。

- WoDoSc

---

是的，它可以工作...不过现在我更想知道Collections.shuffle()是如何工作的。 - gonephishing

Answer 3

以下是两种可能的方法：-

方法1:-

1. 将所有数字存储在大小为n的数组中。 2. 随机选择一个索引号i=rand(0,size) 3. 打印arr[i] 4. 交换arr[i]和arr[size-1] 5. size=size-1 6. 重复步骤1到5直至列表耗尽。

时间复杂度：O(N)

空间复杂度：O(N)

方法2:-

1. 选择池大小为K。 2. 生成K个随机整数。 3. 显示它们作为前k个结果。 4. 将它们添加到哈希集合中。 5. 添加所有先前整数池中的ak+1。 6. 如果不在哈希集合中，则加1。 7. 从池中随机选择一个整数r并显示它。 8. 如果r+1不在哈希集合中，则将其添加到池中。 9. 重复步骤7到8，直到池用尽。

时间复杂度：O(N)

空间复杂度：O(K)

优缺点:-

方法1: 适用于小范围的整数，因为它需要更大的空间，但速度很快且随机性高。

方法2: 适用于较大范围的整数，因为它需要的内存是O(K)，可以根据您的选择进行调整。k越高，所生成的数字随机性越高。因此，您可以在保持良好速度的同时实现很好的空间和随机性之间的平衡。

- Vikram Bhat

Answer 4

生成一个按顺序排列的包含数字1到9的数组。

int arr[]=new int[9];
for(int i=0;i<9;i++)
   arr[i]=i+1;

现在对给定的数组进行shuffle操作。

如何对数组进行洗牌？

To shuffle an array a of n elements (indices 0..n-1):
   for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

参考资料

http://www.geeksforgeeks.org/shuffle-a-given-array/

- Ayush

---

是的...刚得到这个算法 -> 费舍尔-耶茨洗牌算法 - gonephishing

是的，这个程序将以相等概率生成从1到9的随机数字。 - Ayush

Answer 5

使用Java 8，Enne的方法可以写成这样：

private static List<Integer> generateRandom( int low, int high )
{
    List<Integer> range = IntStream.range( low, high ).boxed()
                                   .collect( Collectors.toList() );

    Collections.shuffle( range );
    return range;
}

- Max Fichtelmann

---

我现在没有使用Java 8，但这肯定会有所帮助 :) - gonephishing

Answer 6

public ArrayList<Integer> getRandom(int numbers,int min_value, int max_value)
{     
    HashSet<Integer> list = new HashSet<>();
    Random r = new Random();
    while (list.size()<numbers) {
        list.add(r.nextInt(max_value - min_value) + min_value);
    }
    return new ArrayList<>(list);
}

替代方案：

public ArrayList<Integer> getRandom(int numbers,int min_value, int max_value)
{     
    Random r = new Random();
    ArrayList<Integer> list = new ArrayList<>();
    for(int i=min_value; i<=max_value;i++)
        list.add(i);
    while (list.size()>numbers) {
       list.remove(r.nextInt(list.size()));
    }
    Collections.shuffle(list);
    return list;
}

替代方案：

   public ArrayList<Integer> getRandom(int numbers, int min_value, int max_value) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = min_value; i <= max_value; i++) {
        list.add(i);
    }
    Collections.shuffle(list);
    return new ArrayList<>(list.subList(0, numbers));
}

- Andie2302

---

谢谢...所有三个算法都有效。虽然我已经提到，在第一种方法中，list.add()会使过程变慢，因为越来越多的数字填充到HashSet中，因为相同的随机数会一遍又一遍地生成。这会影响算法的效率。此外，如其他评论所述，list.remove()方法效率低下，因为每次删除一个数字以填补空缺时，数字都必须移动。我想Fisher-Yates_shuffle是一种类似于Collections.shuffle()的算法。 - gonephishing

Answer 7

创建一个类似于这样的ArrayList：

索引0->索引1->索引2...

[1] -> [2] -> [3]....

生成一个介于0和list.size()之间的随机索引值，并获取列表中的位置：

yourNumberResult = get(randomIndexValue).

然后从列表中删除该位置：

list.remove(randomIndexValue)

然后重复这个过程，直到list.size()==0

- João Marcos

---

请注意，从ArrayList中删除项目是低效的，因为所有在被移除元素后面的元素都必须向下移动以填补间隙。在大型数组上反复执行此操作将会导致大量的内存流量，可能成为瓶颈。 - Wyzard

我猜交换而不是删除可能会更快，但是还是谢谢你提供算法。 - gonephishing

我不知道是因为交换算法非常复杂。我认为对于小于10000的列表，您没有性能差异，但是如果很重要，请尝试这两种方法并计算时间。 - João Marcos