# Dividing all permutations

Suppose you're trying to solve the Traveling Sales Person problem by going over all possible paths. To do so, you have a number of computers. Each gets $(n-1)!/p$ paths to scan, where $p$ is the number of computers available. In order for each computer to know which paths it's responsible for, you have to send him an encoding of a path prefix, from which it's supposed to exhaustively scan $(n-1)!/p$ paths. The problem is, how would you calculate the size of that prefix and how would you encode it without calculating $(n-1)!$ (since it might be too large) ?

-
Incidentally, if this isn't a hypothetical question, there are faster ways to solve the Traveling Salesman problem using dynamic programming. – Lopsy Jan 5 '13 at 16:24
If calculating $(n-1)!$ is hard, you don't want to try the problem this way at all. Even if $p=10^{12}$, it only takes $n=25$ to get $(n-1)!/p \approx 6\cdot 10^{11}$. I can do $24!$ on my calculator, but I can't do that many loops in any reasonable time. – Ross Millikan Jan 5 '13 at 17:02

How about this: Select a starting node $a_0$ and $r>0$ such that $(n-1)\cdots(n-r)\ge p$. Then create the $(n-1)\cdots(n-r)$ sub-tasks corresponding to all choices of first $r$ steps and distribute them? In fact, if $r>2$ some pre-optimization can be recommended by checking for an optimal tour from first to last node within the selected $r+1$ nodes.
How would you pick $r$ such that each computer gets roughly the same number of paths to search? – Shmoopy Jan 5 '13 at 15:53
It depends. You can assign each CPU either $\lfloor\frac{(n-1)\cdots(n-r)}{p} \rfloor$ subtasks or one more (ignoring the preoptimization for the moment). If this looks too wasteful (e.g. if $(n-1)\cdots(n-r)=kp+s$ with $k$ small and $s$ small nonzero) you can of course divide $s$ tasks into $(n-r-1)$ subtasks each. – Hagen von Eitzen Jan 5 '13 at 16:44