Need help with Permutations
I'm writing a program that reads a city with x,y coordinates from a test file. It has to Permutate all the cities except the first and last city in the text file. It also needs to get an average of the x,y coordinates and then print the cities in the order in which they were permutated along with the average. My code seems to be leaving out the permutation all together but taking the average of all the coordinates, and only printing the first city. If any one can help me with this, I would greatly appreciate it. Not exactly sure what would be the best way to post my code on here, but here goes:
public static void rotate(int first, int last)
{
String temp = City[first];
for(int i = first; i < last - 1; i++)
{
City = City[i+1];
}
City[last - 1] = temp;
return;
}
//-
public static void perm(int first, int last)
{
if(last - first == 1)
{
for(int j=0; j < City.length; j++)
{
System.out.print(City[j] + " ");
}
System.out.println();
return;
}
else
{
for(int i =last-first; i>=1;i--)
{
perm(first+1, last);
rotate(first, last);
}
}
}
} //end CityList
//--
class CityListApp
{
public static void main (String[] args) throws FileNotFoundException, IOException
{
perm(1,4);
Reader fr = new FileReader ("c:/CityList.txt");
StreamTokenizer frstream = new StreamTokenizer(fr);
frstream.parseNumbers();
frstream.eolIsSignificant(true);
frstream.nextToken();
while(frstream.ttype != StreamTokenizer.TT_EOF)
{
double sum = 0;
int count = 0;
String City = frstream.sval;
frstream.nextToken();
while (frstream.ttype != StreamTokenizer.TT_EOF)
{
sum += frstream.nval;
count++;
frstream.nextToken();
}
double avg = sum / count;
DecimalFormat fmt = new DecimalFormat("0.00");
System.out.println(City + fmt.format(avg));
frstream.nextToken();
}
}
private static void perm(int i, int j) {
// TODO Auto-generated method stub
}
[2261 byte] By [
Nic_C78a] at [2007-11-27 8:36:04]
The best way to post code is to wrap it in [code][/code] tags.When you create a post, there are several buttons above the text entry window. One says "code". Click that button and it creates the code tags for you automatically.
oh, ok, thank you! I'll know better for next time.
At the very bottom of the code there is a part that says
private static void perm(int i, int j) {
// TODO Auto-generated method stub
}
Is this what's causing the problem (it may be overriding the other method named perm)?
Also, it's difficult to tell which classes the top two methods are in.
@modia at 2007-7-12 20:32:50 >
> At the very bottom of the code there is a part that
> says
>
> > private static void perm(int i, int j) {
> // TODO Auto-generated method stub
>
> }
>
>
> Is this what's causing the problem (it may be
> overriding the other method named perm)?
I don't believe that is the problem. I get the same result when I comment it out. I'm thinking that the perm and rotate method are not being called at all.
>
> Also, it's difficult to tell which classes the top
> two methods are in.
They are in my CityList class. Here's my full code:
public CityList(int max)
{
City = new String[max];
Elems = 0;
}
//--
public void insert (String cities)
{
City[Elems] = new String(cities);
Elems++;
}
public String getItem(int l)
{
return City[l];
}
//
public void display()
{
System.out.print("City + j");
}
//
public static void rotate(int first, int last)
{
String temp = City[first];
for(int i = first; i < last - 1; i++)
{
City[i] = City[i+1];
}
City[last - 1] = temp;
return;
}
//-
public static void perm(int first, int last)
{
if(last - first == 1)
{
for(int j=0; j < City.length; j++)
{
System.out.print(City[j] + " ");
}
System.out.println();
return;
}
else
{
for(int i =last-first; i>=1;i--)
{
perm(first+1, last);
rotate(first, last);
}
}
}
} //end CityList
//--
class CityListApp
{
public static void main (String[] args) throws FileNotFoundException, IOException
{
//perm(1,4);
Reader fr = new FileReader ("c:/CityList.txt");
StreamTokenizer frstream = new StreamTokenizer(fr);
frstream.parseNumbers();
frstream.eolIsSignificant(true);
frstream.nextToken();
while(frstream.ttype != StreamTokenizer.TT_EOF)
{
double sum = 0;
int count = 0;
String City = frstream.sval;
frstream.nextToken();
while (frstream.ttype != StreamTokenizer.TT_EOF)
{
sum += frstream.nval;
count++;
frstream.nextToken();
}
double avg = sum / count;
DecimalFormat fmt = new DecimalFormat("0.00");
System.out.println(City + fmt.format(avg));
frstream.nextToken();
}
}
//private static void perm(int i, int j)
//{
// TODO Auto-generated method stub
//}
}
Any help I can get will be greatly appreciated.
In this posting, you are missing part of the CityList class code, probably the part where fields are definied.
when you say permutate, you mean go through all the combinations of two cities? all cities? Is order important -- are we dealing with permutations or combinations? What is the goal of the program? To find the average x and y of cities?
Please redefine the problem and be as precise as possible.
Good luck!
> when you say permutate, you mean go through all the
> combinations of two cities? all cities? Is order
> important -- are we dealing with permutations or
> combinations? What is the goal of the program? To
> find the average x and y of cities?
The program needs to go through all the combinations of let's say 4 cities, but it has to leave the first(source) and the last(destination) in the text file in the same place. example is: Jax, Tampa, Miami, Orlando and the program would permutate Tampa and Miami while leaving Jax and Orlando as the source and desitnation.
>
> Please redefine the problem and be as precise as
> possible.
I have it working right now, without the permutaion. It's almost like the program is not calling my perm and rotate method. I'm not sure I have those methods right either.
>
> Good luck!
Thanks! I need all the luck I can get right now =)
1) Are you trying to compare the differences in distances between different routes, when flying from one city to another?
2) Are you sure that you are going to be manipulating an array of Strings? It seems more logical to me to have an array of City objects where City has name and location (x and y coordinates).
3) Would it be better to use ArrayList<City> rather than array of City if you don't know in advance how big the array will be?
> 1) Are you trying to compare the differences in
> distances between different routes, when flying from
> one city to another?
***Yes, I think I have that part done. It just doesn't change the order that the cities are pulled from the text file.
>
> 2) Are you sure that you are going to be
> manipulating an array of Strings? It seems more
> logical to me to have an array of City objects where
> City has name and location (x and y coordinates).
***The String array seems to be working other than the permutation.
>
> 3) Would it be better to use ArrayList<City> rather
> than array of City if you don't know in advance how
> big the array will be?
***Not sure, I know the size of the array, because I created the text file. I may try that if I can't get it right the way I have it.
> > 1) Are you trying to compare the differences in
> > distances between different routes, when flying
> from
> > one city to another?
>
> ***Yes, I think I have that part done. It just
> doesn't change the order that the cities are pulled
> from the text file.
So if distance, do you have to use the equation:
distance = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
?
> > 2) Are you sure that you are going to be
> > manipulating an array of Strings? It seems more
> > logical to me to have an array of City objects
> where
> > City has name and location (x and y coordinates).
>
> ***The String array seems to be working other than
> the permutation.
But each City is defined by its name and x and y location. The information is tied together, correct? If so, a Class of City that encapsulates this information seems the correct way to go in the long run. It would seem that you need more than just a listing of cities in different orders, but a listing of order and how it affects the relative distances. All this info is tied together and again, should be encapsulated.
Or am I missing something?
> > > 2) Are you sure that you are going to be
> > > manipulating an array of Strings? It seems more
> > > logical to me to have an array of City objects
> > where
> > > City has name and location (x and y
> coordinates).
> >
> > ***The String array seems to be working other than
> > the permutation.
>
> But each City is defined by its name and x and
> y location. The information is tied together,
> correct? If so, a Class of City that
> encapsulates this information seems the
> correct way to go in the long run. It would seem
> that you need more than just a listing of cities in
> different orders, but a listing of order and how
> it affects the relative distances. All this info
> is tied together and again, should be encapsulated.
>
> Or am I missing something?
*** oh, ok. I think I know what you're saying now. I need to create another class for City Instead of just trying to define the varibles within the class CityList. Do I understand you correctly? Sorry, I don't have the vocabulary down good yet, so I get a little lost. =)
Anoher question, How would I call the perm method in the App. I can't figure out how and where to put it?
I'm still trying to grok your specifications. What does the text file look like? Can you print out a sample here?
And where are you creating your array of City as you input data? Without the array, you can't do permutations.
And, have you tested your permutation function in a small test app (without the file input and all that fancy stuff)? Are you sure that it doesn't have an infinite loop in it?
Message was edited by:
petes1234
> Anoher question, How would I call the perm method in
> the App. I can't figure out how and where to put it?
You need to instantiate a new CityList object and then call the perm(...) method on that variable in your main method.
Like this:
CityList list = new CityList(10);
list.perm(0,9);
> I'm still trying to grok your specifications. What
> does the text file look like? Can you print out a
> sample here?
>
Here's what it looks like in NotePad:
Jacksonville,15,30
Tampa,35,20
Orlando,55,30
Miami,40,45
> And where are you creating your array of City as you
> input data? Without the array, you can't do
> permutations.
I tried this:
> int Size = 50;
Object [] City;
City = new Object (Size);
But it didn't seem to want to work with what I have, so I took it out. I guess I should try it with the Object class?
And, have you tested your permutation function in a
> small test app (without the file input and all that
> fancy stuff)? Are you sure that it doesn't have an
> infinite loop in it?
No I haven't.
>
> Message was edited by:
> petes1234
> You need to instantiate a new CityList object and
> then call the perm(...) method on that variable in
> your main method.
> Like this:
> CityList list = new CityList(10);
> list.perm(0,9);
But before permuting he has to fill the list. for that he needs to first create a City class, make the list a list of this Object, then enter objects into the list from the text file, then permute it.
> Here's what it looks like in NotePad:
> Jacksonville,15,30
> Tampa,35,20
> Orlando,55,30
> Miami,40,45
Ok, may I suggest reading the file line by line and then splitting on the comma.
A file can be read very easily by the java.util.Scanner class:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Scanner.html (code samples there as well!)
I find the Scanner class to be far easier than how you are parsing the file now.
> int Size = 50;
> bject [] City;
> City = new Object (Size);
>
> But it didn't seem to want to work with what I have,
> so I took it out. I guess I should try it with the
> Object class?
No, petes meant that you need to create a custom object (not an Object!) that represents a city. Here's what that class would look like:
public class City {
private String name;
private int x;
private int y;
public City(String name, int x, int y) {
this.name = name;
this.x = x;
this.y = y;
}
// the rest of City's methods
}
Now you can create an array of these City objects like this:
City[] cities = new City[10];
cities[0] = new City("Rotterdam", 50, 60);
Oh, and use Java's code conventions! Class names start with a capital but variable names and methods start with a small letter. Please follow these "rules".
> No I haven't.
You should do that then.
> ...
> But before permuting he has to fill the list. for
> that he needs to first create a City class, make the
> list a list of this Object, then enter objects into
> the list from the text file, then permute it.
Yes, the OP has quite some work to do!
; )
don't work with Object. There are better ways. Create a class City and make a list of this. Here is a for instance that doesn't use your model, but is close enough for you to learn from:
First class, my Foo class:
public class Foo
{
private String name;
private double a, b;
public Foo(String name, double a, double b)
{
this.name = name;
this.a = a;
this.b = b;
}
public String getName()
{
return name;
}
public double getA()
{
return a;
}
public double getB()
{
return b;
}
@Override
public String toString()
{
return "Foo: " + this.name + " (" + a + ", " + b + ")";
}
}
Next, a FooList class:
import java.util.ArrayList;
import java.util.List;
public class FooList
{
private List<Foo> foos;
public FooList()
{
foos = new ArrayList<Foo>();
}
public void addFoo(Foo f)
{
foos.add(f);
}
public int size()
{
return foos.size();
}
public Foo getFoo(int i)
{
if (i < 0 || i >= foos.size())
{
return null;
}
else
{
return foos.get(i);
}
}
public double getAverageA() //throws ArithmeticException
{
if (foos.size() == 0)
throw new ArithmeticException("can't divide by zero");
else
{
double temp = 0.0;
for (int i = 0; i < foos.size(); i++)
{
temp += foos.get(i).getA();
}
return temp / foos.size();
}
}
public double getAverageB() //throws ArithmeticException
{
if (foos.size() == 0)
throw new ArithmeticException("can't divide by zero");
else
{
double temp = 0.0;
for (int i = 0; i < foos.size(); i++)
{
temp += foos.get(i).getB();
}
return temp / foos.size();
}
}
And finally, TestFooList class:
public class TestFooList
{
public static void main(String[] args)
{
FooList myFooList = new FooList();
myFooList.addFoo(new Foo("A", 0.0, 1.0));
myFooList.addFoo(new Foo("B", 2.0, 4.0));
myFooList.addFoo(new Foo("C", 5.0, 2.0));
myFooList.addFoo(new Foo("D", 9.0, 5.0));
System.out.println("myFooList:");
for (int i = 0; i < myFooList.size(); i++)
{
System.out.println(myFooList.getFoo(i));
}
System.out.println();
System.out.println("Average 'a' = " + myFooList.getAverageA());
System.out.println("Average 'b' = " + myFooList.getAverageB());
}
}
Message was edited by:
petes1234
Thank you so much for all your help, both of you!! I should be ok now. I appreciate it!=)
ok, so I'm not quite as ok as I thought I would be. I changed from an Array to List and I'm getting the error:
The type of the expression must be an array type but it resolved to List
Here's the part of the code that I'm getting the error on:
public static void rotate(int first, int last)
{
List temp = cityname[first];
for(int i = first; i < last - 1; i++)
{
cityname[i] = cityname[i+1];
}
cityname[last - 1] = temp;
return;
}
Any ideas on how to fix it? Thanks!
This rotate looks all wrong. I have to see the rest of your code.
I'm assuming that you now have a generic list of city like so:
List<City> cityList;
and that if so, a better rotate may be simply:
public void rotate(int first, int last)
{
City temp = cityList.remove(first); // removes the first from the arraylist
cityList.add(last - 1, temp); // replaces the first at the last -1 position
// though may need to make it cityList.add(last - 2, temp);
// since the List has been shortened by the prior removal
}
Message was edited by:
petes1234
Here's a copy of my code:
class City
{
public static int length;
private String name;
private int x;
private int y;
public City(String name, int x, int y)
{
this.name = name;
this.x = x;
this.y = y;
}
public String getName()
{
return name;
}
public double getX()
{
return x;
}
public double getY()
{
return y;
}
}
//CityList.java
//demonstrates use of Recursion using text file
//to run this program c>java CityListApp
//////////////////////////////////////////////////////////////////////////
class CityList
{
private static List cityname;
//--
public CityList()
{
cityname = new ArrayList();
}
//--
public void addCity (City c)
{
cityname.add(c);
}
public int size()
{
return cityname.size();
}
public City getCity (int i)
{
if(i < 0 || i >= cityname.size())
{
return null;
}
else
{
return (City) cityname.get(i);
}
}
//
public void display()
{
System.out.print("City + j");
}
//
public static void rotate(int first, int last)
{
List temp = cityname[first];
for(int i = first; i < last - 1; i++)
{
cityname[i] = cityname[i+1];
}
cityname[last - 1] = temp;
return;
}
//-
public void perm(int first, int last)
{
if(last - first == 1)
{
for(int j=0; j < City.length; j++)
{
System.out.print(cityname + " ");
}
System.out.println();
return;
}
else
{
for(int i =last-first; i>=1;i--)
{
perm(first+1, last);
rotate(first, last);
}
}
}
I'll try your suggestion. Thanks!
I tried your suggestion and that error went away, but now I'm getting an IndexOutOf BoundsException error. Do you see what it is in my code that's causing this? I can't find the issue, but I'm about to debug it.
A couple of suggestions:
I'm not sure that you need this static variable. What purpose does it serve that CityList.size() can't handle?
class City
{
public static int length; // I'm not sure that you need this variable
private String name;
.....
make your list generic and non-static (make it an instance variable). Maybe I'm wrong, but I feel that you are loosing oop-ness by making this static.
class CityList
{
//private static List cityname;
//make this generic (add the <City>) and get rid of the static modifier
private List<City> cityname;
public CityList()
{
//cityname = new ArrayList();
//make this generic
cityname = new ArrayList<City>();
}
get rid of rotate's static modifier if possible. change the method.
//get rid of static modifier
public void rotate(int first, int last)
{
//scrap what you had
//my suggested method:
City temp = cityname.remove(first);
cityname.add(last - 1, temp);
}
Again, City.length seems redundant when cityname.size should do.
public void perm(int first, int last)
{
if(last - first == 1)
{
//for(int j=0; j < City.length; j++)
//change to
for(int j=0; j < cityname.size(); j++)
{
//System.out.print(cityname + " "); // check out the "get" method from arraylist
System.out.print(cityname.get(j).getName() + " ");
}
System.out.println();
return;
}
else
{
for(int i =last-first; i>=1;i--)
{
perm(first+1, last);
rotate(first, last);
}
}
}
Test the code to see what happens
public static void main(String[] args)
{
CityList cl = new CityList();
cl.addCity(new City("A", 1, 2));
cl.addCity(new City("B", 1, 2));
cl.addCity(new City("C", 1, 2));
cl.addCity(new City("D", 1, 2));
cl.perm(0, cl.size());
}
}
GOT IT!!! Your test works perfect!
My code of course does not:
It's still not giving me the different combinations. The output is still just the list of ciites in the same order as they are in the text file.
class CityListApp
{
public static void main (String[] args) throws FileNotFoundException, IOException
{
CityList list = new CityList();
list.perm(0, list.size());
Reader fr = new FileReader ("c:/CityList.txt");
fr = new BufferedReader(fr);
StreamTokenizer frstream = new StreamTokenizer(fr);
frstream.parseNumbers();
frstream.eolIsSignificant(true);
frstream.nextToken();
while(frstream.ttype != StreamTokenizer.TT_EOF)
{
double sum = 0;
int count = 0;
String City = frstream.sval;
frstream.nextToken();
while (frstream.ttype != StreamTokenizer.TT_EOL)
{
sum += frstream.nval;
count++;
frstream.nextToken();
}
double avg = sum / count;
DecimalFormat fmt = new DecimalFormat("0.00");
System.out.println(City + fmt.format(avg));
frstream.nextToken();
}
}
} //end of CityListApp
There are easier ways of getting text input. I suggest the following:
1) Read about the Scanner class here:
http://java.sun.com/docs/books/tutorial/essential/io/scanning.html
2) Read about the String split function. This can easily parse each line using the comma as delimiter.
http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html#split(java.lang.String)
3) Use a while block to read in each line. Split the line, then create a new City object using the splitted string result
4) Add the newly created City object to your list.
5) Permute to your hearts content.
Thank you so much for ALL of your help!!!
