eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybki algorytm na permutacjęRe: Szybki algorytm na permutację
  • Data: 2016-04-23 01:54:49
    Temat: Re: Szybki algorytm na permutację
    Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
    [ pokaż wszystkie 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: