百科问答小站 logo   百科问答小站
问题

c++怎么在1到n这些数中随机产生k（k<n）个？当然，k个数互不相等。有什么比较好的写法吗？

回答
在 C++ 中从 1 到 n（含）的整数范围内，不重复地随机选取 k 个数，这是一个非常常见的需求。网上虽然有不少解决方案，但要做到既简洁高效，又易于理解，还需要一些技巧。下面我来详细讲讲几种思路，并给出比较好的实现方式。

核心问题：无重复随机选取

首先，我们需要明确核心问题：从一个集合 {1, 2, ..., n} 中，不放回地抽取 k 个元素，且抽取出的 k 个元素是随机的。

方法一：先打乱再选取 (FisherYates Shuffle)

这个方法可以说是最直观也是最可靠的。思路是：

1. 创建一个包含 1 到 n 的有序数组。
2. 对这个数组进行随机打乱（洗牌），保证打乱后的顺序是随机的。
3. 从打乱后的数组的开头选取前 k 个元素。

为什么 FisherYates Shuffle 很好？

FisherYates Shuffle (又名 Knuth Shuffle) 是一种经典的、能够产生均匀随机排列的算法。它的核心思想是：

从最后一个元素开始，到第一个元素依次向前遍历。
对于当前遍历到的元素 `i`，从 `0` 到 `i`（包含 `i`）之间随机选择一个索引 `j`。
交换 `i` 和 `j` 位置上的元素。

这样一来，每个元素最终出现在任何位置的概率都是均等的。

C++ 实现思路：

1. 生成初始序列：
使用 `std::vector` 存储 1 到 n 的整数。

```c++
std::vector numbers(n);
std::iota(numbers.begin(), numbers.end(), 1); // numbers 现在是 {1, 2, ..., n}
```

`std::iota` 是 C++11 引入的一个非常有用的算法，它会填充一个范围，从一个起始值开始，按递增顺序。

2. 随机数生成器：
C++11 之后，推荐使用 `` 库来生成随机数，而不是 `rand()`。这提供了更好的控制和分布。

```c++
std::random_device rd; // 用于获取一个随机种子
std::mt19937 generator(rd()); // Mersenne Twister 19937 引擎，生成高质量随机数
```

3. 执行 FisherYates Shuffle：
C++ 标准库提供了一个现成的算法：`std::shuffle`。它正是基于 FisherYates Shuffle 的思想实现的。

```c++
std::shuffle(numbers.begin(), numbers.end(), generator);
```

4. 选取前 k 个：
从打乱后的 `numbers` 向量中，取前 k 个元素。

```c++
std::vector result;
result.reserve(k); // 预留空间，避免多次 realloc
for (int i = 0; i < k; ++i) {
result.push_back(numbers[i]);
}
```
或者更简洁地：
```c++
std::vector result(numbers.begin(), numbers.begin() + k);
```

完整代码示例 (方法一)：

```c++
include
include
include // for std::iota
include // for random number generation
include // for std::shuffle

// Function to generate k unique random numbers from 1 to n
std::vector generate_unique_random_numbers_shuffle(int n, int k) {
if (k <= 0 || k > n) {
// Handle invalid input: k must be between 1 and n
// Depending on requirements, you might throw an exception, return an empty vector, etc.
std::cerr << "Error: k must be between 1 and n." << std::endl;
return {};
}

// 1. Create a vector with numbers from 1 to n
std::vector numbers(n);
std::iota(numbers.begin(), numbers.end(), 1); // Fills with 1, 2, 3, ... n

// 2. Set up a random number generator
std::random_device rd; // Obtain a random number from hardware
std::mt19937 generator(rd()); // Seed the generator

// 3. Shuffle the vector
std::shuffle(numbers.begin(), numbers.end(), generator);

// 4. Take the first k elements
std::vector result(numbers.begin(), numbers.begin() + k);

return result;
}

int main() {
int n = 20; // Range from 1 to 20
int k = 5; // We want 5 unique random numbers

std::cout << "Generating " << k << " unique random numbers from 1 to " << n << ":" << std::endl;
std::vector random_nums = generate_unique_random_numbers_shuffle(n, k);

for (int num : random_nums) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}
```

优缺点分析 (方法一)：

优点：
保证均匀随机性： FisherYates Shuffle 是一个经过充分证明的算法，能产生真正的均匀随机排列。
代码简洁： 使用 `std::shuffle` 后，代码非常简洁易懂。
概念清晰： 打乱再选取，思路清晰。
缺点：
内存开销： 需要创建一个大小为 `n` 的向量。当 `n` 非常大而 `k` 相对较小时，这会造成一定的内存浪费。
时间复杂度： `std::iota` 是 O(n)，`std::shuffle` 是 O(n)，选取是 O(k)。总的来说是 O(n)。如果 `n` 极大，这个时间开销也可能比较显著。

方法二：逐个选取并检查 (Set/Map Approach)

当 `n` 非常大，而 `k` 相对较小时，方法一可能会因为生成和打乱整个 `n` 的序列而显得效率不高。这时，我们可以考虑另一种方法：

1. 循环 `k` 次。
2. 在每次循环中，生成一个 1 到 n 的随机数。
3. 检查这个随机数是否已经选取过。
如果没选取过，就将其加入结果集，并标记为已选取。
如果已经选取过，则重新生成。
4. 重复直到选取了 `k` 个数。

如何高效检查是否选取过？

这里就需要一个数据结构来快速查找。`std::set` 或 `std::unordered_set` 是非常合适的选择。`std::unordered_set` 通常提供 O(1) 的平均查找时间，而 `std::set` 提供 O(log k) 的查找时间。

C++ 实现思路 (使用 `std::unordered_set`)：

1. 随机数生成器： 同方法一。
2. 存储已选取数： 使用 `std::unordered_set`。
3. 循环选取：

```c++
std::random_device rd;
std::mt19937 generator(rd());
std::uniform_int_distribution distribution(1, n); // 生成 1 到 n 的整数

std::unordered_set selected_numbers;
std::vector result;
result.reserve(k); // 预留空间

while (selected_numbers.size() < k) {
int random_num = distribution(generator); // 生成一个随机数
// Try to insert into the set. insert() returns a pair: {iterator, bool}
// The bool is true if insertion took place (i.e., it was a new number)
if (selected_numbers.insert(random_num).second) {
result.push_back(random_num);
}
}
```

完整代码示例 (方法二)：

```c++
include
include
include
include
include // for std::sort, if needed for output

// Function to generate k unique random numbers from 1 to n (efficient for small k, large n)
std::vector generate_unique_random_numbers_set(int n, int k) {
if (k <= 0 || k > n) {
std::cerr << "Error: k must be between 1 and n." << std::endl;
return {};
}

// Set up a random number generator
std::random_device rd;
std::mt19937 generator(rd());
std::uniform_int_distribution distribution(1, n); // Distribution for numbers from 1 to n

std::unordered_set selected_numbers;
std::vector result;
result.reserve(k); // Preallocate memory for k elements

// Loop until we have collected k unique numbers
while (selected_numbers.size() < k) {
int random_num = distribution(generator); // Generate a random number in the range [1, n]

// Attempt to insert the number into the set.
// insert() returns a pair: {iterator to element, bool indicating if insertion occurred}
// The .second part of the pair is true if the element was new and inserted.
if (selected_numbers.insert(random_num).second) {
result.push_back(random_num); // Add the unique number to our result vector
}
// If insert().second was false, it means the number was already in the set,
// so we simply try again in the next iteration.
}

return result;
}

int main() {
int n = 1000000; // Range from 1 to 1,000,000
int k = 10; // We want 10 unique random numbers

std::cout << "Generating " << k << " unique random numbers from 1 to " << n << " using set method:" << std::endl;
std::vector random_nums = generate_unique_random_numbers_set(n, k);

// Optional: sort the output for easier reading
std::sort(random_nums.begin(), random_nums.end());

for (int num : random_nums) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}
```

优缺点分析 (方法二)：

优点：
内存效率高： 只需存储 `k` 个已选取的数字，对于 `n` 很大而 `k` 很小的情况非常节省内存。
时间效率（在特定条件下）： 当 `k` 远小于 `n` 时，平均来说，每次检查和插入的次数不会太多，生成 `k` 个数的时间会比较快。
缺点：
最坏情况时间复杂度： 理论上，如果运气极差，可能需要很多次尝试才能生成一个未出现过的数字。例如，当 `k` 接近 `n` 时，生成最后一个数字的概率会越来越低，导致循环次数急剧增加。这可能是此方法最主要的隐患。
不是严格的均匀分布（在某些实现细节上）： 虽然 `std::uniform_int_distribution` 提供了均匀分布的随机数，但重复检查和重新生成的过程，在数学上可能引入微小的偏差（尽管在实际应用中通常可以忽略不计）。

方法三：优化版逐个选取 (Reservoir Sampling 变种)

方法二的缺点在于当 `k` 接近 `n` 时效率会大幅下降。我们可以结合方法一的打乱思想，但又避免生成整个序列，来优化这个问题。

这个方法更像是 Reservoir Sampling 的一个变种，但在这里我们不需要从一个流中选取。思路是：

1. 创建一个大小为 `k` 的结果数组 `result`。
2. 先用 1 到 `k` 填充 `result`。
3. 然后，对于从 `k+1` 到 `n` 的每一个数 `i`：
以 `k/i` 的概率，用 `i` 替换 `result` 中的一个随机元素。
具体实现是：生成一个 1 到 `i` 的随机数 `j`。如果 `j <= k`，则用 `i` 替换 `result[j1]`。

为什么这样有效？

这是基于一个概率原理：对于任何一个要选择的数字 `x` (1 <= x <= n)，它最终出现在 `result` 数组中的概率都是 `k/n`。

对于 1 到 k 的数： 它们一开始就被放入了 `result` 数组。之后，对于 `i` 从 `k+1` 到 `n`，每个数 `i` 有 `k/i` 的概率被选中替换掉 `result` 中的一个元素。这意味着 `result` 中的一个数被替换掉的概率是 `1/k`。因此，一个数 `x` (1 <= x <= k) 在 `result` 中不被替换的概率是 `(1 1/(k+1)) (1 1/(k+2)) ... (1 1/n)`。 这个乘积化简后等于 `(k/(k+1)) ((k+1)/(k+2)) ... ((n1)/n) = k/n`。
对于 k+1 到 n 的数： 一个数 `x` (k+1 <= x <= n) 要被选中，它必须在处理到 `x` 时被选中（概率 `k/x`），并且之后在处理 `x+1` 到 `n` 的过程中，它不被后续的数字替换。同样的逻辑，它不被替换的概率是 `(x/(x+1)) ((x+1)/(x+2)) ... ((n1)/n) = x/n`。所以 `x` 被选中的总概率是 `(k/x) (x/n) = k/n`。

C++ 实现思路：

1. 随机数生成器： 同方法一。
2. 初始化 `result`：
```c++
std::vector result(k);
std::iota(result.begin(), result.end(), 1); // result is {1, 2, ..., k}
```
3. 处理 k+1 到 n：

```c++
std::random_device rd;
std::mt19937 generator(rd());

for (int i = k + 1; i <= n; ++i) {
// Generate a random index from 0 to i1 (inclusive)
// For this method, we need a random number from 0 to i1.
std::uniform_int_distribution distribution(0, i 1);
int j = distribution(generator);

// If the random index j falls within the first k positions
// (i.e., 0 to k1), replace the element at that position.
if (j < k) {
result[j] = i; // Replace result[j] with the current number i
}
}
```

完整代码示例 (方法三)：

```c++
include
include
include // for std::iota
include // for random number generation
include // for std::shuffle (if needed later)

// Function to generate k unique random numbers from 1 to n
// Optimized for cases where k is not significantly smaller than n
std::vector generate_unique_random_numbers_optimized(int n, int k) {
if (k <= 0 || k > n) {
std::cerr << "Error: k must be between 1 and n." << std::endl;
return {};
}

// 1. Initialize a vector of size k with numbers from 1 to k.
std::vector result(k);
std::iota(result.begin(), result.end(), 1); // Fills with 1, 2, ..., k

// 2. Set up a random number generator.
std::random_device rd;
std::mt19937 generator(rd());

// 3. Iterate from k+1 to n.
for (int i = k + 1; i <= n; ++i) {
// Generate a random integer 'j' between 0 and i1 (inclusive).
// The probability of picking any specific number from 0 to i1 is 1/i.
std::uniform_int_distribution distribution(0, i 1);
int j = distribution(generator);

// If 'j' is less than k, replace the element at index 'j' in 'result'
// with the current number 'i'.
// The probability of this happening is k/i.
if (j < k) {
result[j] = i;
}
}

// At this point, 'result' contains k unique random numbers.
// The order in 'result' is not guaranteed to be random.
// If a random order is desired, you can shuffle it.
// std::shuffle(result.begin(), result.end(), generator);

return result;
}

int main() {
int n = 20; // Range from 1 to 20
int k = 10; // We want 10 unique random numbers

std::cout << "Generating " << k << " unique random numbers from 1 to " << n << " using optimized method:" << std::endl;
std::vector random_nums = generate_unique_random_numbers_optimized(n, k);

// Optional: sort the output for easier reading
std::sort(random_nums.begin(), random_nums.end());

for (int num : random_nums) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}
```

优缺点分析 (方法三)：

优点：
内存效率高： 只需存储 `k` 个数字。
时间效率均衡： 时间复杂度是 O(n)，但它的常数因子比方法一（打乱整个数组）要小，并且它避免了方法二在 `k` 接近 `n` 时的性能瓶颈。
随机性保证： 严格遵循概率原理，保证了结果的均匀随机性。
缺点：
理解稍复杂： 相较于方法一，其背后的概率证明稍微复杂一些。
输出顺序非随机： 数组 `result` 中的元素虽然是随机选取的，但它们的顺序并不一定是随机的。如果需要随机顺序，最后需要再进行一次 `std::shuffle`。

总结与推荐

1. 如果你追求最简洁的代码和最易懂的逻辑，并且 `n` 的大小不是极端到内存是首要考虑因素： 方法一 (FisherYates Shuffle) 是最佳选择。使用 `std::shuffle` 非常方便。
优点： 代码简洁，理论清晰，随机性最可靠。
缺点： 内存开销 O(n)。

2. 如果你知道 `k` 总是远小于 `n`，并且内存是一个非常敏感的因素： 方法二 (Set/Map Approach) 是一个不错的选择，但要警惕 `k` 接近 `n` 时可能出现的性能问题。
优点： 内存开销 O(k)，在 k << n 时效率高。
缺点： k 接近 n 时效率急剧下降，理论上可能无限循环。

3. 如果你需要一个在内存和性能之间取得良好平衡的通用方案，尤其是在 `k` 和 `n` 的比例不确定时： 方法三 (Optimized Approach) 是最推荐的。它结合了两种方法的优点，在各种场景下表现都比较稳定和高效。
优点： 内存开销 O(k)，时间复杂度 O(n) 但常数因子小，性能均衡，无性能瓶颈。
缺点： 代码稍复杂，输出顺序非随机。

我个人更倾向于推荐方法三，因为它在大多数实际场景下都表现得相当出色，既考虑了效率，又避免了方法二的潜在问题。 如果代码简洁性是第一位的，方法一也完全可以接受。

在实际使用时，请务必根据你的具体需求（数据范围 `n`，期望选取数量 `k`，对内存和时间的要求）来选择最合适的方法。同时，确保使用 `` 库提供的工具来生成随机数，以获得更好的随机质量。

网友意见

user avatar

传统的rand()%pool_size方法在一般情况下可以采用，但是实际上这样产生的随机数分布不是完全均匀的。如果对随机数要求较高的话，建议采用下列方法：

       #include <random> #include <iostream>  const int n=10000; const int k=1000; bool taken[n]; int result[k];  int main() {     std::random_device rd;     std::mt19937 gen(rd());     std::uniform_int_distribution<> dis(1, n);      for(int count=0; count<k; ++count)     {         int tmpResult = dis(gen);         while (taken[tmpResult])         {             tmpResult = dis(gen);         }         result[count] = tmpResult;         taken[tmpResult] = true;     }      for(int count=0; count<k; ++count)         std::cout<<result[count]<<std::endl; }

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有

服务条款
联系我们
关于我们
隐私政策
友情链接
知乎
百度问答
搜狐
新浪