eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybki algorytm na permutacjęRe: Szybki algorytm na permutację
  • Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!.POSTED!not-for-mail
    From: bartekltg <b...@g...com>
    Newsgroups: pl.comp.programming
    Subject: Re: Szybki algorytm na permutację
    Date: Sat, 23 Apr 2016 01:54:49 +0200
    Organization: ATMAN - ATM S.A.
    Lines: 37
    Message-ID: <nfedka$e74$1@node1.news.atman.pl>
    References: <nfbjra$fer$1@node2.news.atman.pl>
    NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset=utf-8; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: node1.news.atman.pl 1461369290 14564 89.73.81.145 (22 Apr 2016 23:54:50 GMT)
    X-Complaints-To: u...@a...pl
    NNTP-Posting-Date: Fri, 22 Apr 2016 23:54:50 +0000 (UTC)
    User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
    Thunderbird/38.6.0
    In-Reply-To: <nfbjra$fer$1@node2.news.atman.pl>
    Xref: news-archive.icm.edu.pl pl.comp.programming:209337
    [ ukryj nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

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: