0

Suppose I have 5 numbers: 1,7,13,5,6. I want to perform some kind of algorithm that allows me to derive a number such that if any of those numbers changed in value or switched in order that I would get a different aggregate.

The aggregate must be unique. In other words the only way to get that aggregate is using exactly those 5 numbers in that exact order.

I have something that is passing all my initial testing but would love to have other people weight in.

Proposed: 1^2 + 1^2 + 7^2 + 2^2 + 13 ^ 2 + 3 ^ 2 + 5^2 + 4 ^2 + 6 ^ 2 + 5 ^ 2

Explanation: I square the number add that to the square of the position it is in the list and then accumulate a grand total.

Bonus: Provided that the proposed solution does work. Any solution that would produce a smaller number or require less operations would be fantastic.

Brian White
  • 1
  • Your function is unchanged if you permute the numbers. – lulu Jul 30 '15 at 19:30
  • Are your numbers constrained to be integers? – lulu Jul 30 '15 at 19:33
  • Yes the numbers are positive integers. They can range from 1 to 95. The length of maximum numbers is known in each case but varies from case to case. So if I said there would be no more than 4000 values does that help? – Brian White Aug 03 '15 at 13:57
  • Certainly. If each number in the list has a maximum of $b$, you can just use the base $b+1$ represetation of your string. Your original example, if you knew the maximum were $15$, would simply translate to $17D56_{16}=97622_{10}$ That is an enormous simplification. The length of the list does not matter – Ross Millikan Aug 03 '15 at 14:03

2 Answers2

1

It is not unique, even up to permutation of the numbers. Note the sum of the squares of the positions just gives a constant depending on the length of the string. We know $\sum_{i=1}^ni^2=\frac 16n(n+1)(2n-1)$, so in your case it is $45$. The simplest example that fails is $(0,0,0,2)$ and $(1,1,1,1)$. Another is $(3,4)$ and $(0,5)$

To get a provably unique value for every string of naturals the values will be large. You can do this with the Cantor pairing function, which can be extended to arbitrary length lists, but it gets complicated. Easier would be to use a hash function.

Ross Millikan
  • 374,822
  • As I understand it, the pairing function only comes into play if you insist on getting all natural numbers as possible values. It's a lot easier if you drop that condition. – lulu Jul 30 '15 at 19:43
  • I don't think so. Do you have a limit on the length of the string and the magnitude of the contents? That makes a huge difference. If so, you have a limit on the total number of strings, so you can compute the number of bits necessary to represent all of them by taking the $\log_2$. Now you have a trade between storage, computation time, and ease of programming. (cont) – Ross Millikan Jul 30 '15 at 23:46
  • If you have a limit on the length of the string, yes you can exploit the linear independence of the square roots of the primes to choose a real $a_1\sqrt 2 +...a_n\sqrt{p_n}$ where $p_n$ is the $n^{th}$ prime. To store that you also need a lot of bits so that you know the real to sufficient accuracy that there is no confusion. Unless you know that most of then entries will be small, you should recognize that bits are cheap. Store the list and you are done. Anything else exploits the fact that some lists are more common than others. Is this true for your application? – Ross Millikan Jul 30 '15 at 23:52
  • Oh, it wasn't my question originally...I have no idea what the OP had in mind (integers aren't even specified). I agree with your comments. I wasn't thinking about the storage issues so much as about the abstract comment "injections from $\mathbb N^2\rightarrow \mathbb N$ are easy to write down while bijections are not. Not obvious to me why injections have to explode in size, but I agree that everything I can think of does. – lulu Jul 31 '15 at 00:07
  • @lulu: I think OP was thinking of lists of naturals. A lot depends on the length of the list. The Cantor pairing fn is quadratic in the maximum value, but you have to know that there are only two elements. If you have $n$ elements, each of which may be up to $k$, you need $n^k$ numbers to represent the list. If you don't know the limits beforehand, you waste some bits on separators. Frankly, I think the question is not well enough specified to have a good answer. There are ways to represent an arbitrary string in many bits. If the string is not arbitrary, you can reduce the length. – Ross Millikan Jul 31 '15 at 00:17
  • @Ross the string is not arbitrary. See my comment to lulu above and let me know if that clarifies things well enough. – Brian White Aug 03 '15 at 13:58
0

Assuming that your numbers are constrained to be integers (though this was not specified) then here's a way to do it:

Choose 5 distinct primes, {$2,3,5,7,11$} for instance. Then given your five numbers {$a_i$} just form the single integer: $$2^{a_1}3^{a_2}5^{a_3}7^{a_4}11^{a_5}$$

lulu
  • 70,402