Есть std::set
минимум из N элементов. Как выбрать N разных случайных?
Порядок любой.
Если постановка задачи требует именно работы на структуре данных с последовательным доступом, то классический "алгоритм Кнута" подойдет прекрасно: проходим последовательно по элементам std::set
и принимаем решение брать очередной элемент с вероятностью осталось набрать элементов / осталось пройти элементов
int main()
{
std::set<int> s = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
unsigned N = 3;
std::vector<int> r;
auto it = s.begin();
for (unsigned S = s.size(); S > 0 && N > 0; --S, ++it)
if (rand() % S < N)
{
r.push_back(*it);
--N;
}
std::copy(r.begin(), r.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
Такой алгоритм выполнит случайную выборку N
элементов с сохранением их относительного порядка из исходного std::set
. Если порядок тоже надо получить случайный, то можно просто дополнительно сделать случайную перетасовку полученной выборки.
Другим вариантом будет алгоритм "резервуарной выборки", согласно которому мы сначала сразу забираем N
первых элементов из std::set
в нашу выборку, а затем итерируем через оставшиеся элементы std::set
(начиная с элемента с номером i = N
). Каждый новый элемент мы забираем в выборку с вероятностью N / (i + 1)
и сохраняем в случайную позицию в выборке
int main()
{
std::set<int> s = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
unsigned N = 3;
std::vector<int> r;
auto it = s.begin();
unsigned i = 0;
for (; i < N; ++i, ++it)
r.push_back(*it);
for (; it != s.end(); ++i, ++it)
if (rand() % (i + 1) < N)
r[rand() % N] = *it;
std::copy(r.begin(), r.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
Такой алгоритм уже не будет сохранять относительный порядок элементов в выборке. Однако из-за того, что первые N
элементов выбраны по порядку, полной случайности порядка и тут нет.
Интересной особенностью варианта "резервуарной выборки" является то, что ему не нужно знать размера исходной последовательности заранее, т.е. его можно использовать для генерации случайной выборки из последовательности, генерируемой неким "оракулом", не зная заранее, когда эта последовательность закончится. (Например, для случайной выборки строк из текстового файла нет необходимости знать заранее, сколько в этом файле строк.)
Если бы исходный контейнер поддерживал эффективный прямой доступ по индексу элемента (т.е. если бы это был массив, а не std::set
), то такие подходы были бы довольно неэффективными в ситуациях, когда N
намного меньше, чем размер исходного контейнера. Но в случае std::set
это соображение неприменимо.
Если воспользоваться дополнительным вектором - просто: выбираем в нем эти N элементов, а потом берем соответствующие из множества.
Вряд ли вы будете работать с ними прямо во множестве - скорее всего, вы будете использовать либо копии элементов, либо итераторы/указатели, на них указывающие. В таком случае можно просто загрузить их в вектор, перемешать и выбрать первые N, например.
Если вы уточните, как вы планируете их использовать - можно будет уточнить способ :)
используйте альгоритм std::random_shuffle или std::next_permutation
Какие существуют виды рекламных бордов и как выбрать подходящий?
Аренда удаленного сервера: цены, провайдеры и условия. Руководство для начинающих
Всем приветВ общем дали мне задание, связанное с сортировкой методом шейкере используя пользовательские типы fraction и data
Я думаю что нельзяТак как в куча имеет хедер в котором есть(свободный ли блок и сколько байт в нему)
ЗдравствуйтеВыдает непонятную ошибку, как исправить? Скриншот: Вот исходный код:
У меня есть число N - наименьшее общее кратное двух чисел a и b