Eliminating "duplicate" permutations easily

[Icytroll]

Hello all

I've been working on a little program, that finds the shortest route between given sets of cartesian coordinates, and displays it on a graph.

I've gotten it to work just fine, but there is a major flaw that I'm hoping that someone could help me with.

I'm kind of brute forcing my way through the objective of finding all the possible permutations with for loops, and when the route consists of 10+ coordinates, the number of permutations starts growing fast, which takes a looooong time to process.

So i'm trying to figure out if I can get through all these permutations, without having to do it through time consuming for loops, or a clever way to cut down the remaining duplicate routes, without putting further load on the program.

Inside the program, I've written down some more specific info about how I've already cut away a big chunk of duplicate routes.

Thanks for any help in advance 🙂

[GerdW · Accepted solution]

Hi lcytroll,

you might start with some easy improvements:

- use primitives like ">0" instead of ">" to compare with zero

- don't use BuildArray with a shift register when a simple autoindexing tunnel will do the same…

- instead of putting two IndexArray node you can use just one with two outputs, no need to supply index constants when you want consecutive elements starting from index 0…

(Summary: remove Rube-Goldberg code fragments!)

Then you might want to read the Wikipedia article on the Travelling salesman problem - many people before have tackled exactly the same problem like you!

[Bob_Schor]

Sounds like a variant of the Traveling Salesman Problem, which is one of those famous NP-Complete problems in Computer Science.  Perhaps some Web research might contain some useful ideas ...

Bob Schor

[Icytroll]

Thanks for pointing out the simple stuff GerdW, and I guessI'll look into what this salesman is all about 🙂