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

do góry

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] );

do góry

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

do góry

On 22.04.2016 00:22, 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



Prawie idealnie. Z tym, ze nie potrzebujesz wcale osobnej tablicy,
Masz jedną tablicę, idziesz po niej plętlą

Wszytko co przed indeksem i traktujesz jak swoją drugą tablicę
(tam są losowo zmieszane) a tablice od i (włącznie) w górę
traktujesz jak swoją pierwszą tablicę (źródło nieuzytych liczb).
I robisz tak samo, czyli losujesz z niej jeden element, zamiast
jednak przesyłąć go do innej tablicy i zatykać największym,
przestawiasz go w miejsce i, a dzirę zatykasz tym, co było na miejscu i.

To tzw, "Knuth shuffle".

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_s
huffle#The_modern_algorithm

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n-2 do
j <- random integer such that 0 <= j < n-i
exchange a[i] and a[i+j]

Wydawało mi się, że jest powszechnie znany. Niczym qsort.
To on siedzie (być mozę w wersji 'od tyłu') w std::random_shuffle.

pzdr
bartekltg

do góry

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

do góry

On 23.04.2016 11:38, M.M. wrote:
> 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:


Knutha możęsz policzyć. Bardzo prosto. Wymyśl dowolną
permutację i licz prawdopodobieństwo, że ją wylosujesz.
W każdym kroku musisz wybrać właściwa liczbę i nie ma potem
możliwośći popsucia. 1 liczba z n, 1 liczba z n-1....
Łącznie prawdopodobieństwo 1/n! Identyczne dla dowolnej permutacji.


BTW, dlaczego wołasz srand( seed ); dwa razy?


pzdr
bartekltg

do góry

On Saturday, April 23, 2016 at 11:47:45 AM UTC+2, bartekltg wrote:
> On 23.04.2016 11:38, M.M. wrote:
> > 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:
>
>
> Knutha możęsz policzyć. Bardzo prosto. Wymyśl dowolną
> permutację i licz prawdopodobieństwo, że ją wylosujesz.
> W każdym kroku musisz wybrać właściwa liczbę i nie ma potem
> możliwośći popsucia. 1 liczba z n, 1 liczba z n-1....
> Łącznie prawdopodobieństwo 1/n! Identyczne dla dowolnej permutacji.

Tak, zaletą knutha jest to, że można łatwo przeprowadzić dowód.



> BTW, dlaczego wołasz srand( seed ); dwa razy?
Chyba z rozpędu, zazwyczaj trzeba zadbać o to, aby obie metody dostały
ten sam losowy ciąg, ale tutaj jest inna ilość losowań, więc
nic to nie daje.

Pozdrawiam

do góry