Shuffling an Array

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",…]

 

See Also

• Recipe 2.5, "Generating Random Numbers"
• The Facets Core library provides implementations of Array#shuffle and Array#shuffle!