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

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

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

 



siskos1
Novice

Mar 24, 2010, 9:39 PM

Post #1 of 4 (2322 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 (2305 views)
Re: [siskos1] Recursive functions (an algorithm question) [In reply to] Can't Post

Let's call your function make_comb_set(N).

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 (2286 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 (2272 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

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives