help on algorithm (recursion)

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

  1. Derek

    Derek Guest

    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
    #1
    1. Advertising

  2. Derek

    Thad Smith Guest

    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 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
    Thad Smith, Jul 15, 2003
    #2
    1. Advertising

  3. Derek

    Brad BARCLAY Guest

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

    any help would be appreciated. please reply
    > 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.

    Brad BARCLAY

    --
    =-=-=-=-=-=-=-=-=
    From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
    The jSyncManager Project: http://www.jsyncmanager.org
    Brad BARCLAY, Jul 15, 2003
    #3
  4. 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).
    >
    > 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
    #4
  5. 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
    #5
  6. Derek

    Roedy Green Guest

    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.
    --
    Canadian Mind Products, Roedy Green.
    Coaching, problem solving, economical contract programming.
    See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
    Roedy Green, Jul 21, 2003
    #6
  7. Derek

    Guest Guest

    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
    #7
  8. Derek

    Brad BARCLAY Guest

    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.

    Brad BARCLAY

    --
    =-=-=-=-=-=-=-=-=
    From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
    The jSyncManager Project: http://www.jsyncmanager.org
    
    Brad BARCLAY, Jul 21, 2003
    #8
  9. Derek

    Guest Guest

    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

    > Brad BARCLAY


    > --
    > =-=-=-=-=-=-=-=-=
    > From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
    > The jSyncManager Project: http://www.jsyncmanager.org
    > 
    Guest, Jul 21, 2003
    #9
  10. 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
    For more information, see http://www.kkeane.com/lobbyspousal-faq.shtml
    Ingo Pakleppa, Jul 22, 2003
    #10
  11. 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
    #11
  12. Derek

    Brad BARCLAY Guest

    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.

    Brad BARCLAY

    --
    =-=-=-=-=-=-=-=-=
    From the OS/2 WARP v4.5 Desktop of Brad BARCLAY.
    The jSyncManager Project: http://www.jsyncmanager.org
    
    Brad BARCLAY, Jul 22, 2003
    #12
  13. 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
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ahmed Moustafa
    Replies:
    0
    Views:
    761
    Ahmed Moustafa
    Nov 15, 2003
  2. JimC
    Replies:
    3
    Views:
    508
  3. Allan W
    Replies:
    4
    Views:
    516
    Jos A. Horsmeier
    Jan 22, 2004
  4. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,480
    Mike Treseler
    Jun 23, 2006
  5. Replies:
    8
    Views:
    715
    John Reye
    Apr 26, 2012
Loading...

Share This Page