```--------------020308050602040408010501
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

I wrote:
> ...
> Technically, this is not so much an insight as an intuition.  It might
> not be true in all cases...
D'oh!  Here's my second solution, which does backtrack if necessary.  It
handles Adam's example, and a shorter example I found:

\$ ruby loot.rb 3   3 3 2 2 2 2 2 2 2 1
This loot can't be evenly split 3 ways

\$ ruby loot2.rb 3   3 3 2 2 2 2 2 2 2 1
1: 2 2 3
2: 2 2 3
3: 1 2 2 2

\$ ruby loot.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86
91 96
This loot can't be evenly split 5 ways

\$ ruby loot2.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86
91 96
1: 4 8 9 86 96
2: 6 39 67 91
3: 18 26 76 83
4: 55 66 82
5: 34 36 40 43 50

This one uses recursive yielding to manage the search space.  It should
be close to the first solution in speed for cases where the heuristic
applies, except for the array duping.

Luke Blanshard

--------------020308050602040408010501
Content-Type: text/plain;
nameoot2.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filenameoot2.rb"

#!/usr/bin/ruby -w

# Ruby quiz #65, splitting the loot, take 2
# Usage: loot2.rb <band-size> <values...>
#  where band-size is the number of adventurers in the band
#  and values is the list of numerical values of the rubies

class Array
# Returns a new array consisting of the elements of this array at
# the given indices.
def subscript indices
end

# Deletes all given indices from self, returns self.  Assumes
# indices are in reverse order.
def delete_at_all! indices
indices.each{|i| delete_at i}
self
end
end

# Splits the given array of values up into count equal arrays, or nil.
def split values, count
total  alues.inject(0){|s,v|return nil if v<0;s+v}
return nil if count <  or total % count !
find_split values.sort.reverse!, count, total/count
end

# Recursively picks sublists of "values" that sum to "sum", returns a
# list of them or nil.
def find_split values, count, sum
return [values.reverse!] if count 1
pick values, sum do |indices|
return nil if indices[-1] !   # If we can't consume the first element, give up
result  ind_split( values.dup.delete_at_all!(indices), count-1, sum )
return result.unshift(values.subscript(indices)) if result
end
return nil
end

# Continuously picks values from the given array totaling sum,
# yielding a list of indices for each sublist found.  Assumes values
# is sorted highest first.
def pick values, sum, lo  # Skip past elements bigger than sum
i  o
i +  while i < values.size && values[i] > um
yield [i-1] if i>lo && values[i-1] sum

cutoff  um
while i < values.size
value  alues[i]
if value < cutoff
pick( values, sum-value, i+1 ){|indices| yield indices << i}
cutoff  alue # Try the next unique value
end
i +
end
end

# Main program
if \$0 __FILE__
count, *values  RGV.map {|arg| Integer(arg)}
if result  plit( values, count )
\$,, \$\   ", "\n" # Set the field and record terminators
count.times {|i| print "#{i+1}:", result[i]}
else
puts "This loot can't be evenly split #{count} ways"
end
end

--------------020308050602040408010501--

```