給定一個向量和一定數量的元素 n，我正在尋找一種方法來從向量中選擇 n 個元素，其概率與它們的索引成反比。
例子：
std::vector v = {0, 1, 2, ... 998, 999};
n = 10;
一組潛在的選定指數可能是：
{50, 200, 350, 500, 600, 700, 800, 850, 900, 950}
筆記：
- 選擇的索引需要在呼叫之間保持一致。
- 不能在同一個呼叫結果中兩次選擇同一個索引。
- 向量開頭的索引密度必須與向量結尾的索引密度成正比。即結果 {990 ... 999} 對于給定的示例無效。
- 我更喜歡盡可能多地使用標準庫中的代碼，而不必自己實作。
- 與復雜而高效的解決方案相比，我可能更喜歡簡單且有效但效率較低的解決方案。
謝謝
uj5u.com熱心網友回復：
本文介紹了一種加權隨機抽樣方法。下面是一個 C 實作。
這是1 / index為基于 1 的資料索引分配權重
namespace views = std::ranges::views;
std::random_device rd;
std::mt19937 gen(rd()); // or whichever URBG you want
std::uniform_real_distribution<double> dist(0, 1);
std::vector<std::pair<double, std::size_t>> weighted_indexes;
weighted_indexes.reserve(v.size());
for (auto i : views::iota(0u, v.size())) {
auto k = std::pow(dist(gen), 1.0 / (i 1));
weighted_indexes.emplace_back(k, i);
}
std::sort(weighted_indexes.begin(), weighted_indexes.end());
auto indexes = weighted_indexes | views::take(n) | views::values;
auto selected_values = indexes | views::transform([&v](std::size_t i){ return v[i]; });
uj5u.com熱心網友回復：
您可以使用std::discrete_distribution：
#include <iostream>
#include <numeric>
#include <vector>
#include <random>
#include <map>
int main() {
std::vector<int> v(10);
std::iota(v.begin(),v.end(),1);
std::vector<int> indices = v;
//for (const auto& e : v) std::cout << e << " ";
std::vector<double> probs(indices.size());
std::transform(indices.begin(),indices.end(),probs.begin(),[](int x){ return 1.0/x;});
//for (const auto& e : probs) std::cout << e << " ";
// modified example from https://en.cppreference.com/w/cpp/numeric/random/discrete_distribution
std::random_device rd;
std::mt19937 gen(rd());
std::discrete_distribution<> d(probs.begin(),probs.end());
std::map<int, int> m;
for(int n=0; n<10000; n) {
m[d(gen)];
}
for(auto p : m) {
std::cout << v[p.first] << " generated " << p.second << " times\n";
}
}
就示例而言，v只填充了1直到v.size()-1并且因為1/0格式錯誤，索引也從 開始1（即indices只是 的副本v）。
以上是選擇一個權重為 1/index 的元素。如果您只想選擇每個元素一次，您可以在選擇下一個元素之前將相應的權重設定為零。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/331750.html
上一篇：如何以相反的方式制作數字的平方？