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

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

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

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

Цитата:

надо что бы прога выдала 10 из них полным рендомом

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

Цитата:

Имееться масив на (макс) 200 чисел

? Произвольный размер что ли?
Короче, ждем конкретизации задачи.

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.

Код:

#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;

}

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

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

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

pva
Небольша опечатка, должно быть

Код:

for(unsigned n=0; n<array1.size(); ++n) array1[n] = n + 1;

А ещё можно воспользоваться random_shuffle. Правда, если нужны только 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 Поправил заголовок темы. Прошу в будущем давать более содержательные названия.