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?

 

[BoxHead]

rubbernilly,

The sql below is based on a tool I made awhile back. You may be able to replicate it's structure in VBA as a subquery, but I only know to add the table with my values to the sql as many times as I have items.

Basically, I just add the same table to the query multiple times without a join and set the criteria of each field to be <> to the fields before it. In this example, I used a table with numbers 1 through 20 in field [f1] and set the criteria to look at numbers up to 5 (like your example).

SELECT tblPx.f1, tblPx_1.f1, tblPx_2.f1, tblPx_3.f1, tblPx_4.f1
FROM tblPx, tblPx AS tblPx_1, tblPx AS tblPx_2, tblPx AS tblPx_3, tblPx AS tblPx_4
WHERE (((tblPx.f1)<6) AND ((tblPx_1.f1)<6 And (tblPx_1.f1)<>[tblPx].[f1]) AND ((tblPx_2.f1)<6 And (tblPx_2.f1)<>[tblPx_1].[f1] And (tblPx_2.f1)<>[tblPx].[f1]) AND ((tblPx_3.f1)<6 And (tblPx_3.f1)<>[tblPx_2].[f1] And (tblPx_3.f1)<>[tblPx_1].[f1] And (tblPx_3.f1)<>[tblPx].[f1]) AND ((tblPx_4.f1)<6 And (tblPx_4.f1)<>[tblPx_3].[f1] And (tblPx_4.f1)<>[tblPx_2].[f1] And (tblPx_4.f1)<>[tblPx_1].[f1] And (tblPx_4.f1)<>[tblPx].[f1]))
ORDER BY tblPx.f1;

If you paste this into the sql view of the query design grid it might make more sense.

HTH


John

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

 

[rubbernilly]

Thanks for the response, BoxHead...

I tried your idea, but Access called my query "too complex". I have 49 items in the recordset, so I would have to add the table 49 times, correct?

Basically, it is a record of the 48 continguous US state capitals plus Washington, D.C. I have the distances from any one capital to any other in a separate table. What I want to do is find the order of the capitals that will give me the shortest overall travel.

Can you think of a way to modify your suggestion for 49 tables? Or do you have another?

 

[BoxHead]

rubbernilly,

I figure your 49 items will generate 608,281,864,034,268,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible permutations.

It's been awhile since HS math, but to gett the number of permutations, I believe you use Factorials: 49*48*47*46*45*...*2*1

I can see how that's 'too complex'.

I think there may be another way to get at what you're after. Not sure about the data structure but in general, you should be able to create a recordset where you start at any capital and travel to the next nearest that has not been visited. Running this for the 49 'origins' should give you the total mileage for each starting point.

Could you explain the data structure in more detail?





John

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

 

[rubbernilly]

Sure... here are the tables and pertinent fields:

[b][u][blue]Table: Cities[/blue][/u][/b]

[b][u]Field   [/u][/b]     [b][u]Type      [/u][/b]
City         Text * 255
NorthDbl     Double
WestDbl      Double

[b][u][blue]Table: Distances[/blue][/u][/b]

[b][u]Field   [/u][/b]     [b][u]Type      [/u][/b]
City1        Text * 255
City2        Text * 255
Distance     Double

I generated the Distance field based on the Lat & Long ("North" and "West") of the entry in the cities table, using a right triangle equation.

Every city has 48 entries in the Distances table where it is listed as City1. That is, I did not both to Filter that list for Albany to Detroit if Detroit to Albany already existed. I think that might make our job easier, since it is always and only the first column we would have to test for our departure city, and ditto for the arrival city against the second column.

Is that enough info?

 

[BoxHead]

That's plenty. Does your Distances table have 2401 records?

I'm afraid the trick-or-treaters are going to be occupying my time for a bit so I won't be getting back to this for a few hours.

John

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

 

[rubbernilly]

2352, to be exact. I don't have measurements for each Detroit to Detroit.

That's OK about the T-or-T'ers. We're having them here, too. I'm trying a couple of things in the meantime, but whenever you get a minute to come back to this, let me know what you think.

 

[raskew]

The following solution was provided some years ago by Marshall Barton at

http://groups.google.com/groups?hl=...&selm=3845addf_5%40news5.newsfeeds.com&rnum=1

Public Sub Permute2(Partial As String, _
                    Alpha As String, _
                    MaxLen As Integer)
'*******************************************
'Purpose:
'Inputs: From debug (immediate) window:
'        call permute2("", "12345", 5)
'Output: See debug window
'*******************************************

Dim i      As Integer
Dim result As String
    
    For i = 1 To Len(Alpha)
        result = Partial & Mid(Alpha, i, 1)
        If Len(result) < MaxLen Then
            Permute2 result, Left(Alpha, i - 1) & Mid(Alpha, i + 1), MaxLen
        Else
            Debug.Print result
        End If
        
    Next i

End Sub

Using this as the basis, you can do great and wonderful things, e.g. populating tables, etc.

HTH - Bob

 

[MichaelRed]

Given the table "Cities" with data, a somewhat simpler soloution if less comprehensive sloution wold be to compute the distance to each City in the list, saving the (single) name of the nearest city for each calculation in a loop of the Cities table, excluding the the one with a distance of Zero (the same named/lat/lon). This is the ~~ 2500 calculations.


The right triangle method is, of course, not accurate for spherical geometry, but would be close enough to get a good approximation of a reasonable route. This does not, of course, guarntee that the route is the shortest, only that you know the distance from any given City to its nearest neighbor. There have been numerous algorythims to compute the actual shortest routes including multiple way points amd other criteria.




MichaelRed

 

[raskew]

Michael -

The original question was:

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

Did that somehow fall by the wayside?

Bob

 

[MichaelRed]

I believe that the most direct answer was that the simple calculation of the permutations far exceeded the patience of the community. On the order of 6. E+62. Given the blinding speed of the potential approaches, I am certainly not waiting up for the final answer.



MichaelRed

 

[MajP]

Rubernilly,
Good luck. If I understand correctly it sounds to me like you are trying to solve a classical problem in combinatorial mathematics known as the "Traveling Salesmen Problem". Just so you know what your getting in to.

Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and returning to your starting point. The simplicity of the statement of the problem is deceptive -- the TSP is one of the most intensely studied problems in computational mathematics and yet no effective solution method is known for the general case. Indeed, the resolution of the TSP would settle the P versus NP problem and fetch a $1,000,000 prize from the Clay Mathematics Institute.
Although the complexity of the TSP is still unknown, for over 50 years its study has led the way to improved solution methods in many areas of mathematical optimization.

There is a lot of code for non optimal solutions to this problem. Google "Traveling Saleman Problem". However, if you do come up with the optimal solution through access share part of the $1million with me.

 

[rubbernilly]

Thanks for the responses, all.

Michael - I know that the sort of triangulation I am attempting is not the most accurate representation of distances, but as you say, it is close enough.

Raskew - I took what you provided and modified it so that it would work with the data I already had. I have the code running on my other computer. I'll probably leave it running all night just to see how far it gets.

MajP - Thanks for the heads up as to what I'm getting into. It seems a lot more serious than I had thought. And don't worry, if a solution presents itself through access, I'll be sure to share the 1,000,000 with whomever has helped. (Easy promise to make when there is next to no hope of solving this by other than brute-force).

I'll see how my code is doing in the morning.

 

[BoxHead]

rubbernilly,

This is what I've got:

Created a table tblTrips with four fields:
myOrigin text, the origin city
myStopNum numeric, the leg of the trip 1 thru 48
myStopName text, the city visited
myDistance numeric, the miles from the previous city to this stop

The idea is to open a recordset of the distinct city names, declare the first one is the myOrigin, find the closest city as myStopName for the first myStopNum and record the miles to get there as myDistance. Append that to the tblTrips and then, based on the city visited find the closest city that hasn't been visited and append that record to the table.

The table ends up looking like:

myOrigin	myStopNum	myStopName	myDistance
Albany	       1	           Boise	1097
Albany	       2	           Salem	996
Albany	       3	           Dover	1010
Albany	       4	           Helena	1101
Albany	       5	           Denver	1201
Albany	       6	           Topeka	1224
Albany	       7	           Pierre	1227
Albany	       8	           Austin	1243
...
Albany	       45	           Indianapolis	2386
Albany	       46	           Oklahoma City	2496
Albany	       47	           Salt Lake City	2511
Albany	       48	           Jefferson City	2629
Annapolis	       1	           Boise	1431
Annapolis	       2	           Salem	996
Annapolis	       3	           Dover	1010

I didn't have any real data on the distances so I summed the ASCI codes of the characters in the city names in an update query to do it fast and still make sure that the distance from Annapolis to Boise was the same as Boise to Annapolis.

I'd like to know what this looks like with real data. Once tblTrips is populated, a totals query grouping by myOrigin and summing myDistance should identify the shortest trip.

Here's the code.

Private Sub myTrip()
Dim myOrigin As String, myRecent As String, myAll As String
Dim myTripNum As Integer
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

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
DoCmd.RunSQL "INSERT INTO tblTrips (myOrigin, myStopNum, myStopName,myDistance)" _
            & " SELECT '" & 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

DoCmd.SetWarnings True

End Sub

Now, rubbernilly, if this all works out, I'm not going to ask for a full half of the million dollars. If you'd give me a dollar for the first city in the list, $2 for the second city, $4 for the next, $8, $16 and so on, I'd be satisfied with that.


49 cities would only come to $281,474,976,710,656.00


Let me know what you think.


John

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

 

[DanJR]

...And don't worry, if a solution presents itself through access, I'll be sure to share the 1,000,000 with whomever has helped. (Easy promise to make when there is next to no hope of solving this by other than brute-force).

My understanding is that Microsoft has some of the top computer scientists working on non-deterministic polynomial problems. So if you do find a solution that runs in polynomial time complexity then i'm sure microsoft will give you more than $1M

 

[MajP]

Take a look at the executable. It a fun diversion.

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

Another thing to help put this in perspective, the optimal solution to the 49 City problem was solved in 1954 by three researches to include George Danzig. Just so you know whose league you will be in once you solve this, here is a famouse story about Danzig as a student.

It happened because during my first year at Berkeley I arrived late one day at one of [Jerzy] Neyman's classes. On the blackboard there were two problems that I assumed had been assigned for homework. I copied them down. A few days later I apologized to Neyman for taking so long to do the homework — the problems seemed to be a little harder than usual. I asked him if he still wanted it. He told me to throw it on his desk. I did so reluctantly because his desk was covered with such a heap of papers that I feared my homework would be lost there forever. About six weeks later, one Sunday morning about eight o'clock, [my wife] Anne and I were awakened by someone banging on our front door. It was Neyman. He rushed in with papers in hand, all excited: "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." For a minute I had no idea what he was talking about. To make a long story short, the problems on the blackboard that I had solved thinking they were homework were in fact two famous unsolved problems in statistics. That was the first inkling I had that there was anything special about them.

So I guess the point is I should have never mentioned that this was a hard problem, and you would have got it done already.

 

[rubbernilly]

OK, so status as of this morning...

With the code running all night (albeit on a 1.0 GHz laptop), the code had managed to iterate through 9 positions of the string.

Let me explain. To make raskew's code work, I added a new field to the Cities table, called "Code." I added a single, unique character to each field and then fed the string of those characters to the permute2() function. The string length was 49 characters, obviously. And for each iteration/permutation, I had to do 48 distance lookups against the Distance table. Well... not exactly. If the total distance traveled after any one of those 48 lookups exceeded the previous Minimum, then I exited the calculation and went on to the next permutation.

So, with that code running, the permutation managed to work up to where it was in the middle of the 9th character position.

That would work, but I can't leave one of my computers tied up for a week straight to work through the rest of the potentials.

Boxhead - I am intrigued by your solution. Couple of questions...

1) How is the shortest next leg of the trip different if Albany is my 15th stop as opposed to the 10th stop? Isn't the closest other capital still the closest?

2)Would the aggregate query you describe get the shortest OVERALL trip? I'm trying to wrap my mind around this. Is it possible that on any one individual leg you would be better off not choosing the shortest path because it allowed for shorter paths thereafter?

I'll see if I can get the data that I have and publish it here for anyone that wants to try.

 

[rubbernilly]

Here is the information:

[u][b][blue]Table: Cities[/blue][/b][/u]
Code  City                      North  West     NorthDbl  WestDbl
!     Providence AP             41°44' 71°26'   41.73     71.43
#     Richmond AP               37°30' 77°20'   37.50     77.33
$     Sacramento AP             38°31' 121°30'  38.52     121.50
%     Salem AP                  44°55' 123°1'   44.92     123.02
&     Santa Fe CO               35°37' 106°5'   35.62     106.08
(     Tallahassee AP (S)        30°23' 84°22'   30.38     84.37
)     Pierre AP                 44°23' 100°17'  44.38     100.28
*     Springfield AP            39°50' 89°40'   39.83     89.67
@     Raleigh/Durham AP (S)     35°52' 78°47'   35.87     78.78
[     Topeka AP                 39°4'  95°38'   39.07     95.63
\     Washington, National AP   38°51' 77°2'    38.85     77.03
]     Trenton Co                40°13' 74°46'   40.22     74.77
^     Salt Lake City AP (S)     40°46' 111°58'  40.77     111.97
0     Lincoln Co (S)            40°51' 96°45'   40.85     96.75
1     Little Rock AP (S)        34°44' 92°14'   34.73     92.23
2     Madison AP (S)            43°8'  89°20'   43.13     89.33
3     Minneapolis/St. Paul AP   44°53' 93°13'   44.88     93.22
4     Montgomery AP             32°23' 86°22'   32.38     86.37
5     Montpelier                44°12' 72°31'   44.20     72.52
6     Nashville AP (S)          36°7'  86°41'   36.12     86.68
7     Oklahoma City AP (S)      35°24' 97°36'   35.40     97.60
8     Olympia AP                46°58' 122°54'  46.97     122.90
9     Phoenix AP (S)            33°26' 112°1'   33.43     112.02
a     Albany AP (S)             42°45' 73°48'   42.75     73.80
b     Annapolis                 38°56' 76°34'   38.93     76.57
c     Atlanta AP (S)            33°39' 84°26'   33.65     84.43
d     Augusta AP                44°19' 69°48'   44.32     69.80
e     Austin AP                 30°18' 97°42'   30.30     97.70
f     Baton Rouge AP            30°32' 91°9'    30.53     91.15
g     Bismarck AP (S)           46°46' 100°45'  46.77     100.75
h     Boise AP (S)              43°34' 116°13'  43.57     116.22
I     Carson City               39°10' 119°46'  39.17     119.77
j     Boston AP                 42°22' 71°2'    42.37     71.03
k     Charleston AP             38°22' 81°36'   38.37     81.60
l     Cheyenne                  41°9'  104°49'  41.15     104.82
m     Columbia AP               33°57' 81°7'    33.95     81.12
n     Columbus AP (S)           40°0'  82°53'   40.00     82.88
o     Concord AP                43°12' 71°30'   43.20     71.50
p     Denver AP                 39°45' 104°52'  39.75     104.87
q     Des Moines AP             41°32' 93°39'   41.53     93.65
r     Dover AFB                 39°8'  75°28'   39.13     75.47
s     Frankfort                 38°10' 84°54'   38.17     84.90
t     Harrisburg AP             40°12' 76°46'   40.20     76.77
u     Hartford, Brainard Field  41°44' 72°39'   41.73     72.65
v     Helena AP                 46°36' 112°0'   46.60     112.00
w     Indianapolis AP           39°44' 86°17'   39.73     86.28
x     Jackson AP                32°19' 90°5'    32.32     90.08
y     Jefferson City            38°34' 92°11'   38.57     92.18
z     Lansing AP                42°47' 84°36'   42.78     84.60

Now, rather than me formatting ~2400 records of distances, here is the code that I used to populate the Distances table:

Public Sub GenerateDistances()
Dim rs1 As DAO.Recordset, rs2 As DAO.Recordset
Dim rsDist As DAO.Recordset

Set rs1 = CurrentDb.OpenRecordset("Cities", dbOpenSnapshot)
Set rs2 = CurrentDb.OpenRecordset("Cities", dbOpenSnapshot)
Set rsDist = CurrentDb.OpenRecordset("Distances")

While Not rs1.EOF
    While Not rs2.EOF
        If rs1!City <> rs2!City Then
            rsDist.AddNew
                rsDist!city1 = rs1!City
                rsDist!City2 = rs2!City
                rsDist!Distance = Sqr(((rs1!northdbl - rs2!northdbl) * (rs1!northdbl - rs2!northdbl)) + ((rs1!westdbl - rs2!westdbl) * (rs1!westdbl - rs2!westdbl)))
            rsDist.Update
        End If
        rs2.MoveNext
    Wend
    rs1.MoveNext
    rs2.MoveFirst
Wend

Set rs1 = Nothing
Set rs2 = Nothing
Set rsDist = Nothing

End Sub

 

[BoxHead]

rubbernilly,

You asked:
1) How is the shortest next leg of the trip different if Albany is my 15th stop as opposed to the 10th stop? Isn't the closest other capital still the closest?

The query finds the shortest next leg of the trip that hasn't been visited so depending upon where you start, each stop may have a different next stop.

2)Would the aggregate query you describe get the shortest OVERALL trip? I'm trying to wrap my mind around this. Is it possible that on any one individual leg you would be better off not choosing the shortest path because it allowed for shorter paths thereafter?

I think that's very possible. I began (and continued) with the premise that you would always go to the next closest destination. Obviously, from the discussion of the TSP, there's a large effort to simplify the permutation complexity. I wonder what that sort of work pays??

Since it's the nature of permutations to grow exponentially, I have to think that the only way to actually accomplish this is to devolop a provable, logical system for pre-determining a "Best Route" that eliminates most of the permutations from consideration. Possible examples could be:

Rule 1: You always go to the next nearest destination (NND).
Rule 2: You always go to the destination nearest to the origin location.
Rule 3: You compare the distance of each location's top n NNDs and take the shortest combined route.
Rule 4: You research each location on the internet and just say you went there.






John

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

 

[rubbernilly]

Rule 4: You research each location on the internet and just say you went there.

That's an idea!

Seriously, I gave some thought to always choosing the shortest path, and I don't think it will always produce the most efficient path for 'x' items. Take, for example, the cartesian coordinates:

A (0,0)
B (2,0)
C (2,1)
D (2,-2)

Starting at A, the shortest path is to B. From B, the shortest path to an unvisited point is to C. From C, the shortest path to an unvisited point is to D. But that path is not the most efficient. The most efficient is ACBD.

How does your methodology handle this?

MajP - I understand your story about just attacking the problem as if it is something that needs to be done to see what shakes out of it. I have a similar story about myself.

In middle school Geometry class, we learned how to bisect and trisect a line. We learned how to bisect an angle, but were informed by the instructor that there was no way to trisect an angle, and that the person who could come up with a way to do that would become rich/famous. Now, looking back, it seems that the answer is so straightforward that the instructor must have been mistaken in his declaration that there was no way to trisect an angle. But I digress...

I went home and worked on the problem and realized that the same way you bisect an angle (join the intersection points of a circle on the two sides of the angle, in effect, forming a chord; bisect the chord, and connect the bisection point with the vertex of the angle) is the way you would trisect an angle (simply trisect the line rather than bisect).

I took the basic write-up of the proof to the instructor to show him what I had done. He declared that my solution was not accurate because the three triangles formed by trisecting the angle should be identical.

That is, of course, false. But he couldn't see beyond his own preconception that the problem could not be solved by a middle-schooler.

Here's the rub...

Later that year or the next, I had the same instructor for a different class. Midway through the semester, he passes out a photo-copied proof (more involved and detailed than my basic write-up had been), that he said had been developed by another student. The proof? How to trisect an angle. The method? Trisect the chord line. IOW, my exact solution.

The instructor was very excited for the student and was passing out these photocopies to every one of his classes. I didn't know what to say. But I tell you if I saw that instructor now, I'd know what to say.

In any case, good advice on trying to attack the problem with a fresh outlook.