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

Groups > pl.comp.programming > #28522

Re: Szybki algorytm na permutację

From bartekltg <bartekltg@gmail.com>
Newsgroups pl.comp.programming
Subject Re: Szybki algorytm na permutację
Date 2016-04-23 11:47 +0200
Organization ATMAN - ATM S.A.
Message-ID <nffgc0$foj$1@node1.news.atman.pl> (permalink)
References <nfbjra$fer$1@node2.news.atman.pl> <50b1e418-8178-4dbe-924c-735ceda5e398@googlegroups.com> <nfed5s$4oo$1@node2.news.atman.pl> <dd2bde62-021b-4413-8613-026730ce10e3@googlegroups.com>

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web