class Array 
  def rand 
    uniqs = self.select{|e| e.uniq.size == e.size}
    uniqs.empty? ? self[Kernel.rand(length)] : uniqs[Kernel.rand(uniqs.length)]
  end
  
  def unordered_include?(other)
    self.map{|e| e.map{|s| s.to_s}.sort}.include? other.map{|s| s.to_s}.sort
  end  
end

class Hash
  def comb(group_size)
    result = []    
    inner_comb = lambda do |head,tail|
      tail[0..-(group_size-head.size)].each do |e|
        if (head.size >= group_size-1)
          tail.each {|t| result << head + [t]}
        else
          inner_comb[head + [e], tail[tail.index(e)+1..-1]] 
        end
      end
    end
    inner_comb[[],self.inject([]) {|a,v| v[1].times{a <<v[0]}; a}]
    result.uniq    
  end
  
  def remove_set(set)
    set.each {|e| self[e] -= 1}
  end  
end

def mix_and_match(candles, recipients, candles_per_recipient)
  return ERROR_STRING if ((candles.values.inject{|a,v| a+v}) < (recipients.size * candles_per_recipient))
  candle_set = recipients.inject({}) do |a,v|
    tried = []
    tries = 0
    loop do
      random_pick = candles.comb(candles_per_recipient).rand
      tried << random_pick unless tried.unordered_include? random_pick
      break unless a.values.unordered_include? random_pick
      break if (tries+=1) > candles.values.size * 2 #not perfect, but good enough
    end
    candles.remove_set(tried.last)
    a[v] = tried.last
    a  
  end
  candle_set.merge({:extra => candles})
end