[SUMMARY] Mix and Match (#186)

_This week's summary is provided by Peter, originally [posted to his =20
blog][1]. I am providing it here with permission._

[1]: http://www.rubyrailways.com/ruby-quiz-mix-and-match/


In my interpretation, this is a simple combinatorial problem: say the =20=

number of recipients is `r` and candles per recipient is `c`, then you =20=

are looking for a (preferably non-repeating) random selection of `r` =20
elements of `c`-combinations of the original set of candles. (In fact =20=

it=92s a bit more complicated than that: the `c`-combinations have to be =
=20
recalculated from the remaining candles each time you give away a =20
group of candles, so we=92ll get to that). Sounds confusing? Don=92t =20
worry, after the implementation everything will be clear!

So first, define a k-combination for a histogram (a Hash like candles =20=

above, where keys are elements and values are cardinalities):

     class Hash
       def comb(group_size)
         result =3D []
         inner_comb =3D lambda do |head,tail|
           tail[0..-(group_size-head.size)].each do |e|
             if (head.size >=3D 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

For example:

     candles =3D { :orange   =3D> 2,
                 :vanilla  =3D> 1,
                 :lavender =3D> 1,
                 :garden =3D> 1 }

     pp candles.comb(3)

     =3D> [[:lavender, :garden, :orange],
         [:lavender, :garden, :vanilla],
         [:lavender, :orange, :orange],
         [:lavender, :orange, :vanilla],
         [:garden, :orange, :orange],
         [:garden, :orange, :vanilla],
         [:orange, :orange, :vanilla]]

So, for a set of candles, this method generates all possible 3-=20
combinations of the candles. We can then pick one and assign it to one =20=

of the recipients. Then recalculate the above from the remaining =20
candles, give it to the next recipient - and so on and so forth. =20
That=92s the basic idea, but we also need to ensure the candle =20
combinations are as non-repeating as possible. So let=92s define some =20=

further utility methods:

     class Hash
       def remove_set(set)
         set.each {|e| self[e] -=3D 1}
       end
     end

The above code adjusts the number of candles in the original hash once =20=

we give away some of them. So for example:

     candles =3D { :orange   =3D> 2,
                 :vanilla  =3D> 1,
                 :lavender =3D> 1,
                 :garden =3D> 1 }

     candles.remove_set([:orange,:orange,:lavender])
     p candles
     =3D> {:lavender=3D>0, :garden=3D>1, :orange=3D>0, :vanilla=3D>1}

And some Array extensions:

     class Array
       def rand
         uniqs =3D self.select{|e| e.uniq.size =3D=3D e.size}
       uniqs.empty? ? self[Kernel.rand(length)] : =20
uniqs[Kernel.rand(uniqs.length)]
       end

       def unordered_include?(other)
         self.map{|e| e.map{|s| s.to_s}.sort}.include? other.map{|s| =20
s.to_s}.sort
       end
     end

`Array#rand` is trying to pick a random non-repeating combination if =20
there is one (e.g. `[:orange, :lavender, :garden]`) or, if there is no =20=

such combination, then just a random one (e.g. =20
`[:orange, :orange, :garden]` - orange is repeating, but we have no =20
other choice).

`Array#unordered_include?` is like normal `Array#include?`, but =20
disregards the ordering of the elements. So for example:

     [[:lavender, :garden, :orange]].include? =20
[:lavender, :orange, :garden] =3D> false
     [[:lavender, :garden, :orange]].unordered_include? =20
[:lavender, :orange, :garden] =3D> true

Hmm=85 it would have been much more effective to use a set here rather =20=

than the above CPU-sucker, but now I am lazy to change it. ;-)

OK, so finally for the solution:

     ERROR_STRING =3D "The number of recipients times the number of =20
candles per recipient is more than the supply!"

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

So, in the inner loop we randomly pick a candles-per-recipient-=20
combination of all the possible combinations; If no one has that combo =20=

yet, we assign it to the next recipient. If someone has it already, we =20=

try to find an unique combination (loop on), unless it is impossible. =20=

In this case we simply start giving out any combinations. Once we give =20=

away a set of candles, we remove them from the original set. Easy-peasy.

You can check out the source code here.

This was a great quiz, too bad that not many people took a stab at it =20=

(so far 1 except me ;-)). The hardest part for me was the =20
implementation of the k-combination (and the result looks awful to me =20=

- I didn=92t check any algorithm/pseudocode/other solution though, I =20
wanted to roll my own) - after that the problem was pretty simple.