CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr

Home: Perl Programming Help: Beginner:
Recursive functions (an algorithm question)

siskos1
Novice

Mar 24, 2010, 9:39 PM

Post #1 of 4 (3619 views)
 Recursive functions (an algorithm question) Can't Post
hello everybody; i am stuck in a problem. it is a kind of dynamic programming. it is a string alignment problem but it resembles like;

"writing all possible combinations of numbers that can be divided by 3 and/or 4"

for up to 12;

12 9 8 6 4 3 / 12 9 8 6 4/ 12 9 8 6 3/ ..../ 12 8 6 4/ .../ 9 6 4/... / 6 4 3/ 6 4/ 6 3/ 4 3/ 4 / 3 /

all combinations. if you have any suggestions or can show me similar problems, i will be pleased. thanks in advance.

in fact real question is like printing out all possible combinations that doesnt have consecutive 4 missing numbers in it. any help will be great.

(This post was edited by siskos1 on Mar 24, 2010, 9:42 PM)

rovf
Veteran

Mar 25, 2010, 5:08 AM

Post #2 of 4 (3602 views)
 Re: [siskos1] Recursive functions (an algorithm question) [In reply to] Can't Post

The base case for N <= 4 is trivial. For innstance, for N==4 you have the set (3; 4; 3 4). Now for N>4:

(1) Calculate \$set = make_comb_set(N-1)
(2a) If N fulfils the rule (i.e. is a valid combination), the new set equals \$set, joined by all elements from \$set with N added in front. For instance, if \$set contains the elements (x;y;z), the new set would be (x;y;z; N x; N y; N z).
(2b) If N does not fulfil the rule, the new set simply equals \$set.

siskos1
Novice

Mar 28, 2010, 8:44 PM

Post #3 of 4 (3583 views)
 Re: [rovf] Recursive functions (an algorithm question) [In reply to] Can't Post
thanks a lot. i tried to solve this particular question today. and my code doesnt work for some reason. it is most likely about my references but i couldnt find. if you delete line 14 and line 25-27, you will see that it works fine but to get the all combinations, we have to introduce the results found in the previous level. thats where i am stuck. i am playing with this code for some hours, but the logic behind it seems ok to me. i thought maybe i miss something about references here. thanks in advance. + the problem in the first post is for any number that can be divided by 3 or 4 up to target number; here below code is for all possible combinations of dividers of target number. no difference in logic though.

 Code
`use strict; use warnings;  my @a =();   sub func   {  my \$y=shift; my \$x;  for (\$x=2; \$x<=\$y; \$x++)        {      my @copy_upper_array =  @a;      #line 14            if(\$y % \$x == 0)                  {                                                         foreach( @a) {  push ( @{\$_}, \$x );   }                    my \$array_ref = [ \$x ];                         push(@a, \$array_ref);                                         if( @copy_upper_array )                     #line 25-27      {  foreach (@copy_upper_array)  {   unshift(@a, \$_);  }    }                  }         }  }   &func(12);   foreach(   @a  ) { print "\n  @{\$_}" ; }`

(This post was edited by siskos1 on Mar 28, 2010, 8:55 PM)

rovf
Veteran

Mar 29, 2010, 2:15 AM

Post #4 of 4 (3569 views)
 Re: [siskos1] Recursive functions (an algorithm question) [In reply to] Can't Post
Sorry that I am too busy to research your code in detail, but one thing struck me: In your posting, you were asking for a recursive solution, and this is also what I proposed in my response; however, you are presenting now an iterative solution.

I don't want to say that an iterative solution is necessarily bad; in contrary, there are many cases where the iterative solution has advantages. The recursive one is, however, usually easier to understand. I suggest that you try first a recursive one, and after this works, transform it to an iterative one.

Ronald

 Announcements     PerlGuru Announcements Perl Programming Help     Frequently Asked Questions     Beginner     Intermediate     Advanced     Regular Expressions     mod_perl     DBI     Win32 Programming Help Fun With Perl     Perl Quizzes - Learn Perl the Fun Way     Perl Golf     Perl Poetry Need a Custom or Prewritten Perl Program?     I need a program that...     I Need a Programmer for Freelance Work     Throw Down The Gauntlet General Discussions     General Questions     Feedback     Tutorial/Article Suggestions for The Learning Cent     Internet Security Other Programming Languages     Javascript     PHP

 Search this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0