How slice an array while avoiding duplicate values in each slice?

Question

Suppose I have this array:

a = [1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7,8,9,10,11]

a.each_slice(2).to_a will generate pairs, but these pairs will contain non-unique values like [3,3]. So I guess I'm looking for some sort of unique_each_slice method.

What I want is to be able to keep shuffling this array until I get to a point where I have unique pairs of 2 (doesn't have to be 2, can be anything), like this (using 2 an example):

[3, 1, 3, 7, 6, 3, 4, 5, 8, 3, 9, 3, 2, 3, 6, 3, 3, 11, 10, 3]

If you do each_slice(2) on this array, you'll get unique pairs:

[[3, 1], [3, 7], [6, 3], [4, 5], [8, 3], [9, 3], [2, 3], [6, 3], [3, 11], [10, 3]]

compared to the original where you have:

[[1, 2], [3, 3], [3, 3], [3, 3], [3, 3], [3, 4], [5, 6], [6, 7], [8, 9], [10, 11]]

with non-unique pairs in each, like [3,3]

Another example, suppose I have:

a = [1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7,8,9,10,11,12,13,14,15,16,17]

Now, supposing, there's some function a.unique_slices_of(3), I'd get:

[[4, 16, 3], [1, 9, 3], [3, 6, 17], [3, 6, 10], [15, 3, 2], [3, 8, 12], [11, 3, 14], [7, 13, 3], [3, 5]]

By "unique slice" I mean a slice where the same number doesn't repeat twice: [1,2,3] is a unique slice, [3,1,3] is not.

So far I've come with the following method which seems to take several iterations before it gets things right:

class Array
  def unique_slices_of!(slices)
    loop do
      unique = true
      self.each_slice(slices) do |slice|
        if slice != slice.uniq
          self.shuffle!
          unique = false # so we know whether to loop again
          break
        end
      end
      break if unique # if unique didn't change, that means all slices were equal
      if unique == false then unique == true end # reset and start again
    end
    self 
  end
end

The major problem with my code is that a) I don't think I'm using some idiomatic Ruby method which can shorten this process in half or more. b) The possibility for an infinite loop if the array simply cannot contain unique slices. I'd probably need to use some theory of combinations here, but I'm not sure how.

Answer 1

a = [1,2,3,3,3,3,3,3,3,3,3,4,5,6,6,7,8,9,10,11]

You can test if slices are "unique" by:

a.each_slice(2).all?{|x| x == x.uniq}

So now you just shuffle until you get what you want:

a.shuffle! until a.each_slice(2).all?{|x| x == x.uniq}

The easiest way to avoid an infinite loop is with timeout:

require 'timeout'
# raise an error if it takes more than 1 second
timeout(1){ a.shuffle! until a.each_slice(3).all?{|x| x == x.uniq} }