eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybki algorytm na permutacjęRe: Szybki algorytm na permutację
  • Data: 2016-04-23 12:10:05
    Temat: Re: Szybki algorytm na permutację
    Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: