find route for tsp

hi, find all possible routes for n cities. the starting and ending node must be same node and all n cities must be visit only once.

eg: n =4 cities

route start from city 1 and end city 1

possible routes:

1 2 3 4 1

1 2 4 3 1

1 3 2 4 1

1 3 4 2 1

1 4 3 2 1

1 4 2 3 1

like this i need for all cities. need code for this

[Walter Roberson]

hint: perms()

[praveensilvi]

perms(n) will display 4 elements in one array i need 5 elements what will i do

[Walter Roberson]

You take the result of perms and you either:

1. Take a copy of the first column of the result and append it as the last column; or
2. Take a copy of the last column of the result and prepend it as the first column.

Either way the result would be 5 colums in which the first column was the same as the last column.

[praveensilvi]

thanks. if n =20 perms wil work...?

[Walter Roberson]

No. n = 20 would require more than 2 1/4 exabytes of memory (2E18 bytes). The largest known memory capacity in the world is 160 petabytes, which is more than 300000 times smaller. 2E18 bytes exceeds the hardware capacity of all known x64 architecture implementations, which only wire at most 48 bits of memory address, whereas you would need more than 64 bits of memory addressing to hold the results for n = 20.

[praveensilvi]

without using perms function is there any other code to find permutation

[Walter Roberson]

Yes, of course. You can loop for example.

But how long do you have before you have to hand in the homework? If your computer could compute at (say) 2E9 calculations per second, and there are 2432902008176640000 calculations to get through assuming that building each permutation was just a single instruction (somehow), then it would take you a little over 10^9 seconds to get through the list once, which is close to 32 years.

[John D'Errico]

It is not that perms is so memory intensive. It is that the problem you want it to solve will produce a result that is memory intensive. It is trivial to write something that will take an immense amount of memory. That is what you are trying to do, anyway you write it.

[Walter Roberson]

Creating "all possible" traveling salesmen routes can require a lot of storage space to store them all.

Creating each possible route one at a time or in reasonably sized batches, and using individual or groups of possibilities for the purpose of "brute force" calculation of the shortest route, is something that might not take all that much memory -- just enough for one batch, plus a copy of each route that has the same lowest-found-so-far distance. It is difficult to say what fraction of the N! routines will end up in identical minimum values, but you could reduce the memory requirements further by just storing one of the possibilities that has minimum length.

So, brute force does not necessary need much memory. But it can take more time than you can possibly afford to invest, unless you can gain access to a really large cluster of computers.