From: "Eric I." <rubytraining@...>
Date: 2008-06-30T02:27:25+09:00
Subject: Re: Recursive Logic - Examples and Resources?

On Jun 29, 10:08 am, Dan __ <major_general_...@hotmail.com> wrote:
> Hey all,
>
> Recently, one of my projects has run into a situation where I'm 95% sure
> I need to use recursion.  Its a situation like the following:
>
> Out of 20 numbers, I need a set of 10.  Each user has two numbers, each
> of which may or may not be part of the set.  I need to get 5 users to
> complete the set of 10 desired numbers.
>
> So, if the set is 1 2 3 4 5 6 7 8 9 10, and User1 has (9, 17), while
> 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.