Velocity Reviews > Java > help on algorithm (recursion)

# help on algorithm (recursion)

Derek
Guest
Posts: n/a

 07-15-2003
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 http://www.velocityreviews.com/forums/(E-Mail 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

Guest
Posts: n/a

 07-15-2003
Derek wrote:
>
> 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 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 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.

Guest
Posts: n/a

 07-15-2003
Derek wrote:
> 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[i]+" "+time[j]+"min "
+dose[k]+"ug");
}
}
}

> to newsgroup and email (E-Mail 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.

--
=-=-=-=-=-=-=-=-=
From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
The jSyncManager Project: http://www.jsyncmanager.org

John W. Krahn
Guest
Posts: n/a

 07-15-2003
Derek wrote:
>
> 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
> (E-Mail 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
--
use Perl;
program
fulfillment

Mykola Rabchevskiy
Guest
Posts: n/a

 07-17-2003
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[i]+unit, list.subList(1,list.size() );
}
}
}

Derek wrote:

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

Roedy Green
Guest
Posts: n/a

 07-21-2003
On Thu, 17 Jul 2003 13:09:14 GMT, Mykola Rabchevskiy
<(E-Mail Removed)> wrote or quoted :

>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.
--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Guest
Posts: n/a

 07-21-2003
In comp.lang.java.programmer Roedy Green <(E-Mail Removed)> wrote:
> On Thu, 17 Jul 2003 13:09:14 GMT, Mykola Rabchevskiy
> <(E-Mail Removed)> wrote or quoted :

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

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.

Guest
Posts: n/a

 07-21-2003
(E-Mail Removed) wrote:
> In comp.lang.java.programmer Roedy Green <(E-Mail Removed)> wrote:
>
>>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.

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

--
=-=-=-=-=-=-=-=-=
From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
The jSyncManager Project: http://www.jsyncmanager.org


Guest
Posts: n/a

 07-21-2003
In comp.lang.java.programmer Brad BARCLAY <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
>> In comp.lang.java.programmer Roedy Green <(E-Mail Removed)> wrote:
> >
>>>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.

> 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

> --
> =-=-=-=-=-=-=-=-=
> From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
> The jSyncManager Project: http://www.jsyncmanager.org
> 

Ingo Pakleppa
Guest
Posts: n/a

 07-22-2003
On Mon, 21 Jul 2003 22:33:54 +0000, Brad BARCLAY wrote:

> (E-Mail Removed) wrote:
>> In comp.lang.java.programmer Roedy Green <(E-Mail Removed)> wrote:
> >
>>>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.

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

--
Keep American Families united! Support H.R. 539 and H.R. 832