Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Slashdot Deals: Deal of the Day - Pay What You Want for the Learn to Code Bundle, includes AngularJS, Python, HTML5, Ruby, and more. ×

Submission + - A Permutation on Combinatorial Algorithms (tropicalcoder.com)

TropicalCoder writes: "I don't know what exactly got me obsessed with permutations this past week. I think I was bored and thinking about the Traveling Salesman Problem. I was considering playing with a genetic algorithm to solve it.

Now it turns out that if you want to solve a travelling salesman problem, it would be helpful to know a bit about generating permutations. The idea is that if the salesman doesn't have to visit too many cities, you could simply generate every permutation of the list of cities and measure the distance each route would run and quickly have your answer. Soon I found myself on the Wikipedia page on permutations, and began to play with a classic algorithm. That quickly bored me, so I turned to Doctor Knuth's Art of Computer Programming for more. Did you know he has a full chapter dedicated to this stuff?

For some reason I began subtracting successive permutations, and upon examining the table of values produced, I noticed an interesting pattern. I began to analyse that pattern and became obsessed with it as suddenly a whole world of ideas popped into my head. Here you will find what I have discovered, along with the full source code I developed to prove my theory. In the code I get into a some bit twisting and recursion, and all in all had a very good time. I hope you have as much fun with it as I had."

One picture is worth 128K words.