Asp Forum - Recursive Logic - Examples and Resources?

Dan __

6/29/2008 2:08:00 PM

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 :)
--
Posted via http://www.ruby-....

12 Answers

Matt Darby

6/29/2008 3:14:00 PM

> 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.

This approach is pretty naive, but it might work:

range = 0...10
User.find(:all, :conditions => ["num1 IN (?) and num2 IN (?)", range,
range])

Dan __

6/29/2008 3:46:00 PM

Matt Darby wrote:
>> 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.
>
> This approach is pretty naive, but it might work:
>
> range = 0...10
> User.find(:all, :conditions => ["num1 IN (?) and num2 IN (?)", range,
> range])

Thanks for the suggestion Matt, it seems like a good start. That seems
like it would just return every user that fit into the set though, and
not five to make up a set. As well, I'd like to avoid using SQL code if
I could, because I'm not sure which database the final app will use/how
often it'll switch (its using PostgreSQL right now, but that might have
to switch depending on hosting, etc.).
--
Posted via http://www.ruby-....

Axel Etzold

6/29/2008 4:50:00 PM

-------- Original-Nachricht --------
> Datum: Mon, 30 Jun 2008 00:46:04 +0900
> Von: Dan __ <major_general_joe@hotmail.com>
> An: ruby-talk@ruby-lang.org
> Betreff: Re: Recursive Logic - Examples and Resources?

> Matt Darby wrote:
> >> 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.
> >
> > This approach is pretty naive, but it might work:
> >
> > range = 0...10
> > User.find(:all, :conditions => ["num1 IN (?) and num2 IN (?)", range,
> > range])
>
> Thanks for the suggestion Matt, it seems like a good start. That seems
> like it would just return every user that fit into the set though, and
> not five to make up a set. As well, I'd like to avoid using SQL code if
> I could, because I'm not sure which database the final app will use/how
> often it'll switch (its using PostgreSQL right now, but that might have
> to switch depending on hosting, etc.).
> --
> Posted via http://www.ruby-....

Dan,

maybe you'll need constraint programming with set constraints then.
Have a look at Gecode and its Ruby bindings gecoder then.

http://gecoder.rubyforge.org/documentation/constraints/set-constr...

Best regards,

Axel
--
Psssst! Schon vom neuen GMX MultiMessenger gehört?
Der kann`s mit allen: http://www.gmx.net/de/go/mult...

Eric I.

6/29/2008 5:30:00 PM

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://Lea... for all the details.

Ian Hobson

6/29/2008 6:20:00 PM

Hi Dan,

Dan __ 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:
>
People more expert than I have proven that recursion is not necessary -
although it can be a great convienience.
> 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 :)
>
Hi Dan,

It appears to me, that you have not defined the problem carefully enough
for us yet. :)

So lets assume the set of users is finite, and fixed - and therefore
there may not be a solution. Further, lets assume that if you have taken
somebody into your solution, can you kick them out again, if you find
you can't solve it with them in.

Without loss of generality we can assume that a user's first number is
less than his second (or swap then to make it so).

If the above is true, I would approach it like this.

report is global. (or could return an object with report and the
success/failure flag as properties)

searchroutine(aSet)
if aSet is empty then // we have a solution!
report = "Solution found: "
return success.
end if
find the lowest number in aSet.
create set of users whose first number is this lowest number.
for each user U in this set.
if ( U's second number is in set) then
create newSet = aSet without both of U's numbers.
if (searchRoutine(newSet) == success)
append U to report as part of the solution
return success // abort for loop
end if
end if
end for
return failure. (there is no U to use).
end searchroutine.

Dan __

6/30/2008 3:03:00 AM

Thanks Ian, Erik and Axel for your replies :) I'll get to giving them
all the time they deserve next chance I get (probably tomorrow after
work). However, since I was rather vague in my initial description of
the problem (as Ian and Erik pointed out), I'll try to describe it
better now, without writing a hugely long message.

Basically, what I'm trying to do is design an app to help out with a
game I play. Its a nation simulation game, where every player controls
a nation, and each nation gets two resources (I used numbers to
represent the resources in the example for simplicity). Each nation can
trade with up to five other nations, and gain the effects of the
resources of the other nations.

In this game, there are a few ideal combinations of resources, which
give much better effects than other combinations. So for my app, each
User object would contain information about which two resources a player
has. The app will check through all the stored User objects (in a
database somewhere), and try and put together six User objects (I used
five in the example, I know) whose resources make one of the ideal
resource sets. The number of User objects in the app at one time should
only be a couple hundred at most, and unless the game undergoes a huge
boom in the player base, I shouldn't need to worry about expansion of
that number.

Ian is correct in that the number of users is finite and fixed, at least
at any time during which a check for resource combinations is taking
place, and that a user object can be removed from a set if a solution
can't be reached with that user. The user's first number may not always
be less than their second number the way things are set up now, but if
that simplifies things, I can make it so that becomes the case.

Thanks very much to everyone who's replied so far, and I'll make sure I
give each solution a try after I get home from work tomorrow :)
--
Posted via http://www.ruby-....

Dave Bass

6/30/2008 9:41:00 PM

Dan __ wrote:
> Now, I know enough to figure out that I need some recursion here

For those of us who dislike recursion*, it may be worth pointing out
that anything you can do with recursion, you can also do with iteration
and a stack.

Dave

-----
* I've never been able to get my head around recursion. Does that make
me a bad person, or just a stupid idiot? (Probably the second.) I can't
see how recursion lines up with the principle of keeping things simple;
it seems like a recipe for complexity and potential disaster to me. A
stack, on the other hand, is eminently visualisable and understandable,
and it's pretty trivial to ensure the stack doesn't grow beyond some
predefined size. And everyone loves iteration. But millions of computer
scientists can't be wrong... can they?

--
Posted via http://www.ruby-....

Brian Marick

6/30/2008 10:39:00 PM

On Jun 30, 2008, at 4:41 PM, Dave Bass wrote:
> * I've never been able to get my head around recursion.

Buy _The Little Schemer_ (or, if you can find it used, _The Little
Schemer_, which I prefer). It's a fun introduction to recursion that
starts from nothing and goes amazingly far. If you want the heavy
guns: _Structure and Interpretation of Computer Programs_.

Sorry if these have already been mentioned. Missed beginning of thread.

-----
Brian Marick, independent consultant
Mostly on agile methods with a testing slant
www.exampler.com, www.exampler.com/blog, www.twitter.com/marick

Martin DeMello

6/30/2008 10:54:00 PM

On Mon, Jun 30, 2008 at 3:38 PM, Brian Marick
<marick@visibleworkings.com> wrote:
>
> On Jun 30, 2008, at 4:41 PM, Dave Bass wrote:
>>
>> * I've never been able to get my head around recursion.
>
> Buy _The Little Schemer_ (or, if you can find it used, _The Little Schemer_,
> which I prefer). It's a fun introduction to recursion that starts from
> nothing and goes amazingly far. If you want the heavy guns: _Structure and
> Interpretation of Computer Programs_.
>
> Sorry if these have already been mentioned. Missed beginning of thread.

How To Design Programs is a better way to wrap your head around
things. SICP is an excellent advanced book, but IMO too intense for a
first self-study book.

martin

matt

7/1/2008 12:30:00 AM

Brian Marick <marick@visibleworkings.com> wrote:

> On Jun 30, 2008, at 4:41 PM, Dave Bass wrote:
> > * I've never been able to get my head around recursion.
>
> Buy _The Little Schemer_ (or, if you can find it used, _The Little
> Schemer_

Hmmm, that could be recursive right there!

>, which I prefer). It's a fun introduction to recursion that
> starts from nothing and goes amazingly far. If you want the heavy
> guns: _Structure and Interpretation of Computer Programs_.

I was going to suggest the same thing. SICP is the best computer
programming book ever written, something every programmer should read
sooner or later; and among other virtues it will have you recursing a
blue streak in no time. m.

--
matt neuburg, phd = matt@tidbits.com, http://www.tidbits...
Leopard - http://www.takecontrolbooks.com/leopard-custom...
AppleScript - http://www.amazon.com/gp/product/...
Read TidBITS! It's free and smart. http://www.t...

comp.lang.ruby

Recursive Logic - Examples and Resources?

Dan __

Matt Darby

Dan __

Axel Etzold

Eric I.

Ian Hobson

Dan __

Dave Bass

Brian Marick

Martin DeMello

matt

x Login to ForumsZone