On 2/8/06, Manuel Kasten <kasten.m / gmx.de> wrote:
> Adam Shelly wrote:
> > My turn to say 'Doh!'
>
> Yet again. Your new version doesn't split
>
> 6-ways
> 26 77 26 77 1 39 17 10 90 89 3 20 47 37 51 9 34 15 22 22 94 52
>

Aargh.
How about this one:  here is a replacement splitter function - drop
into my last submission.
I added 2 more tests to detect unsplittable sets before I start
iterating, and I fixed the iterator to be sure it tests every
combination, and quits as soon as it finds a value which can not fit
into any fair share.  Oh, and I added one helper to Integer:

######################
class Integer
  def odd?
      self % 2 != 0
  end
end

def splitter n, loot
  splits=[]
  pile1,pile2=loot.dup.sort.reverse,[]
  total = loot.sum
  share = total/n
  num_odd = loot.inject(0){|s,g| g.odd? ? s+1 : s}

  # lots of ways to fail early:
  # doesn't divide evenly; not enough items; one item bigger than share size;
  # the number of items worth more than 1/2 share must be < number of shares
  # if the share size is even, there must be an even number of items
with odd values
  # if the share size is odd, there must be an even number plus one
for every share

  return nil if total%n != 0 || loot.size < n || loot.max > share
  return nil if loot.find_all{|g| g>share/2}.size > n
  num_odd-=n if share.odd?
  return nil if num_odd < 0 || num_odd.odd?

  #pile1 holds all the items we haven't tried to make a share with.
  #take a candidate from the pile.
  #if you can't make a share using that one, it is impossible to
divide the loot.
  #othewise, keep trying to make shares.
  #if you get stuck, move the candidate to pile2, and start again.
  #if pile1 becomes empty, give up

  until pile1.empty?
    candidate = pile1.shift
    remaining = (pile1+pile2)
    splits[0] = remaining.find_subset_with_sum(share - candidate)
    break if !splits[0]
    splits[0].unshift candidate
    (1...n).each do |i|
        break if nil == (splits[i] = remaining.find_subset_with_sum(share))
        remaining.subtract(splits[i])
      end
      return splits if splits[n-1]
      pile2 << splits[0].shift
  end
  nil
end

######################
-Adam