Random в C (Си)

[ganselo]

Дан массив:
int *x;
x=new int[n];

Я его заполняю рандомно:

srand(time(NULL));
for (int i=0; i<n; i++)
x[i]=rand()%100;


Как исключить вероятность того, чтобы значение элементов не могли повториться(т.е чтобы элементы были уникальны)??
Я пробовал так:

for (int i=0; i<n; i++)
{
x[i]=rand()%100;
for (int j=0; j<n; j++)
{
if (i!=j)
{
if (x[i]==x[j]) x[i]=rand()%100;
}
}
}

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

[ganselo]

Решил проблему так:


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void proverka(int *x, int key);
void size(int *dig);
int n;
int main()
{
int *x, p=1;
size(&n);
x=new int[n];
srand(time(NULL));
for (int i=0; i<n; i++)
{
x[i]=rand()%100;
proverka(x, i);

}
for (int i=0; i<n; i++)
{
printf ("x[%i]=%i\n", i, x[i]);
}
printf ("\n");

for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (i!=j)
if (x[i]==x[j]) printf ("xI[%i]=%i, xJ[%i]=%i\n", i, x[i], j, x[j]);
}
}
delete [] x;
}


void proverka(int *x, int key)
{
for (int i=0; i<key; i++)
{
if (x[key]==x[i])
{
x[key]=rand()%100;
proverka(x, key);
}
}
}

void size(int *dig)
{
scanf("%i", &*dig);
}


Но думаю это не лучший вариант, т.к при проверки происходит очень много действий.

[Drongo]

А если использовать цикл do\while? Тоесть пока не будет соблюдено условие (все элементы не проверены) или один из них равен сгернерированному раньше, продолжать генерацию чисел до тех пор пока не будет найденно число, которого нет в массиве.
do{
... // код
}while(Условие)

[ganselo]

А если использовать цикл do\while? »
спс попробую.

[pva]

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

int values[200];
for(unsigned n=0; n<200; ++n) values[n] = n;

for(unsigned n=200; 1<n;)
{
int& rand_idx(values[rand() % n]);
printf("%i", rand_idx);
rand_idx = values[--n];
}

printf("%i", values[0]);

такие точно не повторятся

[___oj]

pva, Вот вывод твоего кода:
1134459160191733723168103531901711854108105291224071587942115869261551291771481125010676133331255147 1531215789147186529713019216191341595894612145856519411114511715181997231273188110146139123391691821 0414229026931326678845613671474189223212418415195131128127551701018517568916410117917313725165176196 1201408218062957012610719336301501521987582019787014696316311618399968316611412128171888149172463515 115410264981621491311960135576713819178241877710980111003848431741671411431615614413418141
Повторяющиеся числа есть, а если нету, то не понятно почему.

int& rand_idx(values[rand() % n]);
printf("%i", rand_idx);
rand_idx = values[--n];
»
Поясни пожалуйста, в чем суть этих строчек кода?

P.S Еще вариант

1: #include<conio.h>
2: #include<stdio.h>
3: #include<stdlib.h>
4: #include<time.h>
5: #include<mem.h>
6:
7:
8:
9: int main()
10: {
11: srand(time(NULL));
12:
13: int values[ 200 ], rand_idx=0;
14: memset( &values, (-1), sizeof(values) );
15:
16:
17: for(unsigned n=0; n<200; )
18: {
19: rand_idx = rand() % 200;
20: if( values[ rand_idx ]==-1 ) values[ rand_idx ] = n++;
21: }
22:
23: for(unsigned n=0; n<200; n++ )
24: {
25: printf( "%d ", values[ n ] );
26: }
27: return 0;
28: }

[ganselo]

я советую алгоритм хитрее: »
P.S Еще вариант »
Всё хорошо, но тут интервал чисел в массиве будит зависить от размерности массива
(т.е если size=10, то значения x[0], x[1]...x[size] будит пренадлежать интервалу [0, size]). В случае если мне понадобится массив из 10 элементов со зна4ениями на интервале [100, 200] этот вариант я так понимаю не подойдёт?

[Busla]

Надо создать два алгоритма:
для случая когда размерность массива и интервала допустимых значений примерно равны - перетасовать массив
и когда интервал допустимых значений гораздо больше размерности массива - просто рандомно заполнять, проверяя - нет ли уже таких значений в массиве.
Чтобы проверка работала быстрее - создать два массива - один итоговый, второй - своеобразный индекс - где полученные рандомные значения хранятся в порядке возрастания. Т.к. поис по упорядоченному множеству проходит гораздо быстрее.

[___oj]

о тут интервал чисел в массиве будит зависить от размерности массива » Ни в коем случае.

Сорри, будит зависеть.

[ganselo]

Ни в коем случае. »

Пусть размерность массива равна 20,
а масштаб рандомизации я выбрал 200 (т.е рандом будит возврощать значения от 0 до 200 (0<=rand<=200))


for(unsigned n=0; n<50; )
{
rand_idx = rand() % 200;
if( values[ rand_idx ]==-1 ) values[ rand_idx ] = n++;
}


В случае когда мы выбираем слу4айно индекс массива на интервале [0, 200] (rand_idx = rand() % 200; ) и этот индекс больше размерности массива
то мы начинаем проверять с несуществующем элементом массива if( values[ rand_idx ]==-1 ) values[ rand_idx ] = n++;, т.е тут n не увеличится на еденицу.
И следовательно n будит увеличиватся только тогда, когда rand выберит число находящееся на интервале [0, до размерности массива].
Следовательно n увеличится ровно столько раз сколько будит равна размерность массива. И поэтому значение элементов массива не будит превосхадить размерности массива.

[___oj]

Следовательно n увеличится ровно столько раз сколько будит равна размерность массива. И поэтому значение элементов массива не будит превосхадить размерности массива. »
Ты прав, в том примере случайно не число, а индекс в массиве.

Тогда такой вариант:

1: #include<conio.h>
2: #include<stdio.h>
3: #include<stdlib.h>
4: #include<time.h>
5: #include<mem.h>
6:
7:
8:
9: #define ASIZE 200
10: #define RANDOMSID 500
11:
12: int main()
13: {
14: srand(time(NULL));
15: int values[ ASIZE ], random_id[ RANDOMSID ], randomiza, i, j;
16:
17: memset( &random_id, 0, sizeof(random_id) );
18:
19:
20: for( i=0, j=0, randomiza=0; i<ASIZE; )
21: {
22: randomiza = rand() % RANDOMSID;
23: if( !random_id[ randomiza ] )
24: {
25: random_id[ j++ ] = 1;
26: values[ i++ ] = randomiza;
27: }
28: }
29:
30: for(unsigned n=0; n<200; n++ )
31: {
32: printf( "%d ", values[ n ] );
33: }

[pva]

Извияюсь, что в прошлом примере не поставил разделитель при выводе на экран, чем сбил столку. Иногда не проверяю код :-[
Для случая когда диапазон гораздо больше последовательности, которую надо выдать, предлагаю очередной "хитрый" способ:

// Опять же предполагаю, что число возможных комбинаций не меньше числа требуемых
// Снова используем принцип случайного перемешивания.
// Но на этот раз хитро делаем выборку. Главное - чтобы она была отсортирована и без повторений.
// использую C++, если возникнут вопросы - переведу на С

static const int rand_range = 500;
static const unsigned rand_count = 200;

// допустим мы уже получили все комбинации и отсортировали их по возрастанию
// рассчитаем вероятность того, что ра расстояние между соседними двумя < x
// пусть числа выпадают с равномерным на [0,M] распределением
// вероятность что число попадёт N раз в отрезок [X,M] равна ((M-X)/M)^N
// тогда вероятность что при N испытаниях расстояние до ближайшего значения_
// будет X равно F(X) = 1 - ((M-X)/M)^N
// по теореме http://www.nsu.ru/mmf/tvims/chernova/tv/lec/node32.html#SECTION000821
// генерируем случайную величину, которая задаёт расстояния между значениями
// dX = (M - X)*(1 - (1 - R)^(1/N))
// где R - равномерно распределённая на [0,1] величина.
// суммируя dX получаем строго возрастающую последовательность

vector<int> rands(rand_count);

{ // заполняем
int prev = 0;

for (unsigned count=rands.size(); 0<--count; )
{
// dX = (M - X)*(1 - (1 - R)^(1/N))
// стараемся сделать так, чтобы хватило места для последующих элементов /*1*/

prev += (double(rand_range - count /*1*/) - double(prev)) *
(1. - pow(1. - double(rand())/RAND_MAX), 1./count));

rands[count] = prev;

// на единицу смещаем чтобы не выпало одинаковых значений,
// т.к. данное распределение при округлении может давать 0
++prev;
}
rands[0] = (double(rand_range) - double(prev)) *(double(rand())/RAND_MAX);
}

// перемешиваем
for (unsigned count=rands.size(); 0<--count; )
{
std::swap(first[rand() % count], first[count]);
}

// вывод в stdout
for(unsigned count=0; count<rands.size(); ++count)
{
std::cout << rands[count] << "\n";
}

[ganselo]

предлагаю очередной "хитрый" способ: »
Спасибо всё работает если возникнут вопросы - переведу на С »
Не стоит... всё понятно.