Catch up on stories from the past week (and beyond) at the Slashdot story archive

 



Forgot your password?
typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. ×

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."

Slashdot Top Deals

"There... I've run rings 'round you logically" -- Monty Python's Flying Circus

Working...