N Things taken M at a time

Discussion in 'Java' started by Ike, Jan 23, 2006.

  1. Ike

    Ike Guest

    I cannot get my head around how to code this algorithm, am hoping someone
    has an idea that can get me started here.

    If I have an array of N ints:

    int array[N];

    and I want to make an array of those N things, taken Q at a time, where Q >=
    N (i.e.repetition is permitted).

    For example, if I have N=2 where:

    int arrayN[] = new int[{0, 1}] ;

    and let's say Q = 3

    double arrayQ=new double[{
    {0,0,0},
    {0,0,1},
    {0,1,1},
    {1,1,1},
    {1,1,0},
    {1,0,0},
    {0,1,0},
    {1,0,1}
    }[;

    I believe this will yeild N ^ Q permutations. I'm trying discern however,
    how to go about creating a function to write out the new array[][] for a
    given Q for a given one-dimensional input array. I'm into the train of
    thinking whereby I have to "write code to write code," if you know what I
    mean. Has anyone handled a problem similar to this in the past? Thanks, any
    help is more than appreciated. -Ike
    Ike, Jan 23, 2006
    #1
    1. Advertising

  2. Ike

    Oliver Wong Guest

    "Ike" <> wrote in message
    news:t67Bf.11791$...
    >I cannot get my head around how to code this algorithm, am hoping someone
    > has an idea that can get me started here.
    >
    > If I have an array of N ints:
    >
    > int array[N];
    >
    > and I want to make an array of those N things, taken Q at a time, where Q
    > >=

    > N (i.e.repetition is permitted).
    >
    > For example, if I have N=2 where:
    >
    > int arrayN[] = new int[{0, 1}] ;
    >
    > and let's say Q = 3
    >
    > double arrayQ=new double[{
    > {0,0,0},
    > {0,0,1},
    > {0,1,1},
    > {1,1,1},
    > {1,1,0},
    > {1,0,0},
    > {0,1,0},
    > {1,0,1}
    > }[;


    As an aside, the correct syntax is probably something more like this (didn't
    compile, so this might have mistakes too):

    double Q = new double[][] {
    {0,0,0},
    {0,0,1},
    {0,1,1},
    {1,1,1},
    {1,1,0},
    {1,0,0},
    {0,1,0},
    {1,0,1}
    }

    >
    > I believe this will yeild N ^ Q permutations. I'm trying discern however,
    > how to go about creating a function to write out the new array[][] for a
    > given Q for a given one-dimensional input array. I'm into the train of
    > thinking whereby I have to "write code to write code," if you know what I
    > mean. Has anyone handled a problem similar to this in the past? Thanks,
    > any
    > help is more than appreciated. -Ike


    Not sure if this is a homework question, so I'm going to give you a few
    hints instead of the full answer.

    (1) There exists a solution which does not involve "writing code to
    write code".

    (2) Here's the solution for N = {0, 1} and Q = 3:

    {0,0,0},
    {0,0,1},
    {0,1,0},
    {0,1,1},
    {1,0,0},
    {1,0,1},
    {1,1,0},
    {1,1,1}

    Did you notice something about the order in which I wrote the elements
    of the array?

    - Oliver
    Oliver Wong, Jan 23, 2006
    #2
    1. Advertising

  3. Ike

    Stefan Ram Guest

    "Ike" <> writes:
    >and I want to make an array of those N things, taken Q at a time, where Q >=


    class Array
    { final int[] n; boolean hasNext = true; final int base;
    final java.lang.Object[] arg;
    private boolean inc( final int p )
    { final boolean result;
    if( p < n.length )
    { if( n[ p ]< base - 1 ){ ++n[ p ]; result = true; }
    else { n[ p ]= 0; result = inc( p + 1 ); }}
    else{ result = false; }
    return result; }
    private boolean inc()
    { return inc( 0 ); }
    private java.lang.Object[] dress()
    { final java.lang.Object[] result = new java.lang.Object[ n.length ];
    for( int i = 0; i < n.length; ++i )
    result[ i ]= arg[ n[ i ]];
    return result; }
    public Array( final int l, final java.lang.Object[] arg )
    { n = new int[ l ]; this.arg = arg;
    for( int i = 0; i < n.length; ++i )n[ i ]= 0;
    base = arg.length;
    hasNext = l > 0 && base > 0; }
    public boolean hasNext(){ return hasNext; }
    public java.lang.Object[] next()
    { final java.lang.Object[] result = this.dress();
    hasNext = this.inc();
    return result; }}
    public class Main
    { public static void main( final java.lang.String[] args )
    { final java.lang.Object[] names = new java.lang.Object[]{ 0, 1 };
    final int length = 3;
    final Array array = new Array( length, names );
    final int num =java.lang.Math.round
    (( int )java.lang.Math.pow( names.length, length ));
    final java.lang.Object[][] result = new java.lang.Object[ num ][];
    { int i = 0; while( array.hasNext() )
    { result[ i++ ]= array.next(); }}
    for( int i = 0; i < result.length; ++i )
    { for( int j = 0; j < result[ i ].length; ++j )
    java.lang.System.out.print( result[ i ][ j ] + " " );
    java.lang.System.out.println(); }}}
    Stefan Ram, Jan 23, 2006
    #3
  4. "dress" . good.

    ---

    Hey Ike, you're right about N^Q permutations. Here are three steps
    that could get you coding Stefan's solution:

    1. Try a hard coded version for the values in your example. Try to
    have three for loops over your alphabet (the N things). And generate
    an answer for your example.

    2. Try to make the number of for loops variable by using recursion. At
    each level of recursion iterate through your entire alphabet. This
    recursion solution conceptually like writing code to generate nested
    for loops for you, that you mention.

    3. Proceed to Stefan's solution, notice how he has the following layer
    of abstraction: he iterates over possible permutations:

    class Array
    { final int[] n; boolean hasNext = true; final int base;
    final java.lang.Object[] arg;
    private boolean inc( final int p )
    { final boolean result;
    if( p < n.length )
    { if( n[ p ]< base - 1 ){ ++n[ p ]; result = true; }
    else { n[ p ]= 0; result = inc( p + 1 ); }}
    else{ result = false; }
    return result; }
    private boolean inc()
    { return inc( 0 ); }
    private java.lang.Object[] dress()
    { final java.lang.Object[] result = new java.lang.Object[ n.length ];
    for( int i = 0; i < n.length; ++i )
    result[ i ]= arg[ n[ i ]];
    return result; }
    public Array( final int l, final java.lang.Object[] arg )
    { n = new int[ l ]; this.arg = arg;
    for( int i = 0; i < n.length; ++i )n[ i ]= 0;
    base = arg.length;
    hasNext = l > 0 && base > 0; }
    public boolean hasNext(){ return hasNext; }
    public java.lang.Object[] next()
    { final java.lang.Object[] result = this.dress();
    hasNext = this.inc();
    return result; }}
    public class Main
    { public static void main( final java.lang.String[] args )
    { final java.lang.Object[] names = new java.lang.Object[]{ 0, 1 };
    final int length = 3;
    final Array array = new Array( length, names );
    final int num =java.lang.Math.round
    (( int )java.lang.Math.pow( names.length, length ));
    final java.lang.Object[][] result = new java.lang.Object[ num ][];
    { int i = 0; while( array.hasNext() )
    { result[ i++ ]= array.next(); }}
    for( int i = 0; i < result.length; ++i )
    { for( int j = 0; j < result[ i ].length; ++j )
    java.lang.System.out.print( result[ i ][ j ] + " " );
    java.lang.System.out.println(); }}}

    Opalinski

    http://www.geocities.com/opalpaweb/
    opalinski from opalpaweb, Jan 23, 2006
    #4
    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. Ben Cameron

    Time taken algorithm

    Ben Cameron, Aug 4, 2004, in forum: Java
    Replies:
    4
    Views:
    581
    P.Hill
    Aug 5, 2004
  2. =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=

    vs2005 publish website doing bad things, bad things

    =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=, Oct 25, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    579
    =?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=
    Oct 25, 2006
  3. Alf P. Steinbach
    Replies:
    2
    Views:
    1,402
    John H.
    Jan 11, 2010
  4. Balog Pal
    Replies:
    2
    Views:
    329
    Balog Pal
    Jan 11, 2010
  5. Eric Böse-Wolf
    Replies:
    6
    Views:
    1,024
    Eric Böse-Wolf
    Jan 18, 2010
Loading...

Share This Page