# Print all possible permutations for a TSP problem

Page 1 of 1

## 6 Replies - 10142 Views - Last Post: 06 September 2010 - 05:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=189206&amp;s=ae35414488bd04378726bc141de0c8cf&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 cordwell

Reputation: 0
• Posts: 16
• Joined: 19-January 09

# Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:06 PM

Help on how to print all possible permutations city/ distance of a TSP problem using Brute Force.
E.g given a file with 3 cities, code should print all possibilities like;
1,2,3 = distance
1,3,2 = distance
2,1,3 = distance
2,3,1 = distance
...
...
...
The code should be able to do this for any file with any number of cities given although it may take time depending with the number of cities. The time taken to run each file should also be recorded and printed

This post has been edited by cordwell: 05 September 2010 - 09:09 PM

Is This A Good Question/Topic? 0

## Replies To: Print all possible permutations for a TSP problem

### #2 bcranger

• D.I.C Lover

Reputation: 252
• Posts: 1,199
• Joined: 01-February 10

## Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:10 PM

As for what you want to do, a String permutation generator should accomplish what you need...look into permutations if you want.

### #3 cordwell

Reputation: 0
• Posts: 16
• Joined: 19-January 09

## Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:19 PM

This is what I have so far, whic is specifically for 4 cities. How do I make it possible for any number of cities
```int a, b, c, d;
double dist1 = 0;
double dist2 = 0;
double dist3 = 0;
double dist4 = 0;
double totalDist = 0;

System.out.println("\nCity Path " + " \tTotal Distance ");
for(a=0; a<cityCount; a++){

for(b=0; b<cityCount; b++){

for(c=0; c<cityCount; c++){

for(d=0; d<cityCount; d++){

if(!(a==b || a==c || a==d || b==c || b==d || c==d)){
dist1 = Math.sqrt(((xpoints.get(B)/> - xpoints.get(a)) * (xpoints.get(B)/> - xpoints.get(a))) + ((ypoints.get(B)/> - ypoints.get(a)) * (ypoints.get(B)/> - ypoints.get(a))));
dist2 = Math.sqrt(((xpoints.get(c) - xpoints.get(B)/>) * (xpoints.get(c) - xpoints.get(B)/>)) + ((ypoints.get(c) - ypoints.get(B)/>) * (ypoints.get(c) - ypoints.get(B)/>)));
dist3 = Math.sqrt(((xpoints.get(d) - xpoints.get(c)) * (xpoints.get(d) - xpoints.get(c))) + ((ypoints.get(d) - ypoints.get(c)) * (ypoints.get(d) - ypoints.get(c))));
dist4 = Math.sqrt(((xpoints.get(a) - xpoints.get(d)) * (xpoints.get(a) - xpoints.get(d))) + ((ypoints.get(a) - ypoints.get(d)) * (ypoints.get(a) - ypoints.get(d))));
totalDist = dist1 + dist2 + dist3 + dist4;
System.out.println((a+1) + ", " + (b+1) + ", " + (c+1) + ", " + (d+1) + ", " + (a+1) + " \t" + totalDist);

}
}
}
}
}

```

### #4 bcranger

• D.I.C Lover

Reputation: 252
• Posts: 1,199
• Joined: 01-February 10

## Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:30 PM

Put all city numbers into a single string and generate all possible permutations. THen split each string and calculate the distances you need.

Here's a permutation generator found on google:
http://www.merriampark.com/perm.htm

### #5 cordwell

Reputation: 0
• Posts: 16
• Joined: 19-January 09

## Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:46 PM

The input is a file. Code should read file, extract all the cities and their x, y coordinates. every city has a city number, like this: This a 5 city file.

NAME: concorde5
TYPE: TSP
COMMENT: Generated by CCutil_writetsplib
COMMENT: Write called for by Concorde GUI
DIMENSION: 5
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 31.045752 75.527426
2 42.565359 77.004219
3 64.705882 76.160338
4 50.735294 33.333333
5 53.104575 90.717300

### #6 cordwell

Reputation: 0
• Posts: 16
• Joined: 19-January 09

## Re: Print all possible permutations for a TSP problem

Posted 05 September 2010 - 09:58 PM

bcranger, on 05 September 2010 - 08:30 PM, said:

Put all city numbers into a single string and generate all possible permutations. THen split each string and calculate the distances you need.

Here's a permutation generator found on google:
http://www.merriampark.com/perm.htm

I tried to use this template code but it did not work for me. I could not be able to calculate the respective distances of the cities. Since a total distance of each path posibility has to be recorded and printed too.

### #7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• Joined: 27-December 08

## Re: Print all possible permutations for a TSP problem

Posted 06 September 2010 - 05:16 PM

There are a bunch of permutation snippets in the Java Snippets section like KYA's and mostyfriedman's. There are also a few File I/O Tutorials if you need a starting point for reading in the File. The way I would model this is to use the java.awt.geom.Point2D.Double class to represent each city. And as Point2D has a distance() method which accepts another Point2D object, you just have to permute the indices for the array or List<Point2D.Double>.

So for example, if one permutation is: 23451, get elem 2 and elem 3 and find the distance, then elems 3 and 4, etc. until you get through elems 5 and 1. With a sum variable, it should be pretty straight-forward to get total distance.