a rand array

[Keith Thompson]

#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >> [...]
/* it is a c++ main */

[...]

Please stop wasting our time.

 

[CBFalconer]

.... snip ...

/* C++ and C but you use a C++ compiler and try ... */
#include <iostream.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define U unsigned
#define F for
#define W while
#define R return
#define os cout <<
#define is cin >>

You have been told many times not to do this here. rePLONK.

 

[RoSsIaCrIiLoIA]

Do has this soulution as result a 'random' array

#define U unsigned
#define F for
#define W while
#define R return

U rand_array2( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, h;
double d, v;
/*---------------------*/
if( a==0||size==0||sup_val<=size )
R 0;
if(i)
{i = 0; srand( (U) time(0) );}

label:
F( j=0, a[0]=UINT_MAX; j<size; ++j)
{
h = _lrand() % sup_val;
if(a[0]>h) a[0] = h;
}
if(a[0] > sup_val - size)
goto label;

d = ( (double)sup_val - a[0] ) / (size - 1);
if( (unsigned) d <= 1u )
a[0] = 0;
for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=(double) a[0] + d*j)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}

like this

void
ArrRand(unsigned* a, unsiged size, unsigned superiore)
{static int m = 1;
unsigned i, j, h, temp;

if(a==0 || size<2 || superiore==0)
return;
if(m)
{ m = 0; srand(time(0));}
for( i = 0; i < size; ++i)
{label:
a = _lrand() % superiore; /*_lrand is for Borland */
for( j = 0; j < i; ++j) /* if not, use your_lrand() */
{if(a == a[j]) goto label;
else if(a < a[j]) /* that fill an unsigned */
{temp = a;
for( h = i; h > j; --h)
a[h] = a[h - 1];
a[j] = temp;
break;
}
}
}
}

? Is it O(N)?
It is a silly function that find random number where to calculate in
a loop e.g.
array(a, 100,7000000);
cont=0; j=0;
while(++cont<7000000 && j<100)
{
if(cont==a[j]){++j; calaculate..}
....
}

 

[Nick Keighley]

int main(void)
{unsigned a[100] = {0}, i;

ArrRand( a, (sizeof a)/(sizeof *a), 80000000);
for( i = 0; i < 99; ++i)

this only prints 99 items

cout << " " << a;
cout << "\n";
return 0;
}

 

[E. Robert Tisdale]

Tools - Message Filters

Sender contains "Default User"

Action = Mark read or Delete or ...

Thanks Grumble,

I just installed Mozilla 1.6 and this seemed to work.

 

[josh]

Mine can
generate all of them, although I suspect the probability distribution
may be different.

thank you
but seems to me there are odd results e.g.
if rand_array is like you suggest =>

inserisci il massimo[0 finisce]> 888888888
inserisci il numero di elementi> 20
312557105 548251158 760618515 876091816 886173925 888503572 888804673
888826177
888871515 888882642 888884513 888885725 888887085 888888029 888888553
888888700
888888768 888888843 888888873 888888877
inserisci il massimo[0 finisce]> 0

This could come out of a "generate random and sort" algorithm, although
most likely with a lower probability than here. Your code below, if I
understand it correctly, cannot generate this sequence given that input.

It looks like it does create sequences with a different probability
distribution. That should be fixable by using something other than a
uniform random number generator, although exactly how non-uniform might
be difficult to figure out.

Another possibility might be to choose the middle element in the array
and then recursivly fill the top and bottom halves, using a similar
method for selecting the upper and lower bounds. Or this can probably
be done iteritavely, but it would take more thought. Either way it'd
still take O(N) time.

rand_array1 seems 'ok'
inserisci il massimo[0 finisce]> 99
inserisci il numero di elementi> 98
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
26 27 28 29
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 5
6 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
80 81 82
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

If I understand your code correctly, this is the only sequence that this
can generate for this input, despite there being ~99 different sequences
that fit the requirements. (eg, 1 2 3 ... 96 97 98)

U intervallo(U a, U b)
{R a + (U) _lrand() % (b-a);}

U rand_array1( U* a, U size, U sup_val )
{static int i = 1;
unsigned j, k, h;
/*---------------------*/
if( a==0 || size<2 || sup_val<=size )
return 0;
if(i)
{i = 0; srand(time(0));}

k = sup_val / size;
a[0] = (k<=1 ? 0 : (U) _lrand() % k);

for( j = 1; j<size; ++j)
a[j] =
(a[j-1]+1 >= (h=j*k)
? a[j-1] + 1
: intervallo( a[j-1] + 1, h)
);
R 1;
}

This code is hurting my brain. I assume it would be equivalent to this?

unsigned intervallo(unsigned low, unsigned high)
{
return low + (unsigned)_lrand() % (high-low);
}

unsigned rand_array1(unsigned *a, unsigned size, unsigned sup_val)
{
static int rand_seeded = 0;
unsigned i, window, limit;

if (a==0 || size<2 || sup_val<=size)
return 0;

if (!rand_seeded)
{
rand_seeded = 1;
srand(time(0));
}

window = sup_val / size;
if (window <= 1)
a[0] = 0;
else
a[0] = intervallo(0, window);

for (i=1; i<size; ++i)
{
limit = i*window;
if (a[i-1]+1 >= limit)
a = a[i-1]+1;
else
a = intervallo(a[i-1]+1, limit);
}
}

It is possible, though extremely unlikely, that a sorted random set of
10 integers in [0, 1000) comes out to:
990 991 992 993 994 995 996 997 998 999

With this code, that is completely impossible.

There's also some rounding issues, where you will never get 996 if you
use a range of [0, 997) for nearly any array size.

-josh

 

[josh]

Another possibility might be to choose the middle element in the array
and then recursivly fill the top and bottom halves, using a similar
method for selecting the upper and lower bounds. Or this can probably
be done iteritavely, but it would take more thought. Either way it'd
still take O(N) time.

This still isn't quite right.

It occurs to me that the center value, which would be the median of the
set, should be close to the average of the set and thus approximately
normal with certain properties. So you need random numbers with a
normal distribution rather than uniform. I'm using code from "The
Ziggurat Method for Generating Random Variables" by George Marsaglia and
Wai Wan Tsang, which should be available online somewhere. (The
included code isn't terribly nice, but the algorithm is.)

From the central limit theorem:
- the sample mean will be the mean of the population
mean = (range_low + range_high)/2;
- the standard deviation of the sample mean will be the standard
deviation of the population / sqrt( sample size )
stddev = pop_stddev / sqrt(size);

from http://mathworld.wolfram.com/UniformDistribution.html
the population variance is (b-a)^2/12, so the population standard
deviation should be (b-a)/sqrt(12) and
stddev = (range_high - range_low) / sqrt(12*size);

so:

#include <math.h> /* for sqrt */

unsigned normal_in_range(unsigned low, unsigned high, double stddev)
{
/* RNOR from the paper mentioned above */
unsigned r = (unsigned)(RNOR * stddev) + (high+low)/2;
if (r >= high) r = high-1;
if (r < low) r = low;
if (r >= high) r = low; /* in case high==0 */
return r;
}

unsigned sorted_random_array_r(
unsigned *base, unsigned index_low, unsigned index_high,
unsigned range_low, unsigned range_high)
{
const unsigned index_mid = (index_low + index_high)/2;
const unsigned count_below = index_mid-index_low;
const unsigned count_above = index_high-index_mid;
double stddev;

if (index_low >= index_high)
return 0;

stddev = (range_high-range_low)/sqrt(12*(index_high-index_low));

base[index_mid] = normal_in_range(range_low+count_below,
range_high-count_above, stddev);

return 1
+ sorted_random_array_r(base, index_low, index_mid,
range_low, base[index_mid])
+ sorted_random_array_r(base, index_mid+1, index_high,
base[index_mid]+1, range_high);
}

/* returns size on success, 0 if inputs are invalid */
unsigned sorted_random_array(unsigned *base,
unsigned size, unsigned range)
{
if (range < size)
return 0;

return sorted_random_array_r(base, 0, size, 0, range);
}

That gives numbers that look very much like a sorted uniformly random
set in (I hope) O(N) time. That is, not only can it generate the same
sequences as a naive "fill and sort" algorithm, it seems to generate
them with the same probability. (as it theoretically should)

One call to sorted_random_array(, 20, 888888888) gives:
41889677, 53715473, 131865038, 207767453, 234227055, 262409187,
277295135, 333417643, 364713486, 414888301, 472025225, 482934207,
490867513, 539655409, 716275231, 755247825, 776187269, 783141470,
814645472, 871172337

A similar call to a naive "fill and sort" algorithm gives:
11622284, 28435660, 103962880, 110241564, 115014999, 211959552,
279580988, 339350979, 480464091, 503398153, 519736592, 521628837,
553710371, 624480689, 629627559, 676032821, 711727532, 809860628,
809976730, 847242980

Looks pretty good to me.

-josh