help on algorithm (recursion)

Discussion in 'Java' started by Derek, Jul 15, 2003.

1. DerekGuest

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

Derek, Jul 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 (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.

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+" "+time[j]+"min "
+dose[k]+"ug");
}
}
}

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

4. John W. KrahnGuest

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

John W. Krahn, Jul 15, 2003
5. Mykola RabchevskiyGuest

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() );
}
}
}

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

Mykola Rabchevskiy, Jul 17, 2003
6. Roedy GreenGuest

On Thu, 17 Jul 2003 13:09:14 GMT, Mykola Rabchevskiy
<> 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.

Roedy Green, Jul 21, 2003
7. GuestGuest

In comp.lang.java.programmer Roedy Green <> wrote:
> On Thu, 17 Jul 2003 13:09:14 GMT, Mykola Rabchevskiy
> <> 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, Jul 21, 2003

wrote:
> In comp.lang.java.programmer Roedy Green <> 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


9. GuestGuest

In comp.lang.java.programmer Brad BARCLAY <> wrote:
> wrote:
>> In comp.lang.java.programmer Roedy Green <> 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
> 

Guest, Jul 21, 2003
10. Ingo PakleppaGuest

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

> wrote:
>> In comp.lang.java.programmer Roedy Green <> 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

Ingo Pakleppa, Jul 22, 2003
11. Mykola RabchevskiyGuest

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

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

Mykola Rabchevskiy, Jul 22, 2003

wrote:

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

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.

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

13. Mykola RabchevskiyGuest

Ingo Pakleppa wrote:

> 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

Mykola Rabchevskiy, Jul 22, 2003