Szathmáry László honlapja @ DEIK

shuffle művelet (tömb elemeinek az összekeverése)

A tömbökkel való munka során előfordulhat, hogy össze szeretnénk keverni a tömb elemeit.

(Matematikusoknak: szeretnénk előállítani a tömb elemeinek egy random permutációját.)

Python-ban ez a következőképpen néz ki:

>>> from random import shuffle
>>>
>>> li = [1, 2, 3, 4, 5, 6, 7, 8]
>>> li
[1, 2, 3, 4, 5, 6, 7, 8]
>>>
>>> shuffle(li)
>>> li
[6, 3, 7, 8, 1, 2, 4, 5]
>>> shuffle(li)
>>> li
[4, 6, 5, 3, 8, 2, 1, 7]

Mint látható, a shuffle() nem ad vissza semmit, hanem helyben módosítja a tömböt (helyben keveri össze az elemeket).

Az algoritmus modern változatának a leírását itt találják: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm .

Az algoritmus pszeudókódja:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

A fentebb linkelt oldalon találnak egy futási példát is az algoritmus működésére (Examples → Modern method).

Feladat

Készítsük el az algoritmus C implementációját.

Az eljárás szignatúrája:

// Durstenfeld's shuffle algorithm
// helyben módosít
void shuffle(int n, int tomb[]);

Implementáljuk az eljárást!

20200416g