Obtain Permutations of Items in VBA 6

[rubbernilly]

Is there some code template that will give me permutations of items of 'X' amount.

Given five items I want to return:

12345
12354
12534
15234
12435
14235
13245
21345
etc.

For this thread, the items can be phrased in terms of rows in a DAO.Recordset... any thoughts?

 

[MajP]

Boxhead,
Forgot the site

http://odysseus.nat.uni-magdeburg.de/~mertens/TSP/

 

[BoxHead]

Thanks, MajP. I took a quick look and saw that the Lin-Kernighan exchange is touted as being viewable "in the future".

I've gotten side-tracked by another approach. After my last post, I realized that we really do know that there is no path that could produce a result lower than the sum of the lowest 49 trips - 7,490 miles. Not possible. So I'm trying to sequence the trips to fit the answer.

Not as easy and straight-forward as I imagined while driving.

I'll do a google search on Lin-Kernighan in the morning and see if I can get a path.

Thanks again.


John







"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him beacause when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[rubbernilly]

Using my last couple of coding options, I have constructed a form with the ability to pick cities in one listbox to add them to another (automatically generating the distance for that city order), the ability to re-order that second listbox (with real-time calculation of the current distance), and the ability to run permutations either between these cities (as if they were the only cities you had to visit), or from those cities (using the current order and distance as your start-feed).

It looks like it is working well. If it passes some more break-testing, I'll post it on a server for download for anybody interested.

 

[MajP]

I coded a 2-opt insertion optimization. This is the best route I can get, assuming I did things right: 1154 Sm or 9873 NM. Here is the route:

strStartCity	strEndCity	Dist
Annapolis	Dover AFB	61
Dover AFB	Harrisburg	101
Harrisburg	Trenton Co	106
Trenton Co	Albany	182
Albany	       Hartford	  92
Hartford	Providence	63
Providence	Boston	49
Boston	Concord	62
Concord	Augusta	115
Augusta	Montpelier	135
Montpelier	Lansing	614
Lansing	Madison	241
Madison	Minn/StPaul	228
Minn/StPaul	Bismarck	386
Bismarck	Helena	533
Helena	Olympia	516
Olympia	Salem	142
Salem	Sacramento	450
Sacramento	Carson City	103
Carson City	Boise	356
Boise	Salt Lake City	291
Salt Lake City	Phoenix	508
Phoenix	Santa Fe CO	371
Santa Fe CO	Denver	293
Denver	Cheyenne	97
Cheyenne	Pierre	321
Pierre	Lincoln Co	303
Lincoln Co	Des Moines	168
Des Moines	Topeka	200
Topeka	Little Rock	354
Little Rock	Oklahoma City	307
Oklahoma City	Austin	353
Austin	Baton Rouge	391
Baton Rouge	Jackson	139
Jackson	Montgomery	217
Montgomery	Tallahassee	182
Tallahassee	Columbia	312
Columbia	Atlanta	191
Atlanta	Nashville	213
Nashville	Jefferson City	347
Jefferson City	Springfield	160
Springfield	Indianapolis	180
Indianapolis	Frankfort	131
Frankfort	Columbus	167
Columbus	Charleston	132
Charleston	Raleigh/Durham	233
Raleigh/Durham	Richmond	138
Richmond	DC	95
DC	Annapolis	25
                                 11354

This started with our best nearest neighbor solution of 12156 SM. This is within 6%, which should be expected of a nearest neighbor solution. This algorithm takes about 2-3 minutes to run. Rubbernilly, I would like to see the route that is down to 8600. I am a little skeptical. Assuming I done this right (big assumption), this should be 2 optimized. I can not imagine an algorithm that can beat this by 13%.

 

[rubbernilly]

It is my friend's machine (still running at his house) that has the ~8300 best, but as far as the algorithm running it is the same one I posted as "EnMediaRes" (with a couple more optimizations as far as opening a snapshot rather than a dynaset, and not filling variables until after the test for istep =48, and not returning records where that new distance and the current distance would put us greater than the existing. It obviously takes some time to run (a couple of days for all cities, hop limit of nearest 3).

But now, with the form I built, I have greater control over the start city and available cities. I've run Lincoln west, Austin west, and a couple of others mid-country just to see what would be the best there.

We also ran a 3 hop limit for August to Richmond to determine the best path there. So now I'm running the cities between with a 3 hop limit to see how best to bridge. Here is one plot solution:

Augusta to Olympia (via Lincoln as bridge): 8612.8 NM
Augusta
Montpelier
Concord
Boston
Providence
Hartford
Albany
Trenton
Harrisburg
Dover
Annapolis
Washington DC
Richmond
Raleigh/Durham
Columbia
Atlanta
Tallahassee
Montgomery
Nashville
Frankfort
Charleston
Columbus
Indianapolis
Lansing
Madison
Minneapolis/St. Paul
Des Moines
Springfield
Jefferson City
Little Rock
Jackson
Baton Rouge
Austin
Oklahoma City
Topeka
Lincoln
Pierre
Bismarck
Cheyenne
Denver
Santa Fe
Phoenix
Salt Lake City
Helena
Boise
Carson City
Sacramento
Salem
Olympia


And here is another solution that is still less:

Augusta to Olympia (via St. Paul as bridge): 8506.56 NM
Augusta
Montpelier
Concord
Boston
Providence
Hartford
Albany
Trenton
Harrisburg
Dover
Annapolis
Washington DC
Richmond
Raleigh/Durham
Columbia
Atlanta
Tallahassee
Montgomery
Nashville
Frankfort
Charleston
Columbus
Lansing
Indianapolis
Springfield
Jefferson City
Little Rock
Jackson
Baton Rouge
Austin
Oklahoma City
Topeka
Lincoln
Des Moines
Madison
Minneapolis/St. Paul
Bismarck
Pierre
Cheyenne
Denver
Santa Fe
Phoenix
Salt Lake City
Helena
Boise
Carson City
Sacramento
Salem
Olympia


So, is it that the algorithm is more accurate? Yes, without human optimization we got to ~8300. It is, however, far less efficient in time compared to yours.

The two I posted here were reliant on some human optimization and best case testing.

 

[MajP]

I forgot that you are not doing a closed loop. So my algorithm may not give a best solution for the open loop problem. Even if I take out a leg I can only get down to 9340.

 

[BoxHead]

MajP,

It's interesting that when you take out the longest distance in your route (533 miles) to make it a one-way trip, it brings it down to 10,821 miles.

That's the same one-way trip total that your NND path generated even though it's a different route and the round trip total is better this time by 802 miles.

My best one-way trip is still at 10,615 but if I made it a round trip, it's 1,172 miles longer than the round trip you just posted.

It doesn't seem that there's much of a relationship between the one-way trips and round-trippers.






"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him because when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[MajP]

The one way trip algorithm will try to minimize the max routes. Notice how the one way solution throws out the Augusta to Olympia route or 2254 miles. Unfortunately, the way I coded my 2-opt algorithm I do not think I can easily modify it to check one way trips.

 

[rubbernilly]

For anyone interested, I have copied my database up to a web folder in a zipped format.

It is pretty cool, you can draw your route on a map and get immediate distances, you can select a set of cities (with custom pop-up menus), you can go to the cities you have selected, or you can go from them to the remaining cities... you can set the hop limit for each stop... every time the database finds a shorter route it will redraw the mapped route and give you the new distance.

There are a lot of pretty cool features in this DB. It is a point to point route maker, rather than the circular route that others were plotting, but the form that maps the route can be modified pretty easily so that it plotted a circular route instead (once that algorithm was imported and implemented on the form).

If you want to download it and check it out, here is the link:

http://www.kem-tron.com/misc/capitals.zip

Thanks for all those that responded to this thread!

 

[BoxHead]

rubbernilly,

Very nice! Star quality, even.

It was good to be able to plug my best route in and see the results comparing with the mileage calculations you've used.

My best results from running a sub (8705 NM from your db -v- 10038 SM using MajP's PolarDistance) is still a couple hundred miles strong. But, I've been chipping away at it.

There are two totally different approaches I've been working on (measured in bi-polar miles between my ears).

For anyone who's interested, I've found two things helpful in improving the NND code.. First, I ranked each City's trips available 1-48 and then calculated a "cost" for skipping a trip based on how many miles would be added by selecting the next available trip for that city. I use an intersection of those two values to sort my recordset. Second, I switched from adding each trip as a new record to building a string so that once a first trip is selected, subsequent trips can be added to either end of the string. Whenever the code adds a trip to the string, it goes back to the top of the recordset (the best-ranked trips) to start looking for the next available trip. It's improved the NND results by ~600 SM and takes 12 minutes. Next step is creating multiple strings and linking them together.

The other approach I've been working on is looking at the structure of the permutations available. Bigger picture. There are patterns that lead me to believe it should be possible to predetermine the results of any given permutation (sequence) based on a sample.

Using my sample recordset with the numbers 1 through 7, you can see that if you were to build the table manually, you would put 720 1's in the first column, then 720 2's, 3's, etc. In the second column, you'd enter 120 each of 2's through 7's next to the 1's in the first column. 120 each of 1's & 3's thru 7's next to the 2's, etc. 720 = 7 Factorial. 120 = 6 Factorial. The pattern continues through out the recordset.

This has been fun and engaging stuff, rubbernilly. The numbers are admittedly huge, but they are finite and that's what makes it an exciting hunt.

My thanks go out to you for beginning the thread and my thanks to all for keeping it so interesting.


John










"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him because when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[MajP]

I am still pursuing the shortest loop solution. I still have not tried to calculate a one way trip, but my best loop using an 2-opt algorithm is 10625 SM or 9239 NM. The best loop will definately not give the best one way trip. In this loop the longest city to city path is only about 480 NM. As the loops get longer the longest city to city path in the loop gets longer so there are many longer loops with shorter one way distances (subtracting the longest path).
The algorithm is known as an improving algorithm. This algorithm starts with any loop and improves it. It takes about 2 minutes to run, although it is not efficiently coded. It takes the longest 2 non adjacent city to city paths and breaks them apart. It then tries to reconnect them in a different manner (there is only one way to do this). If the distance is shorter, it reconnects the new paths, if not it looks at the next 2 longest paths. It does this until there is no more ways to break the loop apart and find a new shorter route
The algorithm produces some interesting results. Regardless of the starting loop length, all results will beat the best NND solution. However, there is no correlation between the starting loop length and the 2-opt solution length. For example the best NND was about 1256 SM and the Next Farthest Length solution is over 70,000. Improving these solutions takes the same time (about 2 min), and gives answers aroung 10,800 SM each.
The next (better) algorithm I am going to try is a 3-opt replacement. Instead of breaking two paths apart, you break three paths. This is a lot more difficult to code, because you have many more options for putting the loop back together, and I can not figure out an easy way to ensure I do not put reconnect into multiple sub loops.
Rubernilly, I will try your best loop and see if the improving algorithm can improve it.

 

[rubbernilly]

Thanks for the star, Boxhead.

If you have any questions about the database, let me know. I know that some of my friends who have been looking at it told me that the button images did not come through... even though I used symbols from the Arial Font.... so...

Between the listboxes, from top down should be a right arrow, a left arrow, and then a double-left arrow (move all). To the right of the second listbox from top down should be an up arrow, and then a down arrow. The rest of the buttons should have text so you can read them.

Now, your string solution sounds interesting, and like something that I was considering just as a way to narrow the field of choices. It seems to me that there are going to always be cities that will occur together (in whatever direction, forward or back):

Sacramento>Carson City
Dover>Annapolis>Washington DC
Concord>Boston>Providence>Hartford
Montpelier>Augusta
Cheyenne>Denver (maybe)
Bismarck>Pierre (maybe)

There might be others. You might be able to have a stored set of these, and if you happen upon the first or last city in a string, append the rest of that string in the proper order.

MajP - I'm not sure I understand the way you break two non-adjacent cities. Are you talking not about any two non-adjacent cities but only about cities that have one stop between them?

For instance:
Salem>Sacramento>Carson City

You would break that and see if it was shorter to do any of the permutations of three things...

abc
acb
bac
bca
cab
cba

...and then move on to the next longest? Is that what you are doing? Just wondering if I have the right of it before I try to offer help on coding for a three city leg-break.

 

[BoxHead]

rubbernilly,

The database works great. The only problem I had was that my old eyes couldn't make out the map so I stretched it and adjusted the top and left points for the city, but the buttons appear as you say they should.

I plugged in a few different routes and had some fun moving things around to gage the impact of each decision.

With your 8506 NM trip posted earlier, if you move Atlanta between Montgomery and Nashville, you'll save a few miles. My algorithm can figure that out but it can't seem to understand what's happening out west. I can't find any results that optimize the last 7 or 8 stops.

MajP, 10625 SM loop. That's fantastic. When you say, This algorithm starts with any loop and improves it, doesn't that mean there are 48! loops to check? Are you using NND as a starting point or some other means to narrow down the starting loops?

BTW, to put this question in a different perspective, go to the US Patent Office web site and ceck out patent number 6954649.

http://patft.uspto.gov

"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him because when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[MajP]

Boxhead,
The algorithm is independant of the starting loop. I used the NND and basically the opposite Next Farthest Distance (a 70,000 mile loop for those who enjoy traveling). Either way the answer comes out about the same in the same amount of time (about 2 min on 300mhz).
It takes more than N^2 checks, but less than N^3. For example if you have this loop.

Augusta Montpelier
Montpelier Concord
Concord Boston
Boston Providence
Providence Augusta.

It will start with the Aug-Mont as path one. It will select a second path from the remaining paths. It will exclude Mont-Conc, and Prov-Augusta as a second paht. It excludes these two paths because they are adjacent to Aug-Mont (they share either Augusta or Montpelier).
So it take the Aug-Mont path one and first the Conc-Bost path two and tries to reconnect Augusta to Concord and Montpeler to Boston. If this switch is overall shorter it makes the connection. If not it goes to the next comparison of Aug-Mon and Bos-Prov.
Lets say the original switch to Aug-Conc and Mont-Bost produces a shorter route then it makes the switch. Then there is one more step. I have to redirect Mont-Conc to Conc-Mont so that the new loop becomes
Augusta Concord
Concord Montpelier
Montpelier Boston
Boston Providence
Providence Augusta.
After it works with Aug-Mont and all its Nonadjacent Paths it starts with the next path one and compares it to all its non adjacent paths.

 

[BoxHead]

MajP,

I gothcya. You call them loops and I call them trips. I start with a trip/loop and connect it to the next best trip/loop based on distance and 'cost'. That becomes my new trip/loop.

I start with
Madison > 240.64 < Lansing
add on the next best connection for Madison or Lansing
Minneapolis > 228.23 < Madison > 240.64 < Lansing
go back to the top of the list and add the next best connection/trip/loop for either Minneapolis or Lansing.

It sounds like you're already past my "next step" of adding a second trip/loop. Good work.

I don't know if it's helpful for your adding the third loop/trip to your algorithm, but my plan for adding a second is to create variables for each and if the 'next best trip' happens to link the two of them together, create a new 'second' trip. My algorithm is based on a ranking system of all trips and the recordset is sorted by that rank, so anytime I skip an opportunity to link trips, I lose. I'm just not sure if this would apply to the order in which you're looking at records for consideration.

About the time; I'm running through the 2352 possible first trips/loops and getting 2352 complete trips in 12 minutes. Is the 2-minute timing for each 'path one' or for all 2352 of them?






"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him because when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[BoxHead]

rubbernilly,

Just wanted to let you know that your DB is getting some good use.

My ten-year-old daughter sat down and mapped out a 9400 mile route in about six minutes.

Took me close to 2 weeks before I got it that low with my algorithms. [flush]





"I could have fired him because he cut the board 2' 5" long when I asked for 25 inches.
I could have fired him because he threw that board aside to find another one when it only needed 4" cut off of it.
I had to fire him because when he threw the board, I heard him say, 'Stupid wood!'" -The Foreman

 

[rubbernilly]

Sweet!

Now, watch... she'll end up coming up with the lowest mileage route out of all of us!