On 2/6/06, Patrick Deuster <pdeuster / gmx.net> wrote:
> For example, my old version didn't split
>
> ruby loot.rb 6 34 78 21 70 45 67 70 19 90 76 54 20 30 19 80 7 65 43 56 46

My turn to say 'Doh!'
I found a case where the greedy algorithms failed and mine passed, but
now Patrick has found one that mine fails.  But I have a simple 2 line
fix. I just need to move gems to my 'pile2' one at a time, instead of
a share-at-a-time.  I had considered doing this before, but managed to
convince myself it was slower and not needed.  Oops.

-Adam

##################################
#loot.rb
#Adam Shelly
#evenly splits an array into n sets of equal value

class Array
  def sum
    inject(0){|s,v| s+v}
  end
  def subtract arr
    return clear if arr==self
    arr.each{|e| if (n=index(e)) then delete_at(n); end }
    self
  end
 #fast version which misses some subsets.
  #useful as a rough filter.
  def quick_find_subset_with_sum n
    a = self.sort.reverse
    sum,set = 0,[]
    a.each {|e|
      if (sum+e <= n)
        sum+=e
        set<<e
        return set if sum == n
      end
    }
    nil
  end
  def find_subset_with_sum n
    s = quick_find_subset_with_sum n
    return s if s
    possibilities, seen  = [self.select{|e| e<=n}],{}
    until possibilities.empty?
      candidate = possibilities.pop
      diff = candidate.sum - n
      return candidate if diff == 0
      break if diff < 0
      candidate.each_with_index{|e,i|
        break if e > diff
        new_cand = (candidate.dup)
        new_cand.delete_at(i)
        return new_cand if e == diff
        possibilities << new_cand if !seen[new_cand]
        seen[new_cand]=true
      }
    end
    nil
  end
end


#1: put all loot in pile 1
#2: find  a share from pile 1
#3: if you can't find one, it can't be split
#4: find a share in the remaining gems
#5: repeat unitl you find all shares
#6: if you can't find enough shares
#7: move one item from the first share to pile2
#8: repeat starting from step 2,  include pile2 when searcing the
remainder in step 4
# this serves to shuffle the possible combinations.
# if all the gems are moved to pile2, there is no possible solution

def splitter n, loot
  splits=[]
  pile1,pile2=loot.dup.sort.reverse,[]
  total = loot.sum
  share = total/n
  return nil if total%n != 0 || loot.size < n || loot.max > share

  until pile1.empty?
    splits[0] = pile1.find_subset_with_sum(share)
    break if !splits[0]
    remaining = pile1.subtract(splits[0])+pile2
    (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]     ##This line changes to the following two lines
    pile2 << splits[0].shift
    pile1 += splits[0]
  end
  return nil
end

if __FILE__ == $0

n = ARGV.shift.to_i
  if ARGV.size < 2 || n < 1
    puts "Usage: #{$0} partners item1 item2 ..."
  else
    shares = splitter(n, ARGV.map{|a| a.to_i })
    if !shares
      puts  "This loot can not be evenly divided into #{n} parts!"
    else
      shares.sort_by{|a|[a.size,-a.max]}.each_with_index{|share,i|
puts "#{i}: #{share.sort.reverse.join(' ')}"}
      puts "everyone gets #{shares[0].sum}"
    end
  end
end