2
$\begingroup$

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, the algorithm allows me to reproduce the same unique value from them.

Also no other set of numbers should produce that unique value with the same function. how can this be done?

plz fix tags: I am not sure which ones will be appropriate for this question

clarification: the unique value has to be a number

  • 2
    I will assume that your numbers are non-negative *integers*. The suggestion of Austin Mohr is very good, even if you want your value to be an integer. Put the numbers in non-descending order, and concatenate the ascii values of the digits, separated by the ascii value of the comma.2012-01-31

3 Answers 3

4

If I understand you, you're looking for a function $f$ on the set of finite sequences of natural numbers such that $f(s) = f(t)$ if and only if $t$ is a permutation of $s$. If $p_j$ is the $j$'th prime, you could use $f(a_1, \ldots, a_n) = \prod_{j=1}^n p_j^{a_{(j)}}$ where $a_{(j)}$ is the $j$'th order statistic, i.e. $a_{(1)}, \ldots, a_{(n)}$ are $a_1, \ldots, a_n$ sorted into increasing order.

EDIT For example: with $12$, $13$ and $18$, the result would be $2^{12} 3^{13} 5^{18} = 24911296875000000000000$.

Alternatively, take the base-8 representations of $a_{(1)}, \ldots, a_{(n)}$, put 9's between them as separators, and concatenate as a base-10 number.

EDIT For example, with $12$, $13$ and $18$, since $12 = 14_8$, $13 = 15_8$ and $18=22_8$ (i.e. $12 = 1 \times 8 + 4$, $13=1 \times 8 + 5$, $18 = 2 \times 8 + 2$), the result would be $14915922$.

  • 0
    @Charles Morisset: yes, that would also work.2012-02-02
3

@RobertIsrael's solution is good, and another solution is to sum the powers of 2 for each number you have. With your example, you would have: $2^{12} + 2^{13} + 2^{18}$.

The advantage is that this operation is really fast (powers of 2 are just bit shifting), the downside is that if you want your value to be an integer, the maximum number you can use is 32, otherwise you would need to use some big integers, in which case it can be simpler to use a string representation, as indicated by @AustinMohr.

Edit: As pointed out by Gerry, this approach works only if each number is unique.

  • 0
    That's true, I think I automatically assumed that the input was a set of values, and therefore without repetition.2012-02-01
1

You could consider each of the numbers a root for a polynomial. if you have 3 numbers you could construct a polynomial of degree 3 as follows:

$f(x)=(x-n1)(x-n2)(x-n3)$

in your example you have the numbers: 13, 12, 18, so n1=13, n2=12, n3=18 and you can write the above function as follows:

$f(x)=(x-13)(x-12)(x-18)$

Each of the values 13, 12, 18 will make f(x) zero. No other value would do that.

Edit

as per the note below, if you want any permutation of the input value 131218 to result in a unique value, we may still use the same concept as in the above by constructing f(x) using single digits. So, given 13,12,18 we would construct

$f(x) = (x-1)(x-1)(x-1)(x-3)(x-2)(x-8)$ or simply

$f(x)=(x-1)(x-3)(x-2)(x-8)$

  • 0
    @AustinMohr, thanks for your clarification. If this is the case, I need to work something smarter :)2012-02-01