Re: Szybki algorytm na permutację

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Szybki algorytm na permutację
Date	2016-04-23 01:54 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<nfedka$e74$1@node1.news.atman.pl> (permalink)
References	<nfbjra$fer$1@node2.news.atman.pl>

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous 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