N Things taken M at a time

Thread view:

Ike - 23 Jan 2006 16:02 GMT

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

Reply to this Message

Oliver Wong - 23 Jan 2006 16:24 GMT

>I cannot get my head around how to code this algorithm, am hoping someone
> has an idea that can get me started here.
[quoted text clipped - 23 lines]
> {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
[quoted text clipped - 3 lines]
> 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

Reply to this Message

Stefan Ram - 23 Jan 2006 17:12 GMT

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

Reply to this Message

opalpa@gmail.com opalinski from opalpaweb - 23 Jan 2006 18:19 GMT

"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
opalpa@gmail.com
http://www.geocities.com/opalpaweb/

Reply to this Message

N Things taken M at a time

Free Magazines