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

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

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.

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.

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

Code

def reorder(arr)
  groups = arr.group_by { |h| h[:letter] }
  return nil if 2 * groups.map { |_,v| v.size }.max > arr.size + 1
  max_key = groups.max_by { |_,a| a.size }.first
  letters = ([max_key] + (groups.keys - [max_key])).cycle
  ordered = []
  while ordered.size < arr.size
    k = letters.next
    ordered << groups[k].pop unless groups[k].empty?
  end
  ordered
end

nilis returned if it is not possible to rearrange the elements in such a way that g[:letter] != h[:letter] for all pairs of consecutive elements g and h.

Note that this method has near linear computational complexity, O(arr.size), "near" because hash lookups are not quite constant time.

If desired, one could call the method with arr randomized: reorder(arr.shuffle).

Example

arr = [
  { letter: "a" }, { letter: "e" }, { letter: "b" }, { letter: "b" },
  { letter: "e" }, { letter: "a" }, { letter: "a" }, { letter: "f" } 
]

reorder(arr)
  #=> [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
  #    {:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"a"}]

Proof

The assertion is that if the line

return nil if 2 * groups.map { |_,v| v.size }.max > arr.size + 1

were removed from the method the array returned by the method would have the property that for all pairs of successive elements, g, h, g[:letter] != h[:letter] if and only if

2 * groups.map { |_,v| v.size }.max <= arr.size + 1

The proof has two parts.

The above inequality holds if the method produces a valid array

Compute

max_key = groups.max_by { |_,a| a.size }.first
max_key_freq = groups.map { |_,v| v.size }.max

and assume a valid array is returned. There must be at least one element other than max_key between each successive value of max_key in that array. The number of elements of arr other than max_key must therefore be at least max_key_freq - 1, so that

max_key_freq + max_key_freq - 1 <= arr.size

Hence,

2 * max_key_freq <= arr.size + 1

which is the same as:

2 * groups.map { |_,v| v.size }.max <= arr.size + 1

The above inequality does not hold if the method produces an invalid array

Suppose ordered is returned and it contains successive elements g and h for which both g[:letter] and h[:letter] equal the same letter l.

Because of the way ordered is constructed:

• groups[k] must be empty for all keys k in groups for which k != l;
• f[:letter] must equal l for all elements of ordered following g (if there are any); and
• l must be the first key enumerated by keys, which is a letter that appears with a frequency that is not less than that of any other letter. l has frequency groups.map { |_,v| v.size }.max.

If n = groups.keys.size there must be a non-negative integer k (loosely, the number of rounds of allocations for all keys of groups) such that the number of elements h of arr for which h[:letter] != l equals k*n and the number of elements h of arr for which h[:letter] == l is k*n + 2 + m, where m >= 0. The size of arr is therefore 2*k*n + 2 + m.

In that case,

2 * groups.map { |_,v| v.size }.max > arr.size + 1
-> 2 * (k*n + 2 + m) > (k*n + 2 + m + k*n) + 1
-> 2*k*n + 4 + 2*m > 2*k*n + 3 + m
-> (4-3) + m > 0
-> true

Explanation

For the example,

groups = arr.group_by { |h| h[:letter] }
  #=> {"a"=>[{:letter=>"a"}, {:letter=>"a"}, {:letter=>"a"}],
  #    "e"=>[{:letter=>"e"}, {:letter=>"e"}],
  #    "b"=>[{:letter=>"b"}, {:letter=>"b"}],
  #    "f"=>[{:letter=>"f"}]}

The following tells us that a solution exists.

2 * groups.map { |_,v| v.size }.max > arr.size + 1
  #=> 2 * [3, 2, 2, 1].max > 8 + 1
  #=> 2 * 3 > 9
  #=> 6 > 9
  #=> false

Next create an enumerator letters.

  max_key = groups.max_by { |_,a| a.size }.first
    #=> "a"
  letters = ([max_key] + (groups.keys - [max_key])).cycle
    #=> #<Enumerator: ["a", "e", "b", "f"]:cycle>

The elements of letters are generated as follows.

letters.next #=> "a"
letters.next #=> "e"
letters.next #=> "b"
letters.next #=> "f"
letters.next #=> "a"
letters.next #=> "e"
... ad infinititum

See Array#cycle.

I can best explain the remaining calculations by salting the method with puts statements before running the method. Note that arr.size #=> 8.

def reorder(arr)
  groups = arr.group_by { |h| h[:letter] }
  puts "groups = #{groups}"
  return nil if 2 * groups.map { |_,v| v.size }.max > arr.size + 1
  max_key = groups.max_by { |_,a| a.size }.first
  letters = ([max_key] + (groups.keys - [max_key])).cycle
  ordered = []
  while ordered.size < arr.size
    puts "\nordered.size = #{ordered.size} < #{arr.size} = #{ordered.size < arr.size}" 
    k = letters.next
    puts "k = #{k}"
    puts "groups[#{k}].empty? = #{groups[k].empty?}"
    ordered << groups[k].pop unless groups[k].empty?
    puts "ordered = #{ordered}"
    puts "groups = #{groups}"
  end
  ordered
end

reorder(arr)
  #=> [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
  #    {:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"a"}]

The following is displayed.

groups = {"a"=>[{:letter=>"a"}, {:letter=>"a"}, {:letter=>"a"}],
          "e"=>[{:letter=>"e"}, {:letter=>"e"}],
          "b"=>[{:letter=>"b"}, {:letter=>"b"}],
          "f"=>[{:letter=>"f"}]}

ordered.size = 0 < 8 = true
k = a
groups[a].empty? = false
ordered = [{:letter=>"a"}]
groups = {"a"=>[{:letter=>"a"}, {:letter=>"a"}],
          "e"=>[{:letter=>"e"}, {:letter=>"e"}],
          "b"=>[{:letter=>"b"}, {:letter=>"b"}],
          "f"=>[{:letter=>"f"}]}

ordered.size = 1 < 8 = true
k = e
groups[e].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}]
groups = {"a"=>[{:letter=>"a"}, {:letter=>"a"}],
          "e"=>[{:letter=>"e"}],
          "b"=>[{:letter=>"b"}, {:letter=>"b"}],
          "f"=>[{:letter=>"f"}]}

ordered.size = 2 < 8 = true
k = b
groups[b].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}]
groups = {"a"=>[{:letter=>"a"}, {:letter=>"a"}],
          "e"=>[{:letter=>"e"}],
          "b"=>[{:letter=>"b"}],
          "f"=>[{:letter=>"f"}]}

ordered.size = 3 < 8 = true
k = f
groups[f].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"}]
groups = {"a"=>[{:letter=>"a"}, {:letter=>"a"}],
          "e"=>[{:letter=>"e"}], "b"=>[{:letter=>"b"}],
          "f"=>[]}

ordered.size = 4 < 8 = true
k = a
groups[a].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
           {:letter=>"a"}]
groups = {"a"=>[{:letter=>"a"}],
          "e"=>[{:letter=>"e"}],
          "b"=>[{:letter=>"b"}],
          "f"=>[]}

ordered.size = 5 < 8 = true
k = e
groups[e].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
           {:letter=>"a"}, {:letter=>"e"}]
groups = {"a"=>[{:letter=>"a"}],
          "e"=>[],
          "b"=>[{:letter=>"b"}],
          "f"=>[]}

ordered.size = 6 < 8 = true
k = b
groups[b].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
           {:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}]
groups = {"a"=>[{:letter=>"a"}], "e"=>[], "b"=>[], "f"=>[]}

ordered.size = 7 < 8 = true
k = f
groups[f].empty? = true
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
           {:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}]
groups = {"a"=>[{:letter=>"a"}], "e"=>[], "b"=>[], "f"=>[]}

ordered.size = 7 < 8 = true
k = a
groups[a].empty? = false
ordered = [{:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"f"},
           {:letter=>"a"}, {:letter=>"e"}, {:letter=>"b"}, {:letter=>"a"}]
groups = {"a"=>[], "e"=>[], "b"=>[], "f"=>[]}

Refering to the revised question, if

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

one could simply write:

arr.each_slice(arr.index { |s| s != arr.first }.to_a.transpose.flatten
  #=> ["a", "b", "c", "d", "e", "a", "b", "c", "d", "e"]

or

arr.each_slice(arr.count(arr.first)).to_a.transpose.flatten

This sounds a lot like backtracking.

I would build the "shuffled" array from left to right.

Assume that there are N elements in the array. Say that at some point during the algorithm, you have already the first k elements arranged to fulfil the condition.

Now you pick from the remaining (N-k) elements the first one, which you can append to your result array, without breaking the condition.

If you can find one, you repeat the process recursively, now having an result array of (k+1) elements.

If you can not find one, you return a failure indicator and let the caller (i.e. the previous recursion) try another choice.