Coding Challenge #35.2: Lexicographic Order
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- In Part 1 of this multi-part coding challenge, I introduce the classic computer science problem of the Traveling Salesperson (TSP) and discuss the pitfalls with a brute force solution. In Part 2, I discuss Lexicographic Ordering and demonstrate one algorithm to iterate over all the permutations of an array. In Part 3, I apply this algorithm to a brute-force solution of the TSP problem. Every single route permutation is checked one by one. In Part 4, I attempt to create a solution to the TSP problem with a genetic algorithm, and then I add a “crossover” algorithm in Part 5. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): • Coding Challenge #35.1...
📺 Part 3: TSP with Lexicographic Order: • Coding Challenge #35.3...
📺 Part 4: TSP with Genetic Algorithm: • Coding Challenge #35.4...
📺 Part 5: TSP with Genetic Algorithm and Crossover: • Coding Challenge #35.5...
🎥 Previous video: • Coding Challenge #34: ...
🎥 Next video: • Coding Challenge #36: ...
🎥 All videos: • Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: www.quora.com/How-would-you-e...
📝 Array on MDN: developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: natureofcode.com/
Videos:
🎥 Improved Pool Selection: • 9.8: Genetic Algorithm...
🎥 Genetic Algorithm Playlist: • 9: Genetic Algorithms ...
🔴 Live Stream Archive #57: • Live Stream #57 - Trav...
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: • Coding Challenge #29: ...
🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorit...
🚂 #69 Evolutionary Steering Behaviors: • Coding Challenge #69: ...
🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: ...
Timestamps:
00:00 Introducing Part 2
00:33 What is Lexical Ordering?
02:55 An article on Lexicographic Ordering
04:00 Code! Implementing the algorithm
04:42 Step 1 of the algorithm: largest x
06:48 Step 2 of the algorithm: largest y
09:19 Step 3 of the algorithm: swap
10:28 Step 4 of the algorithm: reverse
11:03 The splice() array function
12:26 The reverse() array function
13:43 Oups! Fixing array concatenation
15:05 Debugging the code
18:30 Yay! The correct result!
18:39 Visualizing the algorithm
19:56 How many permutations are they?
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: th-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js
it feels like he's learning, understanding and teaching all at the same time.
true
I actually learn best from people who make mistakes. I believe they make the best teachers!
You're like the Bob Ross of programming, but instead of nice little trees or clouds, you have nice little functions or algorithms.
I see this comment on every one of his videos
he's still got nice little trees though!
parse-like trees :)
Nice little fractal trees
I hope he will be remembered like that. He is not only a great educator, but also an embodiment of wholesomeoness.
Thank you so much for the video. It helped me understand the lexicographic order and the algorithm for its permutations.
I like this weird man.
Dan ain't weird, He's a wizard.
Every geek is naturally weird.
This is exactly what i was looking for a few days. Thanks for explanation.
you are amazing , just started watching you videos a few days ago and now i am determined to complete all your tutorials . And you book (not sure you wrote it??) is amazing too. It's so simple and explains many basic concept in a clear way.
I am in computer engineering 1st year atm but the education system of my country we learn almost nothing in college(at least not learned anything useful in first year).
ha, is there a book about this?
I think it's good to have a look at the debugging portion. Allow's people to see the entire process.
This is the only video on TH-cam. Thanks for this.
i see myself while coding when i see u, thanks i'm not alone
Buenos Aires! I love saying that... and I understand it's a charming city, too.
I Like How You Explain Your Code :D
you are AWESOME! Thank you.
you're so fun to watch man
Been having fun learning to program in java by translating all this so far. But it'd help if javascript splice and java splice weren't completely different functions. I've spent half an hour just trying to figure out how to translate these 5 lines of code. Sticking with my lessons of fail faster and moving onwards.
You' ve mistaken in 7:40 and I was asking myself 'What I am doing wrong' xd
Daniell! when do you stream and where? btw your bids are great
I likes this mad progrmmer... 🤗🤗🤗
What the heck happened at 8:25?! He missed quite a few things, didn't he? Confused... ':o
It made me crazy when you first wrote the code for largest y wrong. ... i paused the video for 10 minutes figuring out why you did it like that because i thaught I !!! was wrong ... when i finally gave up and 5 minutes lateer you corrected yourself ... oh maaaan ... i should not doubt my self :D
cool video Daniel i am just a beginner in javascript and i just finished some lessons in code academy now im learning objects and i am doing great .Anyway i watch your videos everyday even if i dont understand a lot on them.how much time do you think it will take me as a beginner to learn to code these kind of programs?
Everest Ev10 10 months later... How's it going?
Gracias mister Coding.... si la proxima aplica metodo heuristico --> Simulated annealing
Just a couple of optimisations (which seems important when the number of permutations increases factorially with array length):
1. For finding the largest index k such that something(...) it's faster to search from the end of the array and break out of the loop once you've found a case where something(...) is true, i.e.
largestK = -1;
for (var k = vals.length -1; k >=0; k--) {
if(something(...)) {
largestK = k;
break;
}
}
This means that we don't need to waste time checking all indices less than largestK. Here, the loop runs for about half as many iterations before breaking, on average.
2. If I'm not mistaken, increasing the length of an array is typically a slow operation that requires copying all elements in the array to a new location in memory, so for the partial array reversal, it'd likely be more computationally efficient to just perform a sequence of swaps, i.e.
for (int k = 0; k < (end-start)/2; k++) {
swap(vals, start+k, end-k);
}
This way the array never changes length, and you already had the swap(...) function implemented anyway.
Thanks for this feedback!
Hi, Daniel, I love ur vids. I have a suggestion to make another challenge: simple physics engine, bubbles and rectangles are colliding etc.
Gravity changes according to position of mouse with respect to the center of the screen
This one was a bit hard to follow. It might have helped to describe the problem statement that the lexical ordering was meant to solve here (ie not just "traveling salesman"). Love your vids, btw ✌️
u could loop through the endArray and push each value
I love the bell.
Will there every be another print run of the coding rainbow shirts?
All this work is with the j.s software or a special library??
pleas help
If you only call the endArray bit after the sorting is done, this program runs 1000x faster.
Initiate done = false, endArray only runs if(done), and done is set to true when largestI loop is broken.
will it still give all perms if the beginning array is not sorted asc?
This assumes that the list is always in the right order, doesn't it? If you're supposed to be finding the LARGEST x for which it's true (or i), shouldn't you be checking if vals[i] > largestI as well?
Could we also get an (on-demand) index_to_lexico permutations version --
index_to_lexico(index,base,baselength)?
Example... 0=000, 1=001, 2=010, 3=100, 4=011, 5=101, 6=110, 7=111...
Therefore... index_to_lexico(8,9,3) = 002
what if i want to do this for finding nth Lexicographic permutation of array up to 100 elements eg. A[26]={A,B,C..,Z}
I am given index 'n' whose lexicographic permutation . As an example, the factoradic number 2110_! is equal to * * 2 x 3! + 1 x 2! + 1 x 1! + 0 x 0! * = 2 x 6 + 1 x 2 + 1 x 1 + 0 x 1 * = 12 + 2 + 1 + 0 * = 15
So if n = 3 {A,BC} or n =4 and {A,B,C,D} .....trying to solve this problem in c++. thanks for the help!
You can't imagine how hard it was to do this in lua. You don't have functions like splice, reverse, concat...
Dont know about lua.. but you know.. you can always write such simple functions yourself.
@@panunurmilaukas5519 You are right, but I didn't know exactly what they do. I've managed to write them eventually.
I'm actually in the process of doing this in lua. I love LUA! love love love lua. I just either use a library for some of these types of functions, or write my own and save them as my own library. I use lume for a lot of simple variable. github.com/rxi/lume (I realize this comment is a year old. Just saw "lua" and I had to jump in!)
no reason to use lua anymore considering that almost no industry employs it now. stick to java to learn the fundamentals.
@@John-mj1kk You clearly haven't educated yourself on the applications of lua. One literally can't escape the influence of lua nowadays. For example, many animations and 2d simulations are made in LÖVE engine, which explicitly uses lua, native modding tool for Scrap Mechanics and many other games is implemented in lua, even the two biggest companies in the gaming industry, namely Epic Games (Core) and Roblox, let you develop your own games in lua and it worked flawlessly for years. Needless to say, Java will never be considered a "basic", though it has a low-level syntax, the behind-the-scenes is much different. Java forces you to run a virtual machine every time you execute a piece of code and has its own environment that it has to convert into the machine language. Very not "basic", if ask me.
TL;DR: *LUA IS THE BEST*
It will take *16.8* hours to finish that computation.
I know I'm late to the party @ 9:55, but as reference, you can reverse the values in-place without added complexity:
var next = largest + 1;
var middle = (vals.length + next) >> 1;
var last = vals.length - 1;
for(var current = next; current < middle; ++current, --last){
swap(vals, current, last);
}
Thanks for this tip!!!
Anytime boss! Glad I could help :)
Kindly checkout my implementation of the lexicographical permutation algorithm (with round-trip reordering): github.com/karagulamos/Euler/blob/master/Euler.Algorithms/Permutations/Permuters/LexicographicalPermuter.cs
Let me know your thoughts. Thanks.
Or that loop can be while (next < last) {swap(vals, next, last); next++; last-;}, which looks a bit simpler and avoids potential off-by-one errors with the middle.
Or even for (i = 0; 2i < last - next; i++) {swap(vals, next + i, last - i);}
Coding Chalange: Conway's Game Of Life BUT with an infinite grid!
It's solvable.
Except the problem of ya know, infinite monitor which shows entire grid...
isn't there a js function that reverses arrays?
Letters are numbers. Always have been always will be, [just instead of them representing amount of something they are representing an index in our alphabet kind of. It's a little bit more complicated but yeah.]
I don't know what have changed in the past 2 years, but for some reason, a[j] = temp now makes a[j] an object rather than the value of temp, meaning the swap function no longer works.
Maybe you changed some of the code? Because it still works for me.
13:08 vals.push(...endArray) will work!
I'm sure that falls into the "JavaScript magic" territory that he's avoiding. Array.push.apply would probably be best, but short of that he just just use a while loop and pop off the end array to push into the original array. That also reverses the order so he wouldn't need the reverse () call which is a little magic-y itself.
That wasnt a thing during the recording of this
@@Fun-Planet Was it though? ES6 has been around since 2015. Or is the spread operator ES7 or something?
EDIT: The spread operator is ES6. So it was a thing when this was recorded
@@SimonTiger oh ok my bad, he actually started using es6 when es8 came out
I know this is a late comment, by does anyone know why the first log of vals is missing 8 in his p5 code? (not in video, but in the p5 web editor)
Ran into the same issue and haven't figured it out. :(
Use this instead of console log line
console.log(JSON.parse(JSON.stringify(vals)))
This is due to the fact that console logs don't happen when they are supposed to. By the time it happens, the value of the array had changed, so it doesn't get displayed. By using parse and stringify, we are telling it to not log the vals array, but a copy of it
Ps u can use vals.slice() as well
@@Fun-Planet Thank you. I'll have to try that.
6:30 in, shouldn't you be looping from the end and breaking at the first occurrence of largestI? Starting at the beginning is silly.
Hopefully I can get a reply relatively quickly....
Would this algorithm work on a two number "alphabet" that is literally just 0 is first, 1 is second? Something about the P[x] < p[x+1] seems a little bit fishy bc its literally just 0 and 1, but intuitively I think it should still work.
I don't have too much time to really go down the wrong-algorithm-rabbit-hole, so I'd appreciate a confirmation from someone if they get the chance.
Yes it would, x would be 0 and y would be 1. So after swapping, the array would be [1,0] and that is the last permutation.
Isn't this just sorting in reverse order? Lexiographical sorting makes more sense to me when the objects have more than one dimension. For instance: sorting [bee, bay, bear] -> [bay,bear,bee] where you first look at the first letter and then advance to the second dimension within the object (second letter in this case) and sorting there.
funny guy...but nice explaination
PS: keeps awake while watching :P
20:18 16 hours, 48 minutes
11 numbers should mean it takes 11x as long
Awesome
To display all permutations of 10 digits at 60fps, it would take a little more than a month.
Not really, assuming one permutation per frame you get 10! / 60 (fps) / 60 (sec) / 60 min =~ 16h 48min
Do quad-trees speed this u?
You have a 15 inch retina macbook pro don't you?
I get drunk and watch Daniel coding
which programming language you used to solve this problem
sir?
js
I got so furious at Step 2 thinking is he really doing it wrong or I have gone crazy.. I actually paused the video and coded the whole thing myself just to prove myself that I'm not understanding it wrong.
LOL
He is confusing the heck out of me. He defines a function swap that has three parameters then calls it with only 2. Then says the highest value less then 7 is 3 when 6 is also in the array. By the time he got 3/4 of the way done I could not remember how to spell my own last name!!!
He meant highest index in the array
for i in range(0, len(a) -1):
if (a[i] < a[i+1]):
largestI = i
doesn't this also satisfy for 3 and 4 since 3 is less than i +1 .
largestI should be 6 and a(largestI)=3
can someone please enlighten me
Sarbjit Gahra No, he wants the last number that is less than the one after it, which here is 6 (6 < 8, while 8 > 4 > 3, so 6 is the last one).
I read redraw (re draw)
As red raw
😂
not funny enough.
This guy is elite!
Batman!
No, really, Batman:
en.wikipedia.org/wiki/Batman,_Turkey
We were taught this in 11th grade in computer science, i hate it.
Is it better to use recursion for this? like the implementation in StackOverflow (First answer):
stackoverflow.com/questions/9960908/permutations-in-javascript
raniel garcia Permutations via recursion are fantastic for something called backtracking: basically, if it’s possible to test the partial permutations for validity, then you can do that with each partial order you generate, and if it’s invalid, you can avoid generating all the full permutations that come from it, since you know they will be invalid. You can use this to solve sudokus, N-queens problems, etc ridiculously fast.
Your video code is not doing the same thing as what was recorded on the video. If you open in the web editor Web p5.js. It is producing:
[0, 2]
[1]
[1, 2]
[2]
[2, 1]
Rather than:
[0, 1, 2]
[0, 2 , 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
I wonder why?
I am exciting this the 4th time and here's why it happens
It's due to the fact that console log Doesn't happen when it is supposed to happen.
Use this instead of the original console log line
console.log(JSON.parse(JSON.stringify(vals)))
mumbai, delhi, etc.
i calculated how long it would take and that is 42 days lol
u gonna wait 42 days or something??
when he did the function call wrong, I was yelling at him !!!!!!!!!!!!!!!!!!!! So its kind of annoying sometimes, but still its entertaining
gosh..permutation algorithm from misof....hes so famous in competitive programming
A lot of people fear computer science because of the complex words. Same with any science, really. Even the word "science" itself is rather complex.
Please don't, it's just words. If you don't know how to pronounce them, it's OK. Most of the people working with the words every day have no clue how to pronounce them either, they just know what they mean.
But anyway, here's a hint. Slash the word down into its smallest spoken parts. For example, lexicographic: Lek Si Ko Gra Fik
When you either learn to ignore the pronunciation or learn how to pronounce the scary words, the words stop being scary and you'll realize that science is actually quite easy to understand. It's just a lot of those words to take in. You just remember the meaning behind the words, ignore the words themselves and all of a sudden you're doing science.
Pretty much what this channel has been doing for a long time now. You've been doing science without even knowing it. And what's even more awesome, most of that is maths!
And your point is??? Are you saying that science is easy? I think you missed some vocabulary tests in school, just sayin'.
@@avananana No, I'm saying it's easier than people think it is. That doesn't make it easy in any way, but it is not nearly as hard as people seem to think it is. And the reason people think this is because as soon as they hear these complicated words, they get turned off about the whole idea and think they can never understand it.
Then you explain the (in context) simple concepts collected under those words, and people go "Oh, this is easy".
can't you just start at 0, then find the next largest number, then find the next largest number, etc. rather than loop through all the possibilities?
var x = vals[0]
While !vals.length = 0
for(var i = 0, i < vals.length, i++)
if (x < vals[i]) {
x = vals[i]
// i don't know javascript at all but now you can remove x from the array and put it into a new array, then keep doing this until vals doesn't have a length
i think...
I'm probably wrong tho
Yes, this is known as a "selection sort" and would work for getting the array in sorted order (but not for going through all the permutations of the array.)
Daniel Shiffman oh ok. thank you!
But the TSP needs to return back to the city he starts with! Am i right?
bechir jamousi Not in most versions of the problem, though that is also an interesting version.
Can someone please provide the C++ code?
2:35 Asansol 😄
"try and guess which ball the cup is under" swap. this could become an embarrassing game with this guy, first he explains it tells you how, then asks which cup the ball is under.
"it wasnt me, it was i in j"
b in c, that is be in christ
if you dont attempt to get a goal, you dont have any errors
wrong order
14:43 #me endlessly
Should take 42 days to display all 10! possibilities.
Correction:
3628800 / 60 = Seconds
60480 / 60 = Minutes
1008 / 60 = Hours
16.8 Hours total
:) You forgot to divide by 60 since the program is running at 60 frames
CocaCola🤣🤯
can you make a calculator
Lirim Krasniqi I made a calculator in c ++.
It takes 10 hours to me :(
Чел на мефедроне
how the fuck is he typing that fast
Come here from project euler
Dana Carvey teaching algorithms :) too much coffee , slow down a little bit.
uk is best city
There really is nothing wrong in saying travelling salesman. Or saleswoman.
?
plz make a platformer/physics engine plz
I didn't understand the concept of this video at all :(
It's just about implementing an algorithm that generates permutations of an array.
lol. sorry? Have you taken a higher level programming class/calc/discrete math?
+Robert Hird no. didn't understand the reasoning for his combinations. just seemed like he was listing them all
+tehsimo he was trying to list with the algorithm. in the last video he used the swapping technique to get all the possibilities. the problem with that is you need an extra variable that is your temp to store the date. extra variables take up memory, which isn't a problem with small data, but with big data it can become a problem. he is trying to make his program efficient to handle large amounts of data. remember factorials, so if he has 3 possible locations A,B,C, the number of possible routes is 3! (3x2x1) but let's say he has 1000 locations, that's 1000! (1000x999x998x...) possibilities. hope that makes sense, he is trying to make his program more efficient with the algorithm he is modeling with code. (did not proof read this, hope it makes sense)
+Robert Hird ah that makes sense
I kinds forgot about the problem of even doing the sort on the longer character sets. thank you ;) I was baffled by the technical names
are you single?
An alien dislike this awesome video (only one dislike )....
lol anyone else think he's high?
who tf is this happy when they code ? smh.
The explanation was alright, but the implantation was too contrived. You should have rehearsed.
I don't wanna grow up