*This week’s summary is provided by Peter, originally posted to his*

blog. I am providing it here with permission.

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

number of recipients is `r`

and candles per recipient is `c`

, then you

are looking for a (preferably non-repeating) random selection of `r`

elements of `c`

-combinations of the original set of candles. (In fact

it’s a bit more complicated than that: the `c`

-combinations have to be

recalculated from the remaining candles each time you give away a

group of candles, so we’ll get to that). Sounds confusing? Don’t

worry, after the implementation everything will be clear!

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

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

```
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
```

For example:

```
candles = { :orange => 2,
:vanilla => 1,
:lavender => 1,
:garden => 1 }
pp candles.comb(3)
=> [[: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-

combinations of the candles. We can then pick one and assign it to one

of the recipients. Then recalculate the above from the remaining

candles, give it to the next recipient - and so on and so forth.

That’s the basic idea, but we also need to ensure the candle

combinations are as non-repeating as possible. So let’s define some

further utility methods:

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

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

we give away some of them. So for example:

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

And some Array extensions:

```
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

`Array#rand`

is trying to pick a random non-repeating combination if

there is one (e.g. `[:orange, :lavender, :garden]`

) or, if there is no

such combination, then just a random one (e.g.

`[:orange, :orange, :garden]`

- orange is repeating, but we have no

other choice).

`Array#unordered_include?`

is like normal `Array#include?`

, but

disregards the ordering of the elements. So for example:

```
[[:lavender, :garden, :orange]].include?
```

[:lavender, :orange, :garden] => false

[[:lavender, :garden, :orange]].unordered_include?

[:lavender, :orange, :garden] => true

Hmm… it would have been much more effective to use a set here rather

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

OK, so finally for the solution:

```
ERROR_STRING = "The number of recipients times the number of
```

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}) <
```

(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

end

candles.remove_set(tried.last)

a[v] = tried.last

a

end

candle_set.merge({:extra => candles})

end

So, in the inner loop we randomly pick a candles-per-recipient-

combination of all the possible combinations; If no one has that combo

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

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

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

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

(so far 1 except me ;-)). The hardest part for me was the

implementation of the k-combination (and the result looks awful to me

- I didn’t check any algorithm/pseudocode/other solution though, I

wanted to roll my own) - after that the problem was pretty simple.