A little algorithmic problem...

D

dushkin

Hi,
If I am not at the correct plcae, please alert...

Suppose I have a string with x place holders (P1, P2, P3,...Px).
And I have x arrays of variable length which includes a list of
optional values for each Pi.

How can I effectivly generate a set of all string possibilities?

============================================
Example:

Suppose I have the string xxxxxxxP1xxxxxP2xxxxxP3xxxxx
And I have the following list of values:
For P1: a,b,c
For P2: 1,2,3,4,5,6,7
For P3: i,ii,iii,iv

The number of P's is a variable, and also the lengths of the lists.

The product should be:
xxxxxxxaxxxxx1xxxxxixxxxx
xxxxxxxaxxxxx1xxxxxiixxxxx
xxxxxxxaxxxxx1xxxxxiiixxxxx
xxxxxxxaxxxxx1xxxxxivxxxxx
..
..
xxxxxxxcxxxxx7xxxxxivxxxxx

=========================

Thanks! (java code sample will be very welcomed !!!)
 
S

Stefan Ram

dushkin said:
How can I effectivly generate a set of all string possibilities?

When replying to my post, please do not quote my complete
post, but only those parts you directly refer to.
Especially, please do not quote the complete source code.
Otherwise, I will refrain from posting source code to this group.

class Possibility implements
java.lang.Iterable<java.lang.Object>,
java.util.Iterator<java.lang.Object>
{ public Possibility( final java.lang.Object ... array )
{ this.array = array; this.offset = 0; }
public boolean hasNext(){ return this.offset < this.array.length; }
public java.lang.Object next()
{ if( !this.hasNext() )this.offset = 0;
return this.array[ this.offset++ ]; }
public java.util.Iterator<java.lang.Object>iterator(){ return this; }
public void remove()
{ throw new java.lang.UnsupportedOperationException(); }
private final java.lang.Object[] array;
private int offset; }

class Possibilities implements
java.lang.Iterable<java.lang.Object[]>,
java.util.Iterator<java.lang.Object[]>
{ public Possibilities( final Possibility ... array )
{ this.array = array; this.offset = 0;
this.hasNext = true;
this.length = this.array.length;
this.result = new java.lang.Object[ this.length ];
for( int i = 0; i < this.length; ++i )
{ if( this.array[ i ].hasNext() )result[ i ]= this.array[ i ].next();
else throw new java.lang.RuntimeException(); }}
public boolean hasNext(){ return this.hasNext; }
public java.lang.Object[] next()
{ final java.lang.Object[] result =
java.util.Arrays.copyOf( this.result, this.length );
this.advance();
return result; }
private void advance(){ this.advance( this.length - 1 ); }
private void advance( final int offset )
{ if( offset < 0 )
this.hasNext = false;
else
{ if( this.array[ offset ].hasNext() )
this.result[ offset ]= this.array[ offset ].next();
else
{ this.result[ offset ]= this.array[ offset ].next();
this.advance( offset - 1 ); }}}
public java.util.Iterator<java.lang.Object[]>iterator(){ return this; }
public void remove()
{ throw new java.lang.UnsupportedOperationException(); }
private java.lang.Object[] result;
private final Possibility[] array;
private int offset;
private final int length;
private boolean hasNext; }

public class Main
{ public static void main( final java.lang.String[] args )
{ for
( final java.lang.Object[] o :
new Possibilities
( new Possibility( "alpha", "beta" ),
new Possibility( "0", "1" ),
new Possibility( "x", "y", "z" )))
{ java.lang.System.out.printf( "%s-%s-%s%n", o[ 0 ], o[ 1 ], o[ 2 ]); }}}

alpha-0-x
alpha-0-y
alpha-0-z
alpha-1-x
alpha-1-y
alpha-1-z
beta-0-x
beta-0-y
beta-0-z
beta-1-x
beta-1-y
beta-1-z

When replying to my post, please do not quote my complete
post, but only those parts you directly refer to.
Especially, please do not quote the complete source code.
Otherwise, I will refrain from posting source code to this group.
 
D

dushkin

Daniel Kraft :
dushkin said:
Hi,
If I am not at the correct plcae, please alert...

Suppose I have a string with x place holders (P1, P2, P3,...Px).
And I have x arrays of variable length which includes a list of
optional values for each Pi.

How can I effectivly generate a set of all string possibilities?

I'd first split the string into the x+1 fixed pieces. Then simply try
all possiblities. Suppose these fixed Strings are stored in the array
fixed and your optional values arrays are stored itself in an array
values. Then use recursion:

void process(String stem, String[] fixed, String[][] values, int i)
{
if(i==fixed.length-1)
{
System.out.println(stem+fixed);
return;
}

for(String val : values)
process(stem+val+fixed);
}

process("", fixed, values, 0); should then print out all those
possibilities.

Maybe one could optimize those string concatenations with a
StringBuilder but I'm not quite sure whether that would really help.
BTW, I'm also not sure whether this code works out-of-the-box, I
couldn't test it. But something like that should do the job.

Yours,
Daniel


Many thanks Daniel !
I will try it.

Any more ideas around?
 
D

Daniel Kraft

dushkin said:
Hi,
If I am not at the correct plcae, please alert...

Suppose I have a string with x place holders (P1, P2, P3,...Px).
And I have x arrays of variable length which includes a list of
optional values for each Pi.

How can I effectivly generate a set of all string possibilities?

I'd first split the string into the x+1 fixed pieces. Then simply try
all possiblities. Suppose these fixed Strings are stored in the array
fixed and your optional values arrays are stored itself in an array
values. Then use recursion:

void process(String stem, String[] fixed, String[][] values, int i)
{
if(i==fixed.length-1)
{
System.out.println(stem+fixed);
return;
}

for(String val : values)
process(stem+val+fixed);
}

process("", fixed, values, 0); should then print out all those
possibilities.

Maybe one could optimize those string concatenations with a
StringBuilder but I'm not quite sure whether that would really help.
BTW, I'm also not sure whether this code works out-of-the-box, I
couldn't test it. But something like that should do the job.

Yours,
Daniel
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top