Recursive Logic - Examples and Resources?

[Dan __]

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

 

[Matt Darby]

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.findall, :conditions => ["num1 IN (?) and num2 IN (?)", range,
range])

 

[Dan __]

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.findall, :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.).

 

[Axel Etzold]

-------- Original-Nachricht --------

Datum: Mon, 30 Jun 2008 00:46:04 +0900
Von: Dan __ <[email protected]>
An: (e-mail address removed)
Betreff: Re: Recursive Logic - Examples and Resources?

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.findall, :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.).

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

Best regards,

Axel

 

[Eric I.]

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, "throwfound,
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 = catchfound) 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.

 

[Ian Hobson]

Hi Dan,

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 __]

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

 

[Dave Bass]

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?

 

[Brian Marick]

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

 

[Martin DeMello]

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 neuburg]

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.

 

[Brian Marick]

Hmmm, that could be recursive right there!

Sorry - I meant _The Little Lisper_, an earlier edition of the same
book.

 

[Dan __]

Well, after looking over all the suggestions on here yesterday, I
believe I've been able to code exactly what I was looking for. I'd like
to say a big thank you to everyone who posted here to help me out, I'm
fairly sure I couldn't have done it without you all