Заполнение массива уникальными случайными числами

Если тебя волнует промежуток на котором будут эти числа, то смело суммируй. 
Пример:
цикл
  sum = рандом()
  н_i += sum
конец цикла 
Ну а рандом от 0 до 1, поэтому все чиcла разные будут. 

Построить список уникальных чисел нужного размера, потом по случайному индексу выдёргивать их оттуда, уменьшая диапазон для следующего индекса на 1.

Можно с затратами памяти: 

Строишь массив 1,2,3 ... RND_MAX. Перемешиваешь его 
за RND_MAX шагов по следующему алгоритму:  на i-ом шаге цикла от 1 до RND_MAX выбираешь случайный элемент между i-ым и последним массива и меняешь его значения (swap) с i-ым. 

Если N < RND_MAX, то перемешать можно только первые N элементов. 

Пример 
1 2 3 4 5 6 7 8 9
3 2 1 4 5 6 7 8 9
3 7 1 4 5 6 2 8 9
3 7 6 4 5 1 2 8 9 
..... 

>Построить список уникальных чисел нужного размера, потом по случайному индексу выдёргивать их оттуда, уменьшая диапазон для следующего индекса на 1.

А как можно сделать список, в котором и операция удаления, и операция обращения по индексу занимает константное время?

>А как можно сделать список, в котором и операция удаления, и операция обращения по индексу занимает константное время?

Поправка: не список, а множество (порядок не важен). Это то, что описал bizanine.

>Можно с затратами памяти:

Потому реально только для целых чисел небольшого диапазона.

Создаёшь массив, выбираешь несколько случайных чисел и пропускаешь через функцию, которая будет на основе них делать уникальные числа. Ещё лучше на основе одного числа, чтобы гарантировать неповторимость.

Кстати функцию можно сделать так, чтобы следующее число генерировалось на основе предыдущего, либо чтобы функция выдавала заданное количество таких уникальных чисел. Причём дважды случайность можно использовать:

1. Генерация базового числе 2. Генерация случайного числа, на основе которого будет делаться преобразование + перебор цикла для получения уникальности, скажем для уникального множителя или другого параметра.

> Если тебя волнует промежуток на котором будут эти числа, то смело суммируй.

Тогда это будет возрастающая последовательность. А это в данном случае плохо.

То есть, собственно, задача такая: из множества 1..n выбрать m различных чисел (m < n) и расположить в случайной последовательности.

n варьируется, m можно считать фиксированным.

> То есть, собственно, задача такая: из множества 1..n выбрать m различных чисел (m < n) и расположить в случайной последовательности.

Отлично, алгоритм в моём посте подходит :)

В примере тогда считай n = 9 и m = 3. Первые 3 числа в последней строчке -- ответ. Сложность = n + m, затраты памяти = n.

Массив из 2 столбцов. Первый столбец - номер строки, второй - случайное число с плавающей точкой между 0 и 1. Сортируешь массив по второму столцу.

Можно решить за o(N). Если взять правильный генератор ПСЧ с длиной последовательности на много порядков превышающей размерность массива. Про генераторы ПСЧ читать у Кнута.

+1

# быстрое заполнение массива случайными числами 0..size-1
void fill_array(int *arr,int size) {
  int pos,npos;
  memset(arr,-1,size);
  for(pos=0;pos<size-1;) {
     npos=1+pos+(random()%(size-pos-1));// случайное число pos+1..size-1
     if ( arr[npos]==-1 ) {
         arr[npos]=pos;
     } else if (arr[pos]==-1) {
         arr[pos]=arr[npos];
         arr[npos]=pos;
     } else {
         swap(arr,pos,npos); // поменять местами два элемента
         continue;
     }
     pos++;
  }
}
# не тестилось :) 

npos=random()%size; // так наверное правильнее