С/С++ | Выбор 10 случайных элементов из массива

[Vovius]

Надо реализовать такую штуку.
Имееться масив на (макс) 200 чисел
Заполняеться просто от 1 до 200, надо что бы прога выдала 10 из них полным рендомом, причём что бы не повторялись, кто знает как это сделать на с++ а ещё лучше в с++ builder 6.0.

[Cyberhawk]

надо что бы прога выдала 10 из них полным рендомом
Первые 10 или вообще? Если вообще, то как ты узнаешь, какие именно 10 выданы рандомом, а какие заполнены каким-то другим образом?
Короче, я толком не понял даже формулировки задачи. И какой диапазон у членов массива? И что значит Имееться масив на (макс) 200 чисел? Произвольный размер что ли?
Короче, ждем конкретизации задачи.

[XCodeR]

Vovius

Заполняеться просто от 1 до 200
в С++ нумерация идет с 0, а не с 1.

Допустим исходный массив mass.


int randoms[10],ri;
Randomize();
for(int i=0;i<10;i++)
{
ri=RandomRange(0,199);
randoms[i]=mass[ri];
}


Не забудьте подключить библиотеку Math.

[pva]

#include <vector>
#include <cstdlib>

int main()
{
// >> Надо реализовать такую штуку.
// >> Имееться масив на (макс) 200 чисел
std::vector<double> array1(200);

// >> Заполняеться просто от 1 до 200,
for(unsigned n=0; n<array1.size(); +n) array1[n] = n + 1;

// >> надо что бы прога выдала 10 из них полным рендомом,
std::randomize();
for(unsigned n=0; n<10; ++n)
{
unsigned rand_index = std::random(array1.size());
std::cout << array1[rand_index] << std::endl;

// >> причём что бы не повторялись,
std::vector<double>::iterator i = array1.begin();
std::advance(i, rand_index);
array1.erase(i);
}

// >> кто знает как это сделать на с++ а ещё лучше в с++ builder 6.0.
// работает с любым компилятором C++ 3.3.2 под любую ОС
return 0;
}

[Vovius]

Cyberhawk
Ну вот видьшь ниже всё народ понял.

XCodeR
Спасибо за команду для рандома.

pva
Спасибо полезный исходник.

[ivank]

pva
Небольша опечатка, должно бытьfor(unsigned n=0; n<array1.size(); ++n) array1[n] = n + 1;

А ещё можно воспользоваться random_shuffle (http://www.sgi.com/tech/stl/random_shuffle.html). Правда, если нужны только 10 элементов из 200 это будет слегка оверкилл. С другой стороны, он гарантированно линейный от размера массива (т.е. будет сделано 200 перестановок), а вариант pva, если ничего не путаю имеет сложность O(m*n) в худшем/среднем случае, где n - число требуемых элементов, а m - размер массива.

Ещё такое придумалось:

std::vector<int> array; //считаем, что как-то уже заполнено
std::set<size_t> used;
std::list<int> out;

for (size_t i = 0; i < n; ++i)
{
size_t j = rand() % array.size();
while (used.find(j) != used.end())
j = (j+1) % array.size();
out.push_back(array[j]);
used.insert(j);
}


Идея сводится к тому, что просто храним список использованных ключей. Если выпадает уже использованный, то перебираем все за ним следующие на предмет нахождения неиспользованного. Худший случай - O(n*n*logn), лучший - O(n*log n). Если n << m, то средний по идее стремится к лучшему.

Но вариант с rand_shuffle всё равно мне нравится больше. Своей краткостью.

upd Поправил заголовок темы. Прошу в будущем давать более содержательные названия.