Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28514 > unrolled thread

Szybki algorytm na permutację

Started byBorneq <borneq@antyspam.hidden.pl>
First post2016-04-22 00:22 +0200
Last post2016-04-23 01:54 +0200
Articles 7 — 3 participants

Back to article view | Back to pl.comp.programming

Contents

  Szybki algorytm na permutację Borneq <borneq@antyspam.hidden.pl> - 2016-04-22 00:22 +0200
    Re: Szybki algorytm na permutację "M.M." <mmarszik@gmail.com> - 2016-04-22 09:43 -0700
      Re: Szybki algorytm na permutację bartekltg <bartekltg@gmail.com> - 2016-04-23 01:47 +0200
        Re: Szybki algorytm na permutację "M.M." <mmarszik@gmail.com> - 2016-04-23 02:38 -0700
          Re: Szybki algorytm na permutację bartekltg <bartekltg@gmail.com> - 2016-04-23 11:47 +0200
            Re: Szybki algorytm na permutację "M.M." <mmarszik@gmail.com> - 2016-04-23 03:10 -0700
    Re: Szybki algorytm na permutację bartekltg <bartekltg@gmail.com> - 2016-04-23 01:54 +0200

#28514 — Szybki algorytm na permutację

FromBorneq <borneq@antyspam.hidden.pl>
Date2016-04-22 00:22 +0200
SubjectSzybki algorytm na permutację
Message-ID<nfbjra$fer$1@node2.news.atman.pl>
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

[toc] | [next] | [standalone]

#28517

From"M.M." <mmarszik@gmail.com>
Date2016-04-22 09:43 -0700
Message-ID<50b1e418-8178-4dbe-924c-735ceda5e398@googlegroups.com>
In reply to#28514
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] );

[toc] | [prev] | [next] | [standalone]

#28519

Frombartekltg <bartekltg@gmail.com>
Date2016-04-23 01:47 +0200
Message-ID<nfed5s$4oo$1@node2.news.atman.pl>
In reply to#28517
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

[toc] | [prev] | [next] | [standalone]

#28521

From"M.M." <mmarszik@gmail.com>
Date2016-04-23 02:38 -0700
Message-ID<dd2bde62-021b-4413-8613-026730ce10e3@googlegroups.com>
In reply to#28519
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

[toc] | [prev] | [next] | [standalone]

#28522

Frombartekltg <bartekltg@gmail.com>
Date2016-04-23 11:47 +0200
Message-ID<nffgc0$foj$1@node1.news.atman.pl>
In reply to#28521
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

[toc] | [prev] | [next] | [standalone]

#28523

From"M.M." <mmarszik@gmail.com>
Date2016-04-23 03:10 -0700
Message-ID<22e93328-8aee-4c82-9764-f3f736b3aeb0@googlegroups.com>
In reply to#28522
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

[toc] | [prev] | [next] | [standalone]

#28520

Frombartekltg <bartekltg@gmail.com>
Date2016-04-23 01:54 +0200
Message-ID<nfedka$e74$1@node1.news.atman.pl>
In reply to#28514
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_shuffle#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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web