algorithm - Ruby. Shuffle the array so that there are no adjacent elements with the same value

Question

An array of hashes is given (10 elements at least):

arr = [{letter: "a", number: "1"}, {letter: "a", number: "3"}, {letter: "b", number: "4"}, {letter: "b", number: "1"}, ..., {letter: "e", number: "2"} ]

The task is to shuffle the array so that there are no adjacent elements with the same 'letter' value.

So, the result should be like the following:

[{letter: "c", number: "4"}, {letter: "a", number: "1"}, {letter: "e", number: "2"}, {letter: "b", number: "1"}, ..., {letter: "a", number: "3"} ]

What is the simplest way to do that?

=== UPDATE ===

The number of repeated letters in the array is precisely known - it's 20% of the array length. So, the array looks like the following:

[
{letter: "a", number: "1"}, {letter: "a", number: "3"}, 
{letter: "b", number: "4"}, {letter: "b", number: "1"},
{letter: "c", number: "7"}, {letter: "c", number: "3"},
{letter: "d", number: "6"}, {letter: "d", number: "4"},
{letter: "e", number: "5"}, {letter: "e", number: "2"}
]

Or, its simplified version:

["a", "a", "b", "b", "c", "c", "d", "d", "e", "e"]

Or, for example, there is a simplified array containing 15 elements:

["a", "a", "a", "b", "b", "b", "c", "c", "c", "d", "d", "d", "e", "e", "e"]

Answer 1

The simple and maybe the less effective way could be the brute force.

So on a simplified version of the array, one can do:

ary = %w(a a c c b a s)

loop do
  break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
end

Some check should be added to assure that a solution exists, to avoid infinite loop.

---

Other (better?) way is to shuffle then find the permutation (no infinite loop) which satisfy the condition:

ary.shuffle!    
ary.permutation.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }

If a solution does not exist, it returns nil.

---

Run the the benchmark:

def looping
  ary = %w(a a c c b a s)
  loop do
    break if ary.shuffle!.slice_when { |a, b| a == b }.to_a.size == 1
  end
  ary
end

def shuffle_permute
  ary = %w(a a c c b a s)
  ary.shuffle!
  ary.permutation.lazy.find { |a| a.slice_when { |a, b| a == b }.to_a.size == 1 }
end

require 'benchmark'

n = 500
Benchmark.bm do |x|
  x.report { looping }
  x.report { shuffle_permute }
end