Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > how to use recursive algorithm to determine all of the arrangements?

Reply
Thread Tools

how to use recursive algorithm to determine all of the arrangements?

 
 
James McGill
Guest
Posts: n/a
 
      05-04-2006
On Thu, 2006-05-04 at 10:03 +0200, Thomas Weidenfeller wrote:
>
>
> As a general hint, you are suggesting you are using JLayeredPane to
> construct your animation. This doesn't sound too good.


It's not. I need to move away from Swing/AWT entirely, I think.


Thanks,

James.

 
Reply With Quote
 
 
 
 
Oliver Wong
Guest
Posts: n/a
 
      05-08-2006
"index" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
> of course We know that there are n! permutations of n elements,but i
> just want to make a program to print what does every permutation look
> like,like
> this,{A1,A2,A3},{A2,A1,A3},{A3,A1,A2},{A3,A2,A1},{ A1,A3,A2},{A2,A3,A1}.
> can anyone give me some tips?
>


How would you, as a human being, solve this problem? I.e. how did you
come up with the above list of 6 elements?

- Oliver

 
Reply With Quote
 
 
 
 
opalpa@gmail.com opalinski from opalpaweb
Guest
Posts: n/a
 
      05-09-2006
The following code is not recursive. There are three files involved:

IndexMapper.java Permutations.java PossibleSets.java

btw, How do I check for overflow on multiplication in Java (or any
other arithmetic operation)?

One aspect I like about this code is that returned items are of same
type as passed in items, that is one can give an array of integers and
get arrays of integers, or one can give strings and get back strings.

Here is IndexMapper:
import java.util.*;
import java.lang.reflect.Array;
class IndexMapper implements Iterator {
private Object map[];
private Iterator it;
private Class type = null;
IndexMapper(Object map[], Iterator indicies) {
this.map = map;
this.it = indicies;
type = map.getClass().getComponentType();
}
public Object next() {
int current[] = (int []) it.next();
Object trans[] = null;
trans = (Object[]) Array.newInstance(type,current.length);

for (int i=0; i<trans.length; i++)
trans[i] = map[current[i]];
return trans;
}
public boolean hasNext() {
return it.hasNext();
}
public void remove() {
it.remove();
}
}

Here is PossibleSets:
import java.util.*;
/**
This class enumerates subsets of arbitrary sets;
The iterator operations are not synchronized.
*/
final public class PossibleSets {
private int n, k;
private Object map[];
public PossibleSets(int from, int choose) {
n = from;
k = choose;
if (n<=0 || k<=0)
throw new IllegalArgumentException(
"Cannot generate sets from zero or negative parameters.");
if (k>n)
throw new IllegalArgumentException(
"Too many elements asked for.");
map = null;
}
public PossibleSets(Object from[], int choose) {
this(from.length,choose);
map = from;
}

public long count() {
long c = 1;
long local_n = n;
long local_k = k;

while (local_k > 0)
{
c = c * local_n;
if (c < 0)
throw new IllegalArgumentException("Number too large.");
--local_n;
--local_k;
}
local_k = k;
while (local_k > 0)
{
c = c / local_k;
--local_k;
}

return c;
}

public Iterator iterator() {
if (map == null)
return new Provider(n,k);
else
return new IndexMapper(map, new Provider(n,k));
}
private class Provider implements Iterator {
private int set[];
private boolean primedWithAValue = false;
/** @return int [] */
public Object next() {
if (! primedWithAValue)
throw new NoSuchElementException("No more sets to access.");
int returnSet[] = new int[k];
for (int i=0;i<k;i++)
returnSet[i] = set[i];
prepareForCalls();
return returnSet;
}
public boolean hasNext() {
return primedWithAValue;
}
Provider(int n, int k) {
set = new int[k];
for (int i=0; i<k; i++) {
set[i] = i;
}
primedWithAValue = true;
}

private void prepareForCalls() {
if ( thereAreMorePossibleSets() )
{
primedWithAValue = true;
}
else
{
primedWithAValue = false;
}
}
private boolean thereAreMorePossibleSets() {
// generate next combination in lexicographical order
int i = k - 1; // start at last item

while (i>=0 && set[i] == (n - k + i)) // find next item to
increment
--i;

if (i < 0) return false;
++set[i];

for (int j = i + 1; j < k; j++)
set[j] = set[i] + j - i;
return true;
}
public void remove() { throw new UnsupportedOperationException(); }
}
static private ArrayList arrayOfIntegers(Object o) {
int a[] = (int []) o;
ArrayList al = new ArrayList();
for (int i=0; i<a.length; i++)
al.add(new Integer(a[i]));
return al;
}
static public void main(String args[]) {
PossibleSets s = new PossibleSets(new Integer(args[0]).intValue(),
new Integer(args[1]).intValue());
System.out.println("setcounts="+s.count());
for (Iterator it=s.iterator(); it.hasNext(); )
System.out.println("next="+arrayOfIntegers(it.next ()));
}
}


Here is Permutations:
import java.util.*;
final public class Permutations {
private int n, k;
private Object map[];
public Permutations(int from, int choose) {
n = from;
k = choose;
if (n<=0 || k<=0)
throw new IllegalArgumentException("Cannot generate permutations
from zero or negative parameters.");
if (k>n)
throw new IllegalArgumentException("Too many elements asked
for.");
map = null;
}
public Permutations(Object o[], int choose) {
this(o.length,choose);
map = o;
}
public long count() {
long c = 1;
long local_n = n;
long local_k = k;

while (local_k > 0)
{
c = c * local_n;
if (c<0)
throw new IllegalArgumentException("Number too large.");
--local_n;
--local_k;
}

return c;
}

public Iterator iterator() {
if (map == null)
return new Provider(n,k);
else
return new IndexMapper(map, new Provider(n,k));
}
private class Provider implements Iterator {
private int perm[];
private boolean primedWithAValue = false;
private Iterator sets = null;
/** @return int [] */
public Object next() {
if (! primedWithAValue)
throw new NoSuchElementException("No more permutations to
access.");
int returnPerm[] = new int[k];
for (int i=0; i<k; i++)
returnPerm[i]=perm[i];
prepareForCalls();
return returnPerm;
}
public boolean hasNext() {
return primedWithAValue;
}
Provider(int n, int k) {
sets = new PossibleSets(n,k).iterator();
perm = (int []) sets.next();
primedWithAValue = true;
}

private void prepareForCalls() {
if ( thereAreMorePermutationsInCurrentSet() )
{
int i = k - 1;
while (perm[i-1] >= perm[i])
i--;
int j = k;
while (perm[j-1] <= perm[i-1])
j--;

swap(i - 1, j - 1);

i++;
j = k;

while (i < j)
{
swap(i - 1, j - 1);
i++;
j--;
}
primedWithAValue = true;
}
else if (thereAreMoreSets())
{
perm = (int[]) sets.next();
primedWithAValue = true;
}
else
{
primedWithAValue = false;
}
}
private void swap(int a, int b)
{
int temp = perm[a];
perm[a] = perm[b];
perm[b] = temp;
}
private boolean thereAreMorePermutationsInCurrentSet() {
int i = k - 1;
while (i>=1 && (perm[i-1] >= perm[i]))
i--;

return i >= 1;
}
private boolean thereAreMoreSets() {
return sets.hasNext();
}
public void remove() { throw new UnsupportedOperationException(); }
}


static private ArrayList arrayOfIntegers(Object o) {
int a[] = (int []) o;
ArrayList al = new ArrayList();
for (int i=0; i<a.length; i++)
al.add(new Integer(a[i]));
return al;
}
static public void main(String args[]) {
Permutations p = new Permutations(new Integer(args[0]).intValue(),
new Integer(args[1]).intValue());
System.out.println("permcounts="+p.count());
for (Iterator it=p.iterator(); it.hasNext(); )
System.out.println("next="+arrayOfIntegers(it.next ()));
}
}

 
Reply With Quote
 
opalpa@gmail.com opalinski from opalpaweb
Guest
Posts: n/a
 
 
Reply With Quote
 
Chris Uppal
Guest
Posts: n/a
 
      05-09-2006
(E-Mail Removed) wrote:

> btw, How do I check for overflow on multiplication in Java (or any
> other arithmetic operation)?


You might find the book mentioned in the class JavaDoc for java.lang.Integer
intersting.

-- chris


 
Reply With Quote
 
Oliver Wong
Guest
Posts: n/a
 
      05-09-2006
<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
>
> btw, How do I check for overflow on multiplication in Java (or any
> other arithmetic operation)?


The simplest way is to check for integer overflow is to do the
multiplication in floating point precision, and check if the result is
larger than what would fit in whatever primitive type you're trying to store
the value in.

e.g.

<pseudocode>
int a, b, result;
double temp = (double)a * (double)b;
if (temp > max_int_value) {
handleOverFlow();
} else {
result = (int)temp;
}
</pseudocode>

In the case of int, you could use long instead of double.

- Oliver

 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      05-09-2006
Oliver Wong wrote:
> <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) oups.com...
>
>>
>> btw, How do I check for overflow on multiplication in Java (or any
>> other arithmetic operation)?

>
>
> The simplest way is to check for integer overflow is to do the
> multiplication in floating point precision, and check if the result is
> larger than what would fit in whatever primitive type you're trying to
> store the value in.
>
> e.g.
>
> <pseudocode>
> int a, b, result;
> double temp = (double)a * (double)b;
> if (temp > max_int_value) {
> handleOverFlow();
> } else {
> result = (int)temp;
> }
> </pseudocode>
>
> In the case of int, you could use long instead of double.
>
> - Oliver


Note that this should only be used, as written, for int and smaller
types, not long. It depends on all int values being exactly
representable as doubles, so that if there is no overflow temp does
contain the exact answer.

This program:

public class TestMult {
public static void main(String[] args) {
long a = 0x0fffffffffffffffL;
long b = 3;
long result=0;
double temp = (double)a * (double)b;
if (temp > Long.MAX_VALUE) {
handleOverFlow();
System.exit(3);
} else {
result = (long)temp;
}
System.out.println("result="+result+" correct answer="+a*b);
}
private static void handleOverFlow() {
System.out.println("Overflow detected");
}
}

prints:

result=3458764513820540928 correct answer=3458764513820540925

For long, using BigInteger instead of double would be slower but more
reliable.

Patricia
 
Reply With Quote
 
Chris Uppal
Guest
Posts: n/a
 
      05-09-2006
Patricia Shanahan wrote:

> Note that this should only be used, as written, for int and smaller
> types, not long. It depends on all int values being exactly
> representable as doubles, so that if there is no overflow temp does
> contain the exact answer.


I think you can get a lot closer while still staying with the same basic
approach:

=============
private static final double
fmax = (double)Long.MAX_VALUE,
fmin = (double)Long.MIN_VALUE;

public static final long
multiply(long a, long b)
throws OverflowException
{
double
floatA = (double)a,
floatB = (double)b,
floatC = floatA * floatB;

if (floatC < fmin
|| floatC > fmax)
throw new OverflowException("" + floatC);

return a * b;
}

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

I don't think that can ever fail to notice an overflow condition, and whenever
it does return a value that value is correct. I think it can only get it wrong
(i.e. throw when it doesn't have to) are for values of floatC which are > fmax
due /only/ to rounding, and similarly at the other end of the range. I'm not
sure how many such values there are (nor how many floating-point
multiplications can actually yield them) but an ULP is only 2048 at that range,
so I don't think there can be many.

An alternative formulation which is very marginally slower, but which I don't
think has the false-negative problem at all is:

=============
public final long
multiply(long a, long b)
throws OverflowException
{
long c = a * b;
double fTrue = (double)a * (double)b;
double fMaybe = (double)c;

if (fTrue != fMaybe)
throw throwable;

return c;
}

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

But I'm not really sure whether that is actually correct for all possible
multiplications...

-- chris


 
Reply With Quote
 
opalpa@gmail.com opalinski from opalpaweb
Guest
Posts: n/a
 
      05-11-2006
Thank you all for your technique.

Opalinski
(E-Mail Removed)
http://www.geocities.com/opalpaweb/

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Recursive descent algorithm able to parse Python? seberino@spawar.navy.mil Python 9 10-07-2006 03:34 AM
Look for recursive algorithm jacksu Java 11 06-16-2006 03:14 PM
Re: Recursive combinations algorithm alexey.pyatovskiy@gmail.com C++ 0 02-15-2005 06:03 AM



Advertisments