Re: Algorithm to sort list [modified] - Algorithms Discussion Boards

Hi can someone explain to me what a regular language is? And what is pumping lema?

Google knows all that kind of stuff.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.

A regular language is the set of strings that can be generated by a regular expression, consisting of strings and the Kleene star (*), (which means zero or more occurrences of substrings). It's also the set of strings that can be generated by a finite-state machine, or recognized by a finite-state acceptor.

It's the simplest of four classes of languages. An example of a non-regular language is the set of strings with equal numbers of 0's and 1's. This can't be recognized by a finite-state acceptor (with n states) since a string with more than n letters would overflow the acceptor's finite capacity.

Hello,

Pulling my hair out trying to solve this problem. I have a list of data describing maximum allowable speeds along a section of track. I need to sort the data to form a speed 'profile' for that section of track. I'll describe by example:

The generated list may look like this upon retrieval from the database:

<snip>

LOMILE, HIMILE, SPEED
0, 30, 25
2, 10, 15
4, 6, 10
10, 20, 20

<end snip="">

What this describes is a section of track 30 miles long with a normal operating speed of 30 MPH (row 1). However, the operating speed is reduced to 15 MPH from mile 2 to mile 10 (row 2), that section is further reduced to 10 MPH from mile 4 to mile 6 (row 3). The operating speed is reduced to 20 MPH from mile 10 to mile 20 (row 4).

What I've been trying to do is come up with an algorithm that would sort that list into something that looks like this:

<snip>

LOMILE, HIMILE, SPEED
0, 2, 25
2, 4, 15
4, 6, 10
6, 10, 15
10, 20, 20
20, 30, 25

<end snip="">

I'm completely stumped trying to get to the solution. Please help! Smile | :)

It doesn't matter what code you implement in, pseudo code would be ideal, but, however you want to present the algorithm is fine with me.

If you are curious, I'm developing this in Access with VBA, however, in the future I'll probably move it to MySQL with PHP. Therefore, whatever code you want to use to illustrate the algorithm is fine.

Thanks in advance!

Lyle.

If I understand you correctly, the data means something like this:

|--------------------------| 25
   |------------| 15
      |----| 10
                |-------| 20

And the lowest value on a vertical line would be the maximum allowed speed at that point.
Then you want to somehow split the ranges and drop the parts that are not the minimum.
Cut:

|--|--|----|------|-------|---| 25
   |--|----|------| 15
      |----| 10
                  |-------| 20

Drop:

|--|                      |---| 25
   |--|    |------| 15
      |----| 10
                  |-------| 20

There is of course an efficient way to do this, but I'm having trouble defining it exactly.
What I can define exactly, is a far less elegant way..

int[] speed = new int[first.high - first.low];
for each section s
{
   for (int i = s.low; i < s.high; i++)
       speed[i] = min(speed[i], s.speed);
}

You can extract the result from this array in O(size-of-longest-section) time.
Being O(|sections| * size-of-longest-section), this algorithm sucks. But hey, it works.
I'm going to think about this some more, I hope I can accurately define splitting the sections.. Removing the not-minimum cuts after that, is nearly trivial.

Hi,

here is a KISS approach that might be suboptimal but it is simple:

0. get all the different relevant points (LOMILE and HIMILE) in a list
1. sort the list (probably combine 0 and 1 in "add-and-keep-sorted")
2. start at the first listed position
3. check all the rules, apply the lowest speed, and drive to the next listed point
4. iterate 3 until done.

The advantage is we don't need to find overlaps, intersections, ... in the set of rules. A precondition is the entire trajectory needs to be described in the rules, i.e. there should not be part of the route without speed limitation at all.

Smile | :)

PS: sorry Harold for not using your beautiful diagrams...

Luc Pattyn [Forum Guidelines] [My Articles]

Avoiding unwanted divs (as in "articles needing approval") with the help of this FireFox add-in

modified on Thursday, May 7, 2009 7:05 PM

Hi,

a more elaborate approach:

1. assume a "run" structure holding:
- a pointer to the next run (so we can make chains, i.e. linked lists);
- a LO coordinate;
- a HI coordinate;
- a speed limit.
2. the solution will be built as a linked list of such runs.
3. note that all the rules could be stored as a linked list of runs too.
4. start with one run, copied from the first rule, the one that describes the entire trajectory and the overall speed limit
5. take the next rule, and locate its LO in the current chain of runs: if its LO falls halfway inside a run, replace that run by two runs with the original speed (this probably means adapt the existing run, allocate a new run, give it correct values, and insert it in the linked list)
6. now locate the rule's HI in the chain: if its HI falls halfway some run, split it in two runs.
7. now the current rule exactly covers one or more runs in the current chain, for each of those runs if the rule's speed limit is less than the run's speed, reduce the run's speed.
8. repeat 5-6-7 for all rules
9. now the chain of runs describes the trajectory with the correct speed limits.

remark: if the rules are sorted by LOMILE step 6 can take advantage of that.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Avoiding unwanted divs (as in "articles needing approval") with the help of this FireFox add-in

Not certain how efficient this would be, but a tree structure may work for this as well. Bear with me, this might seem more complicated than it really is, trees aren't the easiest to explain in plain text Smile | :)

Assume your initial list is sorted the start of each speed segment as you have described, with the first entry covering the overall speed of the track:

TheConfusedGuy wrote:
LOMILE, HIMILE, SPEED
0, 30, 25
2, 10, 15
4, 6, 10
*7,9,5
10, 20, 20
*Added for example clarification

I'm thinking the tree structure would be like so:

        0,30,25
       /       \
   2,10,15   10,20,20
   /     \
4,6,10  7,9,5

Insert procedure as follows:
1. Root node = (0,30,25)
2. New = (2,10,15), compare = (0,30,25)
3. 2 b/w 0 and 30, compare = child of compare (null/no children)
4. compare = null, add New as child of compare.

5. New = (4,6,10), compare = (0,30,25)
6. 4 b/w 0 and 30, compare = child of compare (2,10,15)
7. 4 b/w 2 and 10, compare = child of compare (null, no children)
8. compare = null, add New as child of compare.

9. New = (7,9,5), compare = (0,30,25)
10. 7 b/w 0 and 30, compare = child of compare (2,10,15)
11. 7 b/w 2 and 10, compare = child of compare (4, 6, 10)
12. 7 past 6, compare = sibling of compare (null, no more siblings)
13. compare = null, add New as sibling of compare

... and so on.

I know the insert procedure seems complicated (trees tend to be that way), but I think it would be relatively efficient. To find the speed limit for a given track position, simply compare the position to the LOWMILE value of each node when you traverse your tree. Your lookup wouldn't be O(1), but no worse O(log m(n)) (I think), where m is the max number of subsections to a given stretch, and n is the total number of defined subsections. So in the example here, it would be O(log 2(3)) Your 2 worst cases would be:

|----|----|----|
|----|
     |----|
          |----|

or

|----|----|----|
|----|----|
     |----|

I hope this all makes sense. This is all totally off the top of me head, so I could be mistaken on how efficient this might be. I'm curious what ya'll's opinion is on this method Smile | :)

Dybs

modified on Friday, May 8, 2009 12:14 AM

Thanks all for the input. The ideas are pretty good, but, I need to take the scenario further I think to hammer down an algorithm, so bear with me Smile | :)

The real world application of this is to calculate train run time over a section of track. I'll use real world examples with explanation to clarify. Here we go:

1. The section of track is called a "subdivision".

2. The 'initial' speed profile for the subdivision is defined by what are called 'zone speeds'.

3. A subdivision can contain many zone speeds, but, the zone speeds do not overlap each other, instead, they run sequentially from one end to the other.

NOTE: to this point, the analysis is simple - it gets tricky with the 4th and 5th point.

4. When the condition of the rail deteriorates to a point where train operation at zone speed is not safe then mechanisms called "temporary slow orders" (TSO) are put in place to restrict the speed until repairs can be made. These mechanisms can be in place for months at a time.

5. These temporary slow orders can, and often do, overlap zone speeds, further, they can, but don't often, overlap each other.

Therefore, consider this scenario:

1. Subdivision length is 50 miles
2. Zone speed 1 exists from mile 0 to mile 28 at 40 MPH
3. Zone speed 2 exists from mile 28 to mile 31 at 20 MPH
4. Zone speed 3 exists from 31 to mile 50 at 25 MPH

NOTE: again, analysis of train speed is simple with this scenario, it gets complicated when the following is added to the scenario:

5. TSO A exists from mile 25 to 29 at 15 MPH
6. TSA B exists from mile 30 to mile 34 at 10 MPH

The data would be presented as it is above as I sort by Zone and TSO and by low mile for both when extracting from the database. So, the question becomes, how do I take that data, as presented above, and create the following list:

1. Mile 0 to 25 @ 40 MPH
2. Mile 25 to 29 @ 15 MPH
3. Mile 29 to 30 @ 20 MPH
4. Mile 30 to 34 @ 10 MPH
5. Mile 34 to 50 @ 25 MPH

??

In terms of the ideas presented above, I have considered using a tree sort, however, does the fact that the children nodes (TSO) can overlap the parent nodes (Zones) present a problem in execution? I had not thought of using a linked list, I think that mechanism might suit the problem, however, I want to think on that a bit more. I wonder if the overlap might cause a problem?

LOL! This problem is killing me. It's been 9 years since I completed my computer science program, and, there is a lot of rust accumulated over the years. The help given thus is greatly appreciated, any other thoughts and or help would also be appreciated.

Lyle.

TheConfusedGuy wrote:

1. Subdivision length is 50 miles (say default speed = 50 MPH
2. Zone speed 1 exists from mile 0 to mile 28 at 40 MPH
3. Zone speed 2 exists from mile 28 to mile 31 at 20 MPH
4. Zone speed 3 exists from 31 to mile 50 at 25 MPH
5. TSO A exists from mile 25 to 29 at 15 MPH
6. TSA B exists from mile 30 to mile 34 at 10 MPH

1. Mile 0 to 25 @ 40 MPH
2. Mile 25 to 29 @ 15 MPH
3. Mile 29 to 30 @ 20 MPH
4. Mile 30 to 34 @ 10 MPH
5. Mile 34 to 50 @ 25 MPH

Here's a question: what would the speed be for mile 25? 40 or 15? Or are you getting speeds for ranges only?

I hadn't thought about overlapping TSO's, such as 6 above. Such TSOs may need to have a parent node in the tree for each subsection they overlap, as below.

I think the insertion method I described above would still work, where the overlapping TSO would be a child of the subsection starting at 0. The list you described above would have a tree as follows:

          0,50,50
       /     |    \
0,28,40  28,31,20  31,50,25
  \      /    \     /
  25,29,15    30,34,10

Can't think of a good way to split up all the zones using the tree either, to get the speeds for a given range (say miles 26 to 33). Plus, having multiple parent nodes certainly complicates the insertion process, so a linked list like Luc's method is probably better.

Dybs

> > > Here's a question: what would the speed be for mile 25? 40 or 15?

The speed would be 15 at mile 25. Essentially, the 40 MPH limit ends at 24.99999999999999 and so on.

The rest of your post is why I sort of gave up the idea of a tree. If the TSO did not overlap the zones then the tree approach is very elegent, but, with the overlap it becomes quite complicated.

I'm thinking linked list as well, however, need to think on it some more. The first response to my original is an interesting approach as well. I need to look at that solution more closely.

Lyle.

do we have any formula for calculating bearing if we are given initial coordinates and great circle distance

thanks

I'm assuming you're talking about coordinates on a sphere and navigation-type problems - something I know a little bit about.

Unfortunately there are an infinite number of great circles from any position, and therefore an infinite number of points which are at a given distance. It's possible to calculate a bearing between two positions (coordinates) or the distance between them, but not to get a bearing from only one position and a distance.

There are three kinds of people in the world - those who can count and those who can't...

The exact problem is something like this:
I am drawing a bounding box around the circle.For calculating the right most bottom longitude,instead of making it as simply center Longitude + radius i am also trying to include bearing in it.This bearing corresponds to maxima of longitude.

I am unable to figure out this bearing.?

Hmmm, that's an interesting problem.

I'm not even sure how to go about drawing the bounding box, or if such a thing really exists in a spherical coordinate system. A few quick sketches show up all sorts of problems in defining the shape - is it a square (with curved edges), or some distorted shape with non-parallel sides? What happens near the poles, or if a pole is inside your circle? I can even end up with a 3-sided "box" in some cases.

I'm afraid I'll have to think a bit more about this one, and get back to you later...

There are three kinds of people in the world - those who can count and those who can't...

I've been having a bit more of a think about this, and I'm not sure there is a valid concept of a bounding box for a circle on a sphere - or not a simple one anyway.

Working in Lat/Long coordinates, there are a number of problem areas. If you define the "sides" of the box as the meridians at centre+radius and centre-radius Long, and the top and bottom as the similarly defined parallels of Latitude, you can get a "box" of sorts provided the circle is reasonably small, and not near or at either of the poles.

If the circle contains a pole, then the sides actually cross inside the circle, and the top or bottom may also intersect it. If the circle is centred on the pole, then there is no way to define a box at all.

Also, if the circle is a great circle around a meridian, then the circle itself is the box (with only two sides and no vertices)!

Going for an alternative approach, the bounding box could be defined as the intersections of four great circles. Each is defined as the great circle tangent to a particular point on your circle's circumference, with those points spaced at 90 degrees around it. This should define a box independently of any Lat/Long coordinate system, and will only have one degenerate case of the test circle being a great circle. Although if the first point is chosen to be at the "top" of the circle, it will, I think, be similar to the Lat/Long aligned one.

I'm not sure how to calculate the coordinates of the vertices of this new "box", or why you would want them, but it has made me think a lot about spherical geometry, and I might even write a quicky visualiser to look at this in more detail.

What does the "box" represent? What about other bounding shapes - hexagons, octagons? What can we say about limits, areas, volumes? Lots of questions, which have nothing to do with navigation, but are very interesting...

Cheers, and thanks for exercising my brain Big Grin | :-D

There are three kinds of people in the world - those who can count and those who can't...

Isn't this just Haversine formula:
R = earth’s radius (mean radius = 6,371km)
Δlat = lat2− lat1
Δlong = long2− long1
a = sin²(Δlat/2) + cos(lat1).cos(lat2).sin²(Δlong/2)
c = 2.atan2(√a, √(1−a))
d = R.c

So obviously:
θ = atan2( sin(Δlong).cos(lat2), cos(lat1).sin(lat2) − sin(lat1).cos(lat2).cos(Δlong) )

No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.

This message is made of fully recyclable Zeros and Ones

Yes that true but i do not have lat2 and long2.I have to calculate these with some very valid assumption of angle.

Have a look at
"http://williams.best.vwh.net/avform.htm"

If I understand the problem correctly, you have a point on a sphere and a great circle distance, this defines a circle C. You are interested in the extremes of lat/long on that circle.

At the original point, take the normal N. This normal is also normal to the plane containing C.

If you project C onto the plane through the equator Pe you will in general get an ellipse. The minor axis of the ellipse will be the projection of N onto the plane Pe, and the major axis perpendicular to this. You should be able to do some 2D geometry to find the extremes of longitude in this plane.

Similarly, projecting C onto a plane through the poles gives another ellipse that you can use to find the extremities of latitude.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

On his blog, Roger Alsing describes a very interesting program. I wonder if it can be improved....?

Here you can find a file with Dan Bystrom’s improvements [to the EvoLisa program], plus an additional improvement (using uints instead of doubles when the fitness drops below 3/4 of uint.MaxValue). I added an additional feature which could be implemented. It allows an interlaced subset of the pixels to be tested for fitness. I also included an open-source C program I found on the Internet that generates fast random numbers, but that would not help improve the program much speed-wise due to other bottlenecks in the system, so I did not implement it. Right now the renderer seems to be the major bottleneck in the code. You may want to try using System.Windows.Shapes.Polygon instead of System.Graphics for the polygons, since then each polygon could be rerendered at will individually. Right now, rendering is the major bottleneck in the code after the updates are applied (Around 350 renders occur per second on my computer, whereas 3,500 mutates or 1,750 fitness evaluations can occur in the same time period [I tested that by commenting out code temporarily and counting to ten while the algorithm was running. The margin of error was around 10%, which is negligible in this case]). By the way, I think that using uints instead of doubles was the 60% improvement that Dan was talking about, although the improvement would be more along the lines of 3X if the Renderer was faster.

The question is, how can I implement this? (I am a high-school student who has recently begun programming, and I consider myself to be a novice-intermediate programmer). Could anyone optimize that code with all of this in mind? The key is to use System.Windows.Shapes.Polygon so only one polygon would usually need to be rendered per generation (maybe two or three, but certainly not all of them as is required now). Before you ask, NO, THIS IS NOT A HOMEWORK ASSIGNMENT!!!

' MAIN()
'
' Entry point. No more PPd. & Add. (^800 = 5)
'
'^:MAIN
MAIN:
'^PR^! Retract form in printer.
PRINT CMD("PR");
'^PL66^! Set line count to 66 for this form.
PRINT CMD("PL66");
'^PN^! Normal print mode on.
PRINT CMD("PN")
'^:GET.TERMS
GET.TERMS:
'^?"BOL ENTER TERMS (1 - 4): 1. PREPAID   2. COLLECT   3. 3RD PARTY   4. COD"1"1""%d"800
'A%=VAL(INPUTBOX$("BOL ENTER TERMS (1 - 4): 1. PREPAID   2. COLLECT   3. 3RD PARTY   4.COD",1,"1"))
A%=3
'^OC(^800 < 1)(^GT GET.TERMS)
'^OC(^800 > 4)(^GT GET.TERMS)
IF (A%<1) OR (A%>4) THEN GOTO GET.TERMS
'^H
'
'         Goto line 2
'^G2
PRINT CMD("G4");
'
'         DATE, ORIGIN, DESTINATION
'
PRINT CMD("C50");CMD("D");STRING$(4," "); K$ ; STRING$(6," "); STRJUST$(FLD(14,0),3,"L"," ")
'GOTO ENDING
'
'         Skip a line
'
PRINT
'PRINT
'
' Shippers acct Number
PRINT STRING$(20," "); L$
'
'
PRINT
PRINT
'
PRINT STRING$(2," "); CMD("YL");CMD("7");CMD("YB")
PRINT STRING$(2," "); CMD("YL");CMD("8");CMD("YB")
PRINT STRING$(2," "); CMD("YL");CMD("9");CMD("YB"); STRING$(32," "); CMD("PB"); "HAWB#: ";STRJUST$(FLD(10,0),18, "L", " ");CMD("Pb")
PRINT STRING$(2," "); " "
'
PRINT STRING$(2," "); " ";STRING$(20," "); M$
PRINT STRING$(2," ");STRIP$(FLD(40,0),"C", " ")
'
'
'Skip 4 lines
'
PRINT
PRINT
PRINT
PRINT
'
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("2"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("3"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("4"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("14"),"C"," ");CMD("YB")
'PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("5"),"C"," ");", ";STRIP$(CMD("6"),"C"," ");" ";STRIP$(CMD("7"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("5"),"C"," ");CMD("YB")
'PRINT
PRINT STRING$(2," ");CMD("YL");STRJUST$(FLD(10,2),18,"L"," ");CMD("YB"); STRING$(2," "); STRIP$(FLD(8,2),"C"," ")
'PRINT STRING$(2," ");
' PO (13chars) / BOL #
PRINT STRING$(2," ");STRJUST$(FLD(40,0),20,"L"," "); STRING$(1," "); STRJUST$(FLD(9,0), 16, "L"," ");
'PRINT STRING$(2," ");STRJUST$(FLD(9,0),13,"L"," "); STRING$(1," "); STRJUST$(FLD(2,0), 16, "L"," ")
'

Looks like old fashioned basic to me.

No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.

This message is made of fully recyclable Zeros and Ones

I have 3 or more persons and they each have 3 or more schedules, how do i get all unique combination against each other.

if you have 3 person and they all have 3 schedules each it should be 27 different combinations but how do i program this.

If possible example code in VB.net or C#.net

Example P = Person, S = Schedule:
P1 S1 P2 S1 P3 S1
P1 S2 P2 S1 P3 S1
P1 S3 P2 S1 P3 S1
P1 S1 P2 S2 P3 S1
P1 S1 P2 S3 P3 S1
P1 S1 P2 S1 P3 S2
P1 S1 P2 S1 P3 S3
P1 S2 P2 S2 P3 S1
P1 S2 P2 S3 P3 S1
ETC ETC

Hi,

no code, just an approach:

if you were to use a ternary number representation (i.e. digits 0, 1, and 2; and digit weights that are powers of 3), then each combination could be written as a number, and incrementing such number would yield the next combination, so you would get 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, ... 222

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Avoiding unwanted divs (as in "articles needing approval") with the help of this FireFox add-in