help on algorithm (recursion)

[Derek]

i need help trying to solve the following problem. the algorithm to use
would
be much appreciated. having it in java would be ideal. the input is any
number
(1..N) factor types. each factor type having any number (1..N) factor
values.
the output are strings as shown below (order is important). i am guessing
that
recursion is involved in this. any help would be appreciated. please reply
to newsgroup and email (e-mail address removed) (remove NOSPAM).
thank you. derek

INPUT (any number of types and values per type):

Factor Type Factor Values Factor Unit
----------- ------------------------------------- ------------
Tissue kidney liver

Time 0 30 60 min

Dose 0.001 0.01 0.1 1 ug


OUTPUT:

kidney 0min 0.001ug
kidney 0min 0.01ug
kidney 0min 0.1ug
kidney 0min 1ug
kidney 30min 0.001ug
kidney 30min 0.01ug
kidney 30min 0.1ug
kidney 30min 1ug
kidney 60min 0.001ug
kidney 60min 0.01ug
kidney 60min 0.1ug
kidney 60min 1ug
liver 0min 0.001ug
liver 0min 0.01ug
liver 0min 0.1ug
liver 0min 1ug
liver 30min 0.001ug
liver 30min 0.01ug
liver 30min 0.1ug
liver 30min 1ug
liver 60min 0.001ug
liver 60min 0.01ug
liver 60min 0.1ug
liver 60min 1ug

 

[Thad Smith]

i need help trying to solve the following problem. the algorithm to use
would be much appreciated. having it in java would be ideal. the input is any
number (1..N) factor types. each factor type having any number (1..N) factor
values.
the output are strings as shown below (order is important). i am guessing
that recursion is involved in this. any help would be appreciated. please reply
to newsgroup and email (e-mail address removed) (remove NOSPAM).
thank you. derek

INPUT (any number of types and values per type):

Factor Type Factor Values Factor Unit
----------- ------------------------------------- ------------
Tissue kidney liver
Time 0 30 60 min
Dose 0.001 0.01 0.1 1 ug

OUTPUT:

kidney 0min 0.001ug
kidney 0min 0.01ug ....
liver 60min 0.1ug
liver 60min 1ug

This can be broken down into three problems:
1. Reading the factor types, factor values, and units.
2. Representing the inputs in memory.
3. Generating the output combinations.

I suggest solving the second problem first.

For the first problem, you need to include details of what format the
input is in, how you know how many factors there are, how you know how
many factor values each has, etc. There are different ways to do this.
A common way is to use a special input (possibly no characters) to
signify the end of a list. I see that in your example the first factor
has no unit. You need to be able to handle that.

The third problem, generating the output, can use recursion. Start with
the first factor, which varies the least, then, for each value, generate
the outputs involving all other factors. The trick with using recursion
is to define the operation that the recursive function does.

Writing the code to do this is Derek's job.

Thad

 

[Brad BARCLAY]

i need help trying to solve the following problem. the algorithm to use
would
be much appreciated. having it in java would be ideal. the input is any
number
(1..N) factor types. each factor type having any number (1..N) factor
values.
the output are strings as shown below (order is important). i am guessing
that
recursion is involved in this.

That would be a bad guess. I don't see anywhere here where recursion
would be significantly useful, as not one single result depends on the
calculation of the previous result.

What you want is a set of imbedded loops, something like:

for (int i=0;i<tissue.length;i++) {
for (int j=0;j<time.length;j++) {
for (int k=0;k<dose.length;k++) {
System.out.println(tissue+" "+time[j]+"min "
+dose[k]+"ug");
}
}
}

any help would be appreciated. please reply

to newsgroup and email (e-mail address removed) (remove NOSPAM).

Sorry, but if you expect someone to take time out of their day to
answer a newsgroup question for you, you should have curteousy and take
the time to check said newsgroup for replies. This is common
netiquette. As such, this has been posted, but _not_ e-mailed.

Brad BARCLAY

 

[John W. Krahn]

i need help trying to solve the following problem. the algorithm to use
would be much appreciated. having it in java would be ideal. the input
is any number (1..N) factor types. each factor type having any number
(1..N) factor values. the output are strings as shown below (order is
important). i am guessing that recursion is involved in this. any help
would be appreciated. please reply to newsgroup and email
(e-mail address removed) (remove NOSPAM).

INPUT (any number of types and values per type):

Factor Type Factor Values Factor Unit
----------- ------------------------------------- ------------
Tissue kidney liver

Time 0 30 60 min

Dose 0.001 0.01 0.1 1 ug

OUTPUT:

kidney 0min 0.001ug
kidney 0min 0.01ug
kidney 0min 0.1ug
kidney 0min 1ug
kidney 30min 0.001ug
kidney 30min 0.01ug
kidney 30min 0.1ug
kidney 30min 1ug
kidney 60min 0.001ug
kidney 60min 0.01ug
kidney 60min 0.1ug
kidney 60min 1ug
liver 0min 0.001ug
liver 0min 0.01ug
liver 0min 0.1ug
liver 0min 1ug
liver 30min 0.001ug
liver 30min 0.01ug
liver 30min 0.1ug
liver 30min 1ug
liver 60min 0.001ug
liver 60min 0.01ug
liver 60min 0.1ug
liver 60min 1ug

#!/usr/bin/perl
use warnings;
use strict;

my @data;
while ( <DATA> ) {
my ( $type, @fields ) = split or next;
if ( $type eq 'Tissue' ) {
@data = @fields;
}
if ( $type eq 'Time' ) {
my $unit = pop @fields;
@data = map { my $data = $_; map "$data $_$unit", @fields }
@data;
}
if ( $type eq 'Dose' ) {
my $unit = pop @fields;
@data = map { my $data = $_; map "$data $_$unit\n", @fields }
@data;
}
}

print for @data;

__DATA__

Factor Type Factor Values Factor
Unit
----------- ------------------------------------- ------------
Tissue kidney liver

Time 0 30 60
min

Dose 0.001 0.01 0.1 1 ug



John

 

[Mykola Rabchevskiy]

You're right, it requires recursion:

public class Recursion {

public static void main( String[] arg ){
Vector v = new Vector();
v.add( "Tissue - kidney liver" .split( " " ) );
v.add( "Time min 0 30 60" .split( " " ) );
v.add( "Dose ug 0.001 0.01 0.1 1.0" .split( " " ) );
for( Iterator V = v.iterator(); V.hasNext(); )
System.out.print( "\t" + ( (String[])V.next() )[0] );
System.out.println();
System.out.println();
enum( "", v );
}

public static void enum( String prefix, List list ){
if( list.size() == 0 ){
System.out.println( prefix );
} else {
String[] v = (String[])list.get( 0 );
String factor = v[0];
String unit = ( v[1].equals( "-" ) ) ? "" : " " + v[1];
for( int i = 2; i < v.length; i++ )
enum( prefix+"\t"+v+unit, list.subList(1,list.size() );
}
}
}

 

[Roedy Green]

You're right, it requires recursion:

I thinks somebody once proved any recursion problem can be turned into
an iteration problem. I remember coding QuickSort in Fortran which
did not have recursion using arrays to track the levels that would
usually be handled by the stack.

Recursion is seductive. The solutions look so elegant. However
sometimes they blow up with stacks that grow too deep. I don't think
that is the case here.

 

[Guest]

On Thu, 17 Jul 2003 13:09:14 GMT, Mykola Rabchevskiy

I thinks somebody once proved any recursion problem can be turned into
an iteration problem. I remember coding QuickSort in Fortran which
did not have recursion using arrays to track the levels that would
usually be handled by the stack.

I think it's more general than this, any iteration can be expressed as
a recursion and vice-versa.

Recursion is seductive. The solutions look so elegant. However
sometimes they blow up with stacks that grow too deep. I don't think
that is the case here.

The only practical use for recursion I've ever had isn't in Java, but
XSLT. In this case it's a completly natural approach because you are
writing bits of code that traverse a tree (well, an XML document,
which is basically just a text description of a tree). But it's still
a mind-bender sometimes when all you want to do is, say, iterate a
value based on some properties in the XML document.

--arne

DISCLAIMER: These opinions and statements are those of the author and
do not represent any views or positions of the Hewlett-Packard Co.

 

[Brad BARCLAY]

I think it's more general than this, any iteration can be expressed as
a recursion and vice-versa.

No, Roedy was correct. Iterations that do not depend on the previous
iteration result don't map into recursion algorithms.

Brad BARCLAY

 

[Guest]

No, Roedy was correct. Iterations that do not depend on the previous
iteration result don't map into recursion algorithms.

Could you provide a specific example? Do you mean an iteration that
sets a variable to the result of a function which returns a result
independent of the iteration (like "rand()")? Or something else?

Thanks, I'm curious,

--arne

 

[Ingo Pakleppa]

No, Roedy was correct. Iterations that do not depend on the previous
iteration result don't map into recursion algorithms.

Are you sure about that? I will easily admit that implementing such an
algorithm as recursion would be wasteful and inefficient, but I don't see
why it wouldn't map at all.

Ultimately, I think Roedy's statement is correct for another reason:
processors do not understand recursion. Therefore, if recursions could not
be expressed as iterations, then it would not be possible to execute
recursions at all.

In practical terms, a recursion is simply an iteration that uses a stack.

 

[Mykola Rabchevskiy]

I thinks somebody once proved any recursion problem can be turned into
an iteration problem. I remember coding QuickSort in Fortran which
did not have recursion using arrays to track the levels that would
usually be handled by the stack.

Yes, any recursive algorithm can be turned into yterative. But sometimes
recursive code is more simple. By the way, recursion level monitoring is
not more complicated that array's length monitoring

 

[Brad BARCLAY]

Could you provide a specific example? Do you mean an iteration that
sets a variable to the result of a function which returns a result
independent of the iteration (like "rand()")? Or something else?

Thanks, I'm curious,

Sorry for the delay in replying -- your request has caused me to go
back through all of my computer science texts to see if I can find a
suitable example .

I'll let you know when I come up with something.

Brad BARCLAY

 

[Mykola Rabchevskiy]

Ultimately, I think Roedy's statement is correct for another reason:
processors do not understand recursion. Therefore, if recursions could not
be expressed as iterations, then it would not be possible to execute
recursions at all.

Processor also do not understand Pascal, Java, C++, generic classes and
so on