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 simplest way (without any random):

# Calculate letter frequency
freq = arr.group_by { |h| h[:letter] }.map { |k, v| [k, v.size] }.to_h

# Then check that the most frequent element occurs less that arr.size / 2
center = (arr.size + 1) / 2
if freq.values.max > center
  # Impossible
end

# Sort array by frequency to have most frequent first.
sarr = arr.sort_by { |h| freq[h[:letter]] }.reverse

sarr[0..center-1].zip(sarr[center..-1]).flatten.compact

Your problem is a special case of this question. See my answer for the detailed explanation how this works.

---

We even don't need to sort by letter frequency. It's for corner cases like "abbcccc". We can solve them in another way:

# Works with correct data: most frequent letter occurs <= center times
def f(arr)
  arr = arr.sort
  center = (arr.size + 1) / 2
  arr = arr[0..center-1].zip(arr[center..-1]).flatten.compact
  double = (1..arr.size-1).find { |i| arr[i] == arr[i-1] }
  double ? arr.rotate(double) : arr # fix for the corner cases
end

puts f(%w[a a a a b b c].shuffle).join
# ababaca
puts f(%w[a a b b b b c].shuffle).join
# bcbabab
puts f(%w[a b b c c c c].shuffle).join
# cacbcbc

The only non-linear part of the algorithm is arr.sort. But as you can see by the link above, we even don't need the sorting. We need letters counts, which could be found in linear time. Therefore, we can reduce the algorithm to O(n).

---

The number of repeated letters in the array is precisely known - it's 20% of the array length.

With this update, the algorithm is simplified to (as there are no corner cases):

sarr = arr.sort_by { |h| h[:letter] }
center = (arr.size + 1) / 2
sarr[0..center-1].zip(sarr[center..-1]).flatten.compact