Нужен алгоритм выборки - Компьютерный форум OSzone.net

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

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

- - Нужен алгоритм выборки (http://forum.oszone.net/showthread.php?t=42145)

Нужен алгоритм выборки

Нужно получить n неповторяющихся целых чисел, равномерно распределенных от 1 до N (n <= N). Считаем, что функция, выдающая _одно_ псевдослучайное число, есть.
Просто проверять каждое вновь получаемое число на совпадение со всеми выпавшими до него, при совпадении бросать снова и снова проверять - долго и тупо. Не подскажет ли кто-нибудь более быстрый алгоритм?

IksSafonsky
Толи я смысл задачи не уловил, толи... Случайной выборкой тут и так ничего не выйдет, ведь получаемые числа не будут распределены равномерно. Если заполнять диапазон от 1 до N до предела, то получится ряд чисел с шагом единица, в получении такого ряда вообще не вижу проблем. Если задаться произвольным целым шагом (в нецелом смысла нет), то создаем цикл от 1, в цикле включаем счетчик, что бы знать n, на каждом новом шаге определяем новое число, добавляя шаг к предыдущему числу и проверяем условие, что бы вновь полученное число не превысило N. В общих чертах так, по идее проще валенка или я чего-то не допер с просонья? В таком случае прошу меня вразумить.

IksSafonsky

Код:

int i;

int n;

int found[N]; // это с помощью malloc

int data[N]; // ...

...

for (i=0; i<N; ++i)

{

        data[i] = i+1;

}

 

n = 0;

 

while (N>1)

{

        i = random(N--);

 

        found[n++] = data[i];

 

        for (int k=i; k<N; ++k)

        {

                data[k] = data[k+1];

        }

}

 

found[n] = data[0];