On Jun 29, 10:08 am, Dan __ [email protected] wrote:
User2 has (3, 7), User2 could be part of the set, while User1 could not.
Now, I know enough to figure out that I need some recursion here, but I
have no idea how to implement it. Could anyone point me to some guides
or examples that could be of help to me? Thanks very much in advance
You’ve left off some details, such as what a User is and what order of
magnitude of Users we’re dealing with. Depending on these issues you
may want to approach the problem differently.
But I’ve attached some Ruby-ish pseudocode that goes through the basic
process. I would use a Set for some of the data rather than an Array,
as it allows you to use the Set#subset? method.
====
require ‘set’
def recurse(remaining_users_array, used_users_array,
uncovered_numbers_set)
if uncovered_numbers.empty?
puts used_users_array.join(', ')
# if you want any one solution, “throw(:found,
used_users_array)”
# if you want all solutions, you need another array parameter,
and
# add used_users_array to that
parameter
# if you just want is see a list, a simple “return” is
fine.
end
remaining_users_array.each_with_index do |user, index|
if uncovered_numbers_set.subset?(user.numbers_set)
recurse(all users from remaining_users_array after user,
used_users_array + user,
uncovered_numbers_set - user.numbers_set)
end
end
end
result = catch(:found) do
recurse(list_of_all_users, empty_list, set_of_numbers_to_be_covered)
end
====
Hope that helps,
Eric
====
LearnRuby.com offers Rails & Ruby HANDS-ON public & ON-SITE
workshops. Please visit http://LearnRuby.com for all the details.