Создание упорядоченного массива случайных чисел

[AMDemon]

Задача звучит так: создать массив целых чисел длины n, элементы которого не отрицательны и не превышает k. n и k задаются пользователем.
Без последнего условия задача решается крайне просто:
randomize();
array[0]=random(10);
for (i=1;i<n;i++) array+=random(10);
Но когда k<n начинаются поблемы...
Есть у кого-нибудь идеи?

[Albor]

Судя по задаче, нужно создать массив размерности n, а, затем, заполнить его значениями от 0 до k. При чём здесь k<n? Эти параметры вообще не пересекаются. В приведенном листинге инициализируется только 0-й элемент массива, а остальные?

[Oscar]

элементы которого не отрицательны и не превышает k.

Прошу прощения, что не превышаЕТ k ?

[AMDemon]

Ошибку увидел.
array[0]=random(10); // инициализация первого
for (i=1;i<n;i++)
array=array[i-1]+random(10); // инициализация остальных, каждый заранее больше предыдущего
А у меня элементов больше миллиона. При таком алгоритме значение элемента на каком-то этапе превышает integer. Массивов у меня много и их упорядочивание длится дольше чем сутки, на большее терпения у меня не хватило.

[Albor]

Может быть стоит сначала заполнить массив, а затем отсортировать его (не методом пузырька, конечно)? И без сложения с предыдущим элементом. Или задача стоит получить неповторяющиеся числа? Если случайное число получать способом остатка от деления на k, то число никогда не превысит предел. Например, если k=565, то случайное число получаем random()*1000%k (random() должна возвращать число от 0 до 1, хотя и не обязательно), результат будет лежать в интервале >=0 и < 565

[Naeel Maqsudov]

А если так:

1. Delta=K/N
2. Для i={0..N-1}: X=i*Delta+Random(0..Delta)

Т.е. заполняем массив линейной функцей i*K/N, но каждому элементу задаем случайный сдвиг на +{0..шаг}.

[DeeJayC]

Naeel Maqsudov, Так делать нельзя - надо исследовать вопрос о распределении и случайности чисел X.

[Naeel Maqsudov]

В задаче про это ничего на сказано. Если считать что функция Random дает числа, появление каждого из которых равновероятно, то предлагаемое решение является как нельзя лучшим.

Этот алгоритм можно улучшить.
Если "окно", задаваемое случайным смещением расширить. Сделать, скажем не +{0..шаг}, а +{0..шаг*2}. То в присвоение X надо будет поставить в еще один вложенный цикл, прерываемый по условию X>=X[i-1]. (Разумеется крайние элементы массива будут являться особыми случаями.)

Можно предположить, что в среднем внутренний цикл будет выполняться 2 раза, так как половина "окна" пересевается с другим окном. Однако, это все равно несравнимо лучше, чем алгоритм с сортировкой на втором проходе.

[Naeel Maqsudov]

О! Можно БЕЗ вложенного цикла обойтись!

Движемся по всему диапазону достаточно большим окном.
Первое значение будет просто случайным в пределах этого окна.
Все последующие - будут случайными в пределах от предыдущего, до верхней границы окна. При максимальном значении I (т.е. I=N) Верхня граница окна должна совпадать с K.


Даже можно еще короче сформулировать:

Тут надо рассчитывать только значение верхней границы окна - это линейная функция от i. Нижняя граница окна равна предыдущему значению X, а для первого шага берется равной 0.

[Naeel Maqsudov]

Вот наиболее общая формулировка моего решения:

Дано:
Kmin,Kmax-предельные значения величины X,
N-количество элементов,
P-ширина окна (0<=P<Kmax). Чем больше P тем "разболтаннее" получится картина. При P=0 результат получится аналогичный предложенному мною в первый раз.

X[-1]=0 //Это начальное условие, а не элемент массива.
i=0..N-1:
X=X[i-1]+random((Kmax-P)*(i+1)/N-X[i-1])+Kmin