Ruby. Receptury

4.10. Tasowanie tablicy

Problem

Chcemy zmienić uporządkowanie elementów tablicy w sposób losowy.

Rozwiązanie

Najprościej można to uczynić, sortując tablicę według losowego klucza (w wersji 1.8 lub nowszej języka Ruby):

[1,2,3].sort_by { rand }    # => [1, 3, 2]

Dyskusja

Trudno zarzucić przedstawionemu rozwiązaniu brak zwięzłości, można natomiast kwestionować jego efektywność. Jak wiadomo, sortowanie n-elementowej tablicy wymaga w przeciętnym przypadku O(n log n) przestawień elementów; w celu potasowania zawartości tablicy wystarczy natomiast wstawić losowo wybrany element na każdą z n pozycji, co wymaga jedynie n przestawień.

class Array def shuffle! each_index do |i| j = rand(length-i) + i self[j], self[i] = self[i], self[j] end ...