On Saturday, April 23, 2016 at 1:47:09 AM UTC+2, bartekltg wrote:
> On 22.04.2016 18:43, M.M. wrote:
> > On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
> >> z wykorzystaniem random()
> >> Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
> >> drugą, początkowo wielkości 0.
> >> Z posortowanych wybieram za pomocą random(n) któryś element, i
> >> najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
> >> element ostatni.
> >> Potem wybieram za pomocą random(n-1) wkładam w dziurę.
> >> I tak dalej
>
> >
> > Może tak?
> > for( int i=1 ; i<=N ; i++ )
> > tab[i] = i;
> > for( int i=0 ; i<N*2 ; i++ )
> > swp( tab[rand()%N] , tab[rand()%N] );
>
> Bardzo źle.
> Wynonujesz 4N losowań.
> Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.
>
> pzdr
> bartekltg

Nie wiem, też bym się nie założył, ale na pewno Knuth shuffle dał
mniejsze odchylenie standardowe w kilku testach:


#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <QHash>
#include <QString>
#include <cmath>

#define N (10000000)
#define M (5)

static void swp( int &a , int &b ) {
const int x = a;
a = b;
b = x;
}

static QHash<QString,int> test1() {
QHash<QString,int> hash;
for( int i=0 ; i<N ; i++ ) {
int tab[M];
for( int j=0 ; j<M ; j++ )
tab[j] = j;
for( int j=0 ; j<M*2 ; j++ )
swp( tab[rand()%M] , tab[rand()%M] );
QString p;
for( int j=0 ; j<M ; j++ )
p.append( QString::number(tab[j]) );
if( hash.contains(p) )
hash[p]++;
else
hash.insert(p,1);
}
return hash;
}


static QHash<QString,int> test2() {
QHash<QString,int> hash;
for( int i=0 ; i<N ; i++ ) {
int tab[M];
for( int j=0 ; j<M ; j++ )
tab[j] = j;
for( int j=0 ; j<M-1 ; j++ )
swp( tab[j] , tab[ j + rand()%(M-j) ] );
QString p;
for( int j=0 ; j<M ; j++ )
p.append( QString::number(tab[j]) );
if( hash.contains(p) )
hash[p]++;
else
hash.insert(p,1);
}
return hash;
}


static void stat( const QHash<QString,int> &hash ) {
double sum=0, sum2=0, avg, cnt=0, min=1, max=0;
for( QHash<QString,int>::const_iterator i=hash.begin() ; i!=hash.end() ; ++i ) {
const double tmp = (double) i.value() / N;
sum += tmp;
cnt ++ ;
if( min > tmp ) min = tmp;
if( max < tmp ) max = tmp;
}
avg = sum / cnt;
for( QHash<QString,int>::const_iterator i=hash.begin() ; i!=hash.end() ; ++i ) {
const double tmp = (double) i.value() / N;
sum2 += (tmp-avg) * (tmp-avg);
}

printf("cnt=%.0lf sum=%lf min=%lf max=%lf avg=%lf std=%lf\n" , cnt , sum , min ,
max , avg , sqrt( sum2 / cnt ) );
fflush(stdout);

}

int main(int argc, char *argv[])
{
const uint seed = (uint)time(NULL);
printf("seed = %u\n",seed);

srand( seed );
{
const QHash<QString,int> hash = test1();
stat(hash);
}

srand( seed );
{
const QHash<QString,int> hash = test2();
stat(hash);
}

return 0;
}

seed = 1461404107
cnt=120 sum=1.000000 min=0.008029 max=0.009185 avg=0.008333 std=0.000209
cnt=120 sum=1.000000 min=0.008270 max=0.008425 avg=0.008333 std=0.000029