Shuffling an Array

2017-11-03 09:05:06

Problem

You want to put the elements of an array in random order.

Solution

The simplest way to shuffle an array (in Ruby 1.8 and above) is to sort it randomly:

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

This is not the fastest way, though.

Discussion

It's hard to beat a random sort for brevity of code, but it does a lot of extra work. Like any general sort, a random sort will do about n log n variable swaps. But to shuffle a list, it suffices to put a randomly selected element in each position of the list. This can be done with only n variable swaps.

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

If you're shuffling a very large list, either Array#shuffle or Array#shuffle! will be significantly faster than a random sort. Here's a real-world example of shuffling using Array#shuffle:

class Card def initialize(suit, rank) @suit = suit @rank = rank end def to_s "#{@suit} of #{@rank}" end end class Deck < Array attr_reader :cards @@suits = %w{Spades Hearts Clubs Diamonds} @@ranks = %w{Ace 2 3 4 5 6 7 8 9 10 Jack Queen King} def initialize @@suits.each { |suit| @@ranks.each { |rank| self << Card.new(rank, suit) } } end end deck = Deck.new deck.collect { |card| card.to_s } # => ["Ace of Spades", "2 of Spades", "3 of Spades", "4 of Spades",…] deck.shuffle! deck.collect { |card| card.to_s } # => ["6 of Clubs", "8 of Diamonds", "2 of Hearts", "5 of Clubs",…]

Категории