Coding Challenge #35.2: Lexicographic Order

Channel:

The Coding Train

Subscribers:

1,750,000

Published on August 25, 2016 2:55:29 PM ● Video Link: https://www.youtube.com/watch?v=goUlyp4rwiU

Duration: 21:03

159,566 views

2,165

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: https://thecodingtrain.com/challenges/35-traveling-salesperson

p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): https://editor.p5js.org/codingtrain/sketches/FCNAHaCqf
🕹️ Part 2: Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/iYxi30gbl
🕹️ Part 3: TSP with Lexicographic Order: https://editor.p5js.org/codingtrain/sketches/bWPIkEv9s
🕹️ Part 4: TSP with Genetic Algorithm: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9

Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): https://youtu.be/BAejnwN4Ccw
📺 Part 3: TSP with Lexicographic Order: https://youtu.be/9Xy-LMAfglE
📺 Part 4: TSP with Genetic Algorithm: https://youtu.be/M3KTWnTrU_c
📺 Part 5: TSP with Genetic Algorithm and Crossover: https://youtu.be/hnxn6DtLYcY

🎥 Previous video: https://youtu.be/Cl_Gjj80gPE?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
🎥 Next video: https://youtu.be/rX5p-QRP6R4?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
🎥 All videos: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH

References:
🌐 Traveling Salesman on Wikipedia: https://en.wikipedia.org/wiki/Travelling_salesman_problem
🗨️ Permutation Algorithm Using Lexicographic Ordering: https://www.quora.com/How-would-you-explain-an-algorithm-that-generates-permutations-using-lexicographic-ordering
📝 Array on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array
📝 Array.includes() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/includes
📝 Array.reverse() on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/reverse
📝 ES6 Sets on MDN: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Set
💾 The Nature of Code Part 2: https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
📕 The Nature of Code: http://natureofcode.com/

Videos:
🎥 Improved Pool Selection: https://www.youtube.com/watch?v=ETphJASzYes&list=PLRqwX-V7Uu6YJ3XfHhT2Mm4Y5I99nrIKX&index=23
🎥 Genetic Algorithm Playlist: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6bJM3VgzjNV5YxVxUwzALHV
🔴 Live Stream Archive #57: https://youtu.be/r_SpBy9fQuo

Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: https://youtu.be/bGz7mv2vD6g
🚂 #51 A* Pathfinding Algorithm: https://youtu.be/aKYlikFAV4k
🚂 #69 Evolutionary Steering Behaviors: https://youtu.be/flxOkx0yLrY
🚂 #70 Nearest Neighbors Recommendation Engine: https://youtu.be/N8Fabn1om2k

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: http://thecodingtrain.com/
👾 Share Your Creation! https://thecodingtrain.com/guides/passenger-showcase-guide
🚩 Suggest Topics: https://github.com/CodingTrain/Suggestion-Box
💡 GitHub: https://github.com/CodingTrain
💬 Discord: https://discord.gg/hPuGy2g
💖 Membership: http://youtube.com/thecodingtrain/join
🛒 Store: https://standard.tv/codingtrain
🖋️ Twitter: https://twitter.com/thecodingtrain
📸 Instagram: https://www.instagram.com/the.coding.train/

🎥 Coding Challenges: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6ZiZxtDDRCi6uhfTH4FilpH
🎥 Intro to Programming: https://www.youtube.com/playlist?list=PLRqwX-V7Uu6Zy51Q-x9tMWIv9cueOFTFA

🔗 p5.js: https://p5js.org
🔗 p5.js Web Editor: https://editor.p5js.org/
🔗 Processing: https://processing.org

📄 Code of Conduct: https://github.com/CodingTrain/Code-of-Conduct

This description was auto-generated. If you see a problem, please open an issue: https://github.com/CodingTrain/thecodingtrain.com/issues/new

#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js