2

I read this post which is quite close to the problem I'm having, but couldn't generalize it. I'm trying to solve the Traveling Sales Person by searching all paths using multiple CPU's. What I need, is a way to encode a path prefix to integer and distribute it to each CPU so it would know what paths it's supposed to scan. For example, if the number of cities is 10 one possible 3-prefix (suppose prefix length is fixed and known) is 4-10-3 (there are 10*9*8 prefixes), so the CPU which would receive it, would search all paths that begin with 4-10-3. Since the number of cities is quite large, I can't compute n! thus I can't use the post above.

Community
  • 1
  • 1
Shmoopy
  • 5,334
  • 4
  • 36
  • 72
  • I think I understand what you're trying to do. What I don't understand is which part of it you are having difficulty with. – NPE Jan 05 '13 at 19:06
  • 1
    @NPE Suppose number of cities is 10 and prefix size is 3 (fixed). So there are 10*9*8 different prefixes. I'm having difficulty with finding a mapping between a number in the range of [1,10*9*8] and a prefix. – Shmoopy Jan 05 '13 at 19:09

2 Answers2

2

The standard representation of a permutation as a number uses Lehmer codes represented in the factorial number system. The idea is that every permutation of n elements can be mapped to a sequence of n numbers, the first of which is in the range 0 to (n - 1), the second of which is in the range 0 to (n - 2), etc. This sequence of numbers can then be represented as a single integer in the factorial number system.

I believe that it should be possible to adapt this trick to work with prefixes of permutations rather than entire permutations. Suppose that you have n elements and want to choose a permutation of k of them. To do this, start off by computing the Lehmer code for the partial permutation. Instead of getting a sequence of n numbers, you'll get back a sequence of k numbers. For example, given the partial permutation c a d drawn from a b c d e f g, your Lehmer code would be found as follows:

  • c is the second (zero-indexed) element of a b c d e f g
  • a is the zeroth (zero-indexed) element of a b d e f g
  • d is the first (zero-indexed) element of b d e f g

So the Lehmer code would be (2, 0, 1).

Once you have this Lehmer code, you can try to encode it as a single integer. To do this, you can use a modified factorial number system encoding. Specifically, you can try doing the following. If you have n elements and want a permutation of k of them, then there will be a total of (n - k + 1) possible choices for the very last element. There are a total of (n - k + 2) possible choices for the second-to-last element, (n - k + 3) possible choices for the third-to-last element, etc. Consequently, you could take your Lehmer code and do the following:

  1. Keep the final digit unchanged.
  2. Multiply the second-to-last element by (n - k + 1).
  3. Multiply the third-to-last element by (n - k + 1)(n - k + 2) 4 ...
  4. Multiply the first element by (n - k + 1)(n - k + 2)...(n - 1)
  5. Sum up these values.

This produces a unique integer code for the permutation.

For example, our Lehmer code was (2, 0, 1), n = 7, and k = 3. Therefore, we'd compute

1 + 0 × (7 - 3 + 1) + 2 × (7 - 3 + 2)(7 - 3 + 3)

= 1 + 2 × (5 × 6)

= 5 + 2 × 30

= 61

To invert this process, you can take the integer and run it backwards through this procedure to recover the partial Lehmer code. To do this, start off by taking the number and dividing by (n - k + 1)(n - k + 2)...(n - 1) to get back the very first digit of the Lehmer code. Then, mod the number by (n - k + 1)(n - k + 2)...(n - 1) to drop off the first digit. Then, divide the number by (n - k + 1)(n - k + 2)...(n - 2) to get back the second digit of the Lehmer code, then mod by (n - k + 1)(n - k + 2)...(n - 2) to drop off the second digit. Repeat this until all the digits of the Lehmer code have been reconstructed.

For example, given prefix 61, n = 7, and k = 3, we would start off by dividing 61 by 7 × 6 = 30. This gives 2, remainder 1. Thus the first digit of the Lehmer code is 2. Modding by 30, we get back the number 1. Next, we divide by 6. This gives 0, remainder 1. Thus the second digit is 0. Finally, we read off the remaining number, which gives the last digit of the Lehmer code, 1. We have recovered our Lehmer code (2, 0, 1), from which we can easily reconstruct the permutation.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • It does, thanks! You wrote: "then there will be a total of (n - k + 1) possible choices for the very last element" - why not n possible choices? am I missing something? – Shmoopy Jan 06 '13 at 07:08
  • @Shmoopy- Once you've picked the first k - 1 elements, your choice for the kth element must be made from the n - (k - 1) = n - k + 1 elements that remain. Does that make sense? – templatetypedef Jan 06 '13 at 07:18
  • Oh gotcha, the first has (n-1) the second has (n-2) and the k'th has (n-k+1). – Shmoopy Jan 06 '13 at 07:29
1

The easiest way here is to map the prefix without treating it as part of a permutation. Don't map the prefix to [0,10*9*8-1], but rather to [0,10*10*10-1], so the prefix 0,4,5 will be mapped to the number 45, and the prefix 4,1,9 will be mapped to the number 419 (assuming there are 10 cities over-all, of course).

zmbq
  • 38,013
  • 14
  • 101
  • 171
  • This is a much easier solution than my approach. :-) The only concern I have is that for long prefixes of large sets, this might overflow an integer more quickly than a more efficient mapping. – templatetypedef Jan 05 '13 at 19:46
  • Indeed, but I think there aren't going to be a lot of cases where this technique is going to overflow and the most efficient technique isn't. That is, you might be able to squeeze in another city, but I doubt you'll be able to squeeze in more. If you reach this problem, you'll have to solve it another way (not using an integer to encode the entire prefix) – zmbq Jan 05 '13 at 21:12
  • This is a bit problematic since it might be ambiguous. The number 12 can be interpreted as 1-2 or 12 so you would have to separate them by, say, -1. That would limit the size of prefix I can support. – Shmoopy Jan 06 '13 at 06:53
  • It isn't ambiguous at all. If you have 10 cities and the prefix contains 3 cities, "12" is only "city 0, city 1, city 2" and. There is no other meaning. The problem is the other side - 444 is not a legal prefix, but that isn't a real issue since he's the one encoding the prefixes. – zmbq Jan 06 '13 at 10:26