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]

Rubbernilly,
If this is a pure academic drill keep at it, would not want to discourage you. If you a are looking for a one time solution, grab some code off the internet, there is a ton of code out there. The link I included above has some source code for a heuristic solutions. If you are truly looking for an exhaustive solution you are not likely going to get it on your machine in our lifetime.
Boxhead is doing what looks like a modified version of Dijkstra's shortest path algorithm. The good news is that this should run in O(N^2) complexity. So you will see a solution in our lifetime. A lot better then your NP approach. It won't be optimal, it might not even be shorter than eyeballing a solution, but it will converge.
Again take a look at the two applictions on these pages. They will give you a good idea of how complex this gets with 10-15 cities and are very interesting.

http://www.delphiforfun.org/Programs/Fences.htm

http://www.delphiforfun.org/Programs/traveling_salesman.htm

 

[BoxHead]

rubbernilly,

How does my methodology handle that?

It doesn't. Not in the least.

I was using the Next Nearest Destination as a starting point (so to speak) to avoid having to run through all of the permutations. Your example makes it clear that the assumption (the Rule) is false.

I believe that this can be approached in one of three ways.

Rules to eliminate permutations: For instance, if you only had three locations. If you were standing at one point of a triangle and your challenge was to get to the other two points in as few steps as possible, you can know that if you begin your journey along the hypotenuse of the triangle, you lose. The hypotenuse + any side of a triangle will always be more than the sum of the two sides. That's a rule that can eliminate one of your options (permutations) from consideration.

Identify the path: Distances between points are not enough. You would have to identify each step's coordinates and calculate the next step.

Speed the code to calculate all permutations: With the six-hundred-and-eleventy-jillion possible routes, how can we identify one permutation at a time. Right now, it seems we're generating our list of 6E+62 possible permutations and saying to Access, "Here, remember these and tell them to me one at a time. And while you're remembering that, calculate these other things."

If you can devise a way to determine that the 17th permuatation is a calculable sequence without calculating the 16 before and the eleventy-jillion after, then I think a combination of our solutions could work.

The append query is quick and I don't believe it requires any overhead after running (Access shouldn't have to retain the recordset in code because it is in a table).

The code I posted (albeit, based on an inaccurate assumption) does run in about 10 seconds.

Let me know what you think.






John

Use what you have,
Learn what you can,
Create what you need.

 

[MajP]

Good news. I had to bust out my linear programming notes. I noticed that on some examples with 25 cities, the heuristic solution of choosing the shortest path to the next closest city gave solutions within 6% difference above the optimal. You can do better than that by defining multiple start conditions. If you start at Richmond, make the first path to Washington. Then run it with the first to Raliegh. Then with first to Dover, etc. Initial conditions will have a big impact on this method.

 

[BoxHead]

MajP,

"linear programming notes" ???

Wow! I can't even imagine what that might be. But, I got the jist of your idea and it proved to be an exciting one. Thanks for that!
__________________________

rubbernilly,

I modified the code above to change the beginning choices for each trip from each destination. It's set up to run through the data 11 times for each origin: 539 trips. It took 3 minutes 56 seconds to run.

tStart and tEnd are textboxes I put on my form to track the timing. Comment that out if you don't want it. I added a route umber field to the tblTrips to distinguish routes.

Running the totals query on the final data really shows how the first choices can make an impact. The two shortest trips showed up on the second run through. The 3rd and 4th were from the third time through. The 5th came from the first run and the 6th showed up on the fourth run through the data.

Private Sub myTrip() 
tStart = Now()
DoCmd.SetWarnings False
DoCmd.RunSQL "DELETE * FROM tblTrips;"
DoCmd.SetWarnings True

Dim myOrigin As String, myRecent As String, myAll As String
Dim myTripNum As Integer, myRteNum
Dim myD As DAO.Database, myR1 As DAO.Recordset, myR2 As DAO.Recordset
Set myD = CurrentDb
Set myR1 = myD.OpenRecordset("SELECT DISTINCT City1 FROM Distances ORDER BY City1;", dbOpenDynaset)
myR1.MoveFirst
   For myRteNum = 0 To 10
        Do While Not myR1.EOF 'start outer loop

        myOrigin = myR1.Fields(0)
        myRecent = myOrigin
        DoCmd.SetWarnings False
            Do Until myTripNum = myR1.RecordCount - 1        'start inner loop
            Set myR2 = myD.OpenRecordset("SELECT City1, City2, Distance FROM Distances WHERE city1 = '" _
            & myRecent & "' AND city2 <> '" & myRecent & "' " & myAll & " ORDER BY distance;", dbOpenDynaset)
            myTripNum = myTripNum + 1
            myR2.MoveFirst
            If myTripNum <= myRteNum + 1 Then
            myR2.Move (myRteNum)
            End If
            DoCmd.RunSQL "INSERT INTO tblTrips (myRouteNum, myOrigin, myStopNum, myStopName,myDistance)" _
            & " SELECT " & myRteNum & ", '" & myOrigin & "', " & myTripNum & ", '" & myR2.Fields(1) & "', " & myR2.Fields(2) & ";"
            myAll = myAll & " AND city2 <> '" & myRecent & "' "
            myRecent = myR2.Fields(1)
            Loop
        myTripNum = 0
        myAll = ""
        myRecent = ""
        myOrigin = ""
        myR1.MoveNext
        Loop
        myTripNum = 0
        myAll = ""
        myRecent = ""
        myOrigin = ""
        myR1.MoveFirst
   Next myRteNum
DoCmd.SetWarnings True

tEnd = Now


End Sub

HTH





John

Use what you have,
Learn what you can,
Create what you need.

 

[rubbernilly]

Thanks guys!

Looks like I've got some research/reading to do, and some code to try.

Oh, and some stars to hand out for your help!

I'll report back how this works for me as soon as I can.

 

[MajP]

Rubbernilly,
Did you get a chance to look at the executable?

http://www.delphiforfun.org/Programs/traveling_salesman.htm

You can define your cities on a map (estimate not exact location) and then let the computer find the shortest path. You can tell it to use a Heuristic solution or an optimized solution (within time constraints). Will be interesting to see how your "closest point" algorithm compares to some of their methods. One more thing if you are doing a round trip often the best starting point is unintuitive. You may find better solutions if your first path is to a far away city. So try all 49 cities, as your first leg.

 

[PHV]

The TSP is a complete tour, i.e. the arrival is the origin, therefore the optimal path is independant of the origin.

 

[MajP]

PHV,
Yes in a classical sense the TSP is a complete tour. However, now a days the term TSP is often used to describe a family of problems and variations of it. Returning to the origin adds an additional constraint, but it has been proven that the complexity is not diminished without this constraint.
As was discussed above the algorithm will obviously not give an optimal solution (unless by luck). This is a "next closest node" algorithm. So in this case the initial conditions will have a drastic effect.

 

[BoxHead]

PHV, that's good to know. That eliminates even more of the permutations that would have to be tested.

We can already eliminate from testing all of the inverted routes: 1>2>3>4>5 is the same as 5>4>3>2>1 so that should knock out half of the permutations.

Without a specific origin, it means that
1>2>3>4>5 = 2>3>4>5>1 = 3>4>5>1>2 = 4>5>1>2>3 = 5>1>2>3>4
and their inverted values.

For real-world applications I think that trucks and cell-phone signals will actually be back-tracking along the stops and cells visited, but it's good news for the Traveling Salesman.

Thanks!



John

Use what you have,
Learn what you can,
Create what you need.

 

[rubbernilly]

In my case, it is a matter of not having to return to the start... it is a matter of speed. "How quickly can you visit each of these cities?" Returning to start (and in fact getting to the initial launch city) is not a constraint.

However, it seems that if you found the most efficient circle, you will have found the most efficient path, as well... at least after one more step. From the most efficient loop, simply remove the single longest leg. Your departure city is now one of the cities involved in that leg.

At least, it seems to to me.

I am playing with the executable now, MajP... trying to see what it will do. It seems that I have to add the cities (since they won't all show in each itinerary).

Anyway, I want to compare this to what Boxhead came up with, too.

 

[BoxHead]

Combinatorial mathmatics may work in your favor with the complete circuit element.

In a sample database using all permutations of 7 items (numbers 1 thru 7), the total number of combinations is 5040.

I ran a query to identify when circuits are repeated and was able to eliminate all but 720 combinations that would actually return unique results.

Granted that will only reduce your needs from 49! to 48!, but it's something. And of course, I have no idea as yet on how to identify only the 720 combinations that matter.

Any ideas?


John

Use what you have,
Learn what you can,
Create what you need.

 

[rubbernilly]

A question...

Combinations treat the same selection of numbers as one choice regardless of order.

123 is the same as 321 is the same as 231, etc.

So that does not seem like exactly the logic of what you're saying we can get rid of. With your example, 7 digits...

1234567

is the same as

23456712
34567123
45671234
56712345
67123456
71234567

but the other permutations are still valid options.

Are these the options you are talking about taking out of the mix?

 

[BoxHead]

I'm not saying that all combinations are the same. I'm saying that when we generate all of the permutations for a given quantity (49!), about 98% of our results are redundant because they represent the same sequence with a different starting point.

I'm not a mathematician or even a programmer (which is why I love hanging out here) so it's difficult for me to explain and there are plenty of people who have known for years the things I've learned in the last few hours.

However, I do golf so let's think of it in terms of a shotgun start in a golf match. 18 foursomes tee off at the same time on eighteen different holes. They all play the same holes in the same relative order. If we make the group that started on the 1st tee walk from the 18th green back to the 1st tee (round-trip), we don't have to ask each group how far they walked because they're all equal.

The mathematical premise of looking at all permutations of your 49 locations is the same as asking all 18 foursomes how far they walked.

What I've come to realize since my last post is that if we select any one starting location and look at all of the permutations moving forward from that starting position, we've effectively analyzed all possible routes.

How I got there...

I took my 5040 permutations of 1 2 3 4 5 6 7 in the results of the query I described at the beginning of this thread. I built another query where I concatenated the fields into a string twice.

That gave me values like
12345671234567
32654173265417
41732654173265

Built another query, using Mid(myVal,InStr(myVal,1),7) to identify matching routes. The 2nd and 3rd values above represent the same route: 1732654. That's how I knew that the 5040 permutations would only yield 720 unique routes.

After posting, I looked more closely at the results and saw that all of the permutations beginning with 1 gave me the same 720 unique values as all of the permutations beginning with 2 as with 3 and 4 and so on. That's when your post clicked that we're traveling in a full circle so it doesn't matter where we start.









John

Use what you have,
Learn what you can,
Create what you need.

 

[MajP]

I built the "closest Node" algorithm. You set a start city and you find the closest next city and keep going. This algorithm is very dependant on the initial path. Here is the code. Also my distances are based on a polar coordinate solution. The first sub accounts for the first and last leg.

Public Sub runRoute(theStartCity As String, theFirstStop As String, intRun As Integer)
  'This sub only adds the first and last legs.
  Dim rsOutputRoutes As DAO.Recordset
  Dim dblFirstDistance As Double
  Dim dblLastDistance As Double
  Dim strLastCityVisited As String
  Dim dblTotalDistance As Double

  Set rsOutputRoutes = CurrentDb.OpenRecordset("tblOutputRoutes", dbOpenDynaset)
  With rsOutputRoutes
    .AddNew
    .Fields("strStartCity") = theStartCity
    .Fields("strEndCity") = theFirstStop
    dblFirstDistance = DLookup("dblDistance", "tblCityDistance", "strStartCity = '" & theStartCity & "' and strEndCity = '" & theFirstStop & "'")
    .Fields("dblDistance") = dblFirstDistance
    .Fields("dblTotalDistance") = dblFirstDistance
    .Fields("strRun") = "Start " & intRun
    .Update
   End With
   Call subGetRoute(theFirstStop, "'" & theStartCity & "', '" & theFirstStop & "', ", rsOutputRoutes, dblFirstDistance)
  With rsOutputRoutes
    rsOutputRoutes.MoveLast
    strLastCityVisited = .Fields("strEndCity")
    dblTotalDistance = .Fields("dblTotalDistance")
    .AddNew
    .Fields("strStartCity") = strLastCityVisited
    .Fields("strEndCity") = theStartCity
    dblLastDistance = DLookup("dblDistance", "tblCityDistance", "strStartCity = '" & strLastCityVisited & "' and strEndCity = '" & theStartCity & "'")
    .Fields("dblDistance") = dblLastDistance
    .Fields("dblTotalDistance") = dblLastDistance + dblTotalDistance
    .Fields("strRun") = "End " & intRun
    .Update
  End With
End Sub

This is the real algorithm which is a recursive call. I have to admit it is pretty eloquent

Public Sub subGetRoute(ByVal strStartCity As String, ByVal strChoosenCities As String, rsOutPut As DAO.Recordset, ByVal dblTotalDistance)
  Dim rsPossibleCities As DAO.Recordset
  Dim strSql As String
  Dim strEndCity As String
  strSql = "select top 1 tblCityDistance.* from tblCityDistance where tblCityDistance.strStartCity = '" & strStartCity & "' and tblCityDistance.strEndCity not in (" & strChoosenCities & ") order by dblDistance"
  Set rsPossibleCities = CurrentDb.OpenRecordset(strSql, dbOpenDynaset)
  Do While Not rsPossibleCities.EOF
    strEndCity = rsPossibleCities.Fields("strEndCity")
    With rsOutPut
       .AddNew
       .Fields("strStartCity") = strStartCity
       .Fields("strEndCity") = strEndCity
       .Fields("dblDistance") = rsPossibleCities.Fields("dblDistance")
       dblTotalDistance = dblTotalDistance + rsPossibleCities.Fields("dblDistance")
       .Fields("dblTotalDistance") = dblTotalDistance
       .Update
    End With
    strChoosenCities = strChoosenCities & " '" & strEndCity & "',"
    Call subGetRoute(strEndCity, strChoosenCities, rsOutPut, dblTotalDistance)
    Exit Sub
  Loop
End Sub

I tested this with Richmond as my first node, and then tried every other city as the first path from Richmond. This takes about 1 minute. My best solution was to go south to Raliegh at 13,106 Miles.

strStartCity	strEndCity	dblTotalDistance
Richmond AP	Raleigh/Durham AP (S)	138.4
Raleigh/Durham AP (S)	Columbia AP	326.2
Columbia AP	Atlanta AP (S)	517.6
Atlanta AP (S)	Montgomery AP	660.3
Montgomery AP	Tallahassee AP (S)	842.2
Tallahassee AP (S)	Jackson AP	1205.12
Jackson AP	Baton Rouge AP	1344.1
Baton Rouge AP	Little Rock AP (S)	1641.4
Little Rock AP (S)	Jefferson City	1907.0
Jefferson City	Springfield AP	2067.3
Springfield AP	Indianapolis AP	2247.6
Indianapolis AP	Frankfort	2378.6
Frankfort	Columbus AP (S)	2545.2
Columbus AP (S)	Charleston AP	2677.2
Charleston AP	Washington, National A	2926.4
Washington, National AP	Annapolis	2951.8
Annapolis	Dover AFB	3012.5
Dover AFB	Trenton Co	3096.6
Trenton Co	Harrisburg AP	3202.3
Harrisburg AP	Albany AP (S)	3436.3
Albany AP (S)	Hartford, 	3528.27
Hartford, 	Providence AP	3591.2
Providence AP	Boston AP	3640.0
Boston AP	Concord AP	3702.2
Concord AP	Montpelier	3788.1
Montpelier	Augusta AP	3923.1
Augusta AP	Lansing AP	4671.6
Lansing AP	Madison AP (S)	4912.3
Madison AP (S)	Minneapolis/St. Paul AP	5140.5
Minneapolis/St. Paul AP	Des Moines AP	5373.2
Des Moines AP	Lincoln Co (S)	5541.3
Lincoln Co (S)	Topeka AP	5678.0
Topeka AP	Oklahoma City AP (S)	5954.0
Oklahoma City AP (S)	Austin AP	6306.8
Austin AP	Santa Fe CO	6916.3
Santa Fe CO	Denver AP	7209.5
Denver AP	Cheyenne	7306.4
Cheyenne	Pierre AP	7627.3
Pierre AP	Bismarck AP (S)	7794.2
Bismarck AP (S)	Helena AP	8327.7
Helena AP	Boise AP (S)	8621.5
Boise AP (S)	Salt Lake City AP (S)	8913.02
Salt Lake City AP (S)	Carson City	9340.88
Carson City	Sacramento AP	9444.3
Sacramento AP	Salem AP	9893.9
Salem AP	Olympia AP	10035.3
Olympia AP	Phoenix AP (S)	11132.3
Phoenix AP (S)	Nashville AP (S)	12579.8
Nashville AP (S)	Richmond AP	13106.1

Here is the distribution of other cities as the first path.

strStartCity	FirstCity	dblTotalDistance
Richmond AP	Raleigh/Durham 	13106
Richmond AP	Frankfort	13268
Richmond AP	Charleston AP	13407
Richmond AP	Nashville AP S)	13519
Richmond AP	Columbus AP (S)	13525
Richmond AP	Indianapolis AP	135681
Richmond AP	Salt Lake City 	13579
Richmond AP	Columbia AP	13708
Richmond AP	Madison AP (S)	13709
Richmond AP	Albany AP (S)	13882
Richmond AP	Washington, National 	13891
Richmond AP	Cheyenne	13924
Richmond AP	Atlanta AP (S)	13925
Richmond AP	Annapolis	13929
Richmond AP	Tallahassee AP (S)	13962
Richmond AP	Boston AP	13984
Richmond AP	Pierre AP	13990
Richmond AP	Dover AFB	13996
Richmond AP	Concord AP	14006
Richmond AP	Augusta AP	14018
Richmond AP	Trenton Co	14018
Richmond AP	Bismarck AP (S)	14022
Richmond AP	Harrisburg AP	14032
Richmond AP	Montgomery AP	14072
Richmond AP	Oklahoma City AP (S)	14102
Richmond AP	Jackson AP	14156
Richmond AP	Baton Rouge AP	14186
Richmond AP	Austin AP	14223
Richmond AP	Boise AP (S)	14259
Richmond AP	Springfield AP	14316
Richmond AP	Helena AP	14350
Richmond AP	Lansing AP	14355
Richmond AP	Minneapolis/St. Paul 14526
Richmond AP	Denver AP	14555
Richmond AP	Hartford	14567
Richmond AP	Providence AP	14611
Richmond AP	Little Rock AP 	14665
Richmond AP	Montpelier	14683
Richmond AP	Olympia AP	14700
Richmond AP	Salem AP	14764
Richmond AP	Jefferson City	14988
Richmond AP	Des Moines AP	15234
Richmond AP	Lincoln Co (S)	15299
Richmond AP	Topeka AP	15349
Richmond AP	Carson City	16004
Richmond AP	Sacramento AP	16015
Richmond AP	Santa Fe CO	16713
Richmond AP	Phoenix AP (S)	16778

In this algorithm initial path makes a big difference and may not be intuitive. The table shows that heading from Richmond to the first closest city, "Washington DC", give the 11th best answer. While heading to Salt Lake City gives the 5th.

Anyone get a better than 13,106 statute miles?

 

[rubbernilly]

I'll let you know after this weekend. The pilot friend of mine (whose request started this whole ball rolling) and I are going to examine the data and the processes people have suggested and see what we can come up with.



...

yeah, we're dorks.

;-)

 

[BoxHead]

Cool, MajP!

And fast.

I'm using rubbernilly's data which expresses the distances in minutes (I believe) so I'm not sure how to compare. It sounds like the .AddNew runs faster than my update query which surprises me but is good to know.




John

When Galileo questioned the accepted principles of the day, his fellow scholars called him a fool.
When he disproved those same principles,
they called him dangerous.

 

[MajP]

The "addNew" is not part of the algorithm, just makes nice output.

 

[rubbernilly]

Boxhead:

1 Minute = 1 Nautical mile
1 Nautical mile ~ 1.15 Statute Miles (1.15077945)

The data I posted in this thread is actually in degrees... so unless I'm mistaken the conversion will go:

(DistanceInDegrees) * 60 * 1.15

Or just

(DistanceInDegrees) * 69

I'll use that formula to convert results back for what we find this weekend.

 

[BoxHead]

Thanks rubbernilly. I had assumed it was something like that and had already updated with

(DistanceInDegrees) * 60

I'll update to * 69 and rerun my last sub, but the proportional change shouldn't change my results.

MajP, either way, I'm not matching the 'miles between' that you are showing and my results are pretty different.

The sub I posted 11/1, myTrip() was designed to look at the first 11 origin options with
For myRteNum = 0 To 10

and then on subsequent stops, instead of looking at the next nearest location, skip to the 2nd or 3rd choice.

I revised the sub to use
For myRteNum = 0 To myR1.RecordCount - 2
to look at each possible origin, and changed the code that deviated from the Next Closest paradigm from:

myR2.MoveFirst
If myTripNum <= myRteNum + 1 Then
myR2.Move (myRteNum)
End If
to

myR2.MoveFirst
If myTripNum = 1 Then
myR2.Move (myRteNum)
End If

so it would look at all 48 choices for the first stop.

It took 16 minutes, 7 seconds to run and gave me each city as an origin 48 times with every other city used as the first-stop.

When I look at the results, my trip originating in Richmond and starting with Raleigh as the first stop took 12408 miles.

My trip that started in Minneapolis and went to Bismarck first only took 11033 miles.

I don't know if this is a data difference or a process difference. Is there any chance you could run your procedure with rubbernilly's data (*69) to see if it changes your totals?

When I compare my Richmond>Raleigh trip to yours, mine deviates after Springfield because in rubbernilly's data, Madison is 4 miles closer to Sprinfield than Indianapolis is.

Thanks,




John

When Galileo questioned the accepted principles of the day, his fellow scholars called him a fool.
When he disproved those same principles,
they called him dangerous.

 

[MichaelRed]

At lot of activity for the subject. Particularly since it has been clearly stated, at least tacitly acknowledged and now clearly demonstrated that the approach is more or less guanrnteed to not actually solve the problem as orignially stated.

I have also constructed the actual distance routine and done a one-pass execution. With some difference:

I calculate the distance in sttute miles between all pairs of possib;e waypoints (city pairs). This calculation includes the adjustment for the Longitudinal miles per degreebased on the latitude (simplified somewhat to use hte longitudinal distance at he median (average) latitude of hte two waypoints.

I use several tables (the cities list - grabbed from this thread, including the Lat /Lon values) and an aded field "BeenThere" as a boolean to identify the already used waypoints. The macro repository of distances between the city pairs. This is the ~~ 2500 calculations refered to quite early on in the thread. I use this as the recordsource for a parameter query to return the nect stop" from any specific waypoint (City). Using the last stop, as the parameter, sorting the results by the mileage (ascending) and limiting the recordset to the cities where "BeenThere" is false, the first record is ALWAYS the next place to go on the tour.

Finally, I maintain the "Route" as a list of cities - in the order of the visitations (at least records are added in this order) so one last (aggregate) query returns the total tour distance.

Since NONE of the distance calculations appear to be common, it is clearly a waste of time to attemp to compare these results in any meaningful way, so I will not bother with that at all.

What I did find interesting, even at the briefest of galnces it that the furrther down the list of waypoins one goes, the less optimum the individual distances become. Although it did not seem to get to a ridiculous point untill it was nearly finished (the last to lege added almost 3,500 miles.

If anyone is interested in some specific part of the above (code / query stuff anyway) I would be glad to post it. Not much difference in the overall approaches to those already exhaustively listed, so I will not clutter the bandwith with a dump.




MichaelRed