From: Robert Klemme <bob.news@...>
Date: 2005-10-23T21:27:01+09:00
Subject: Re: combination sums of several arrays

Dominik Bathon <dbatml@gmx.de> wrote:
> On Sun, 23 Oct 2005 03:14:16 +0200, David Vincelli
> <micologist@gmail.com> wrote:
> 
>> I'm writing a little BlackJack program for fun and I'm at the point
>> where I have to decide which point value to assign to a hand. As you
>> know, an Ace may be worth 1 or 11 in this game - whatever is closer
>> to 21 without going over.
>> 
>> Considering this, I know I have to come up with an algorithm that
>> first determines what the different point values may be (the extreme
>> case may be that a player got all four aces, now I'd have to
>> determine all combinations of the players cards).
>> 
>> This demonstrates some of the code I wrote:
>> 
>> pl = Player.new
>> pl.hand.each { |card|  p pl.card.value }
>> 
>> might produce this output:
>> [1, 11]
>> [5]
>> [10]
>> 
>> For the above example, so what I'm looking for is a method that will
>> calculate all possible point totals. For this example  I'd get the
>> results [16, 26]
>> 
>> I'm thinking I might do this by first building a binary tree,
>> creating unique branches that would add up to the results when I
>> applied some recursive algorithm to it. But I'm curious to know how
>> other people might do this? (I'm especially curious to see if anyone
>> has some solution that does not require building a tree and
>> recursing..). 
> 
> You probably won't need this because of the other replies, but here
> is a solution to the combination sums problem (without building a
> tree ;-): 
> 
> def combination_sums(arr)
>    arr.inject([0]) { |sums, cur|
>      cur.map { |a|
>        sums.map { |b| b+a }
>      }.flatten
>    }.uniq
> end
> 
> p combination_sums([[1,11],[5],[10]])
> p combination_sums([[1,3,5],[2,3,6]])
> 
> output:
> [16, 26]
> [3, 5, 7, 4, 6, 8, 9, 11]
> 
> Dominik

Here's a variant that reduces the number of created arrays:

sums = values.inject([0]) do |sums,values|
  values.inject([]) do |su,v|
    sums.inject(su) {|su,s| su << (s+v)}
  end
end
sums.uniq!

>> values = [[1,11],[2],[3,4]]
=> [[1, 11], [2], [3, 4]]
>> sums = values.inject([0]) do |sums,values|
?>   values.inject([]) do |su,v|
?>     sums.inject(su) {|su,s| su << (s+v)}
>>   end
>> end
=> [6, 16, 7, 17]
>> sums.uniq!
=> nil

Kind regards

    robert