4
$\begingroup$

I am given a list of $n>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$).

My problem is that I would like to efficiently map each element product to unique integer. Also, I would like to efficiently compute the integer, when I change the order of the arrays in the list.

I was thinking something in the line of integer factorization.

Take first $n$ primes ($p_1, p_2, ..., p_n$) and remeber the index of the array in the original list with $ind: A \rightarrow \mathbb{N}$. So the initial function would be $ind(A_i)=i$.

Also we denote with $a_{i,j}$ the $j$-th element of the $i$-th array in the list. So the function $F:A_1 \times A_2 \times \ldots \times A_n \rightarrow \mathbb{N}$ would be:

$$F(a_{1,i_1}, a_{2,i_2}, \ldots, a_{n,i_n})=\prod_{j=1}^{j=n}p_{ind(A_i)}^{i_j}$$

In more common words, we initially assign a prime number $p_i$ to array $i$ and raise $p_i$ to the index of the element in array $i$.

This guarantees us the uniqueness and also if we change the order of the arrays in the list, we just need to change the $ind$ function. But the problem here is that these products are fairly large and will overflow soon enough (even with using doubles).

Do you have any better idea how to enumerate these products without the large number constraint? I am implementing this in Java and I really would not like to use BigInteger implementation.

$\endgroup$
  • $\begingroup$ Is it hashing you are after, or what is the purpose here? $\endgroup$ – Raphael Apr 5 '13 at 10:10
  • $\begingroup$ Yes. Something like that. I actually need unique numbers, because these output numbers represent some kind of output (the number is actually mapped to a string value). So for example I need to get different integers for (1,2,3) and for (3,2,1). $\endgroup$ – Nejc Apr 5 '13 at 11:57
  • 2
    $\begingroup$ What is the "element product", is it the product of all elements in one array? Why would this change when the order of the arrays is changed? $\endgroup$ – Juho Apr 5 '13 at 15:30
  • $\begingroup$ Based on your description, I take it that an element product is taking one element from each array and multiplying (you should clarify that). $\endgroup$ – Aryabhata Apr 5 '13 at 17:26
  • $\begingroup$ Sorry for not being clear! One element product of $n$ arrays is a $n$-tuple, where we take one element from each array and on the $i$-th place of the $n$-tuple is an element from $i$-th array. Clearly there are $|A_1| \cdot |A_2| \cdot \ldots \cdot |A_n|$ such products. $\endgroup$ – Nejc Apr 5 '13 at 17:45
1
$\begingroup$

Based on your description, I take it that an element product is taking one element from each array and multiplying?

You don't really need to multiply or use prime numbers which might overflow (but not too much for your constrains I suppose, and is a cute solution :-)).

Suppose the arrays were of fixed size $k$ (You can pad the arrays to achieve this, and based on your constraints, won't be too much of a problem).

Then you want to map all possible tuples $(x_1, x_2, \dots x_n)$ where $0 \le x_i \lt k$ to unique integers.

The mapping you need: Interpret the tuple as an integer in base-$k$.

If arrays are shuffled you can still change the $ind$ function and remap the digits according to that.

(or did you try that and didn't work for some reason?)

$\endgroup$
1
$\begingroup$

You want an injection between your element space and the naturals. Why not take the oldest one that happens to be a bijection, the Cantor pairing function.

Its basic form is defined to map $\mathbb{N^2}$ to $\mathbb{N}$:

$\qquad\displaystyle \pi(k_1,k_2) = \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2$.

It readily extends to $\mathbb{N}^k$:

$\qquad \pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) = \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)$.

The Wikipedia article explains how to invert the function.

Now, in your case, $n$ is unknown. That's not a problem; we can extend above $\pi$ easily to enumerate $\mathbb{N}^+ = \bigcup_{n \geq 1} \mathbb{N}^n$ by encoding $n$ -- here the array's length -- as well:

$\qquad \pi^+(a_1,\dots,a_n) = \pi^{(n+1)}(a_1, \dots, a_n, n)$.

Since it's a bijection into $\mathbb{N}$, values are arguably as small as possible. Also, computing either direction is efficient.

When implementing it, be very carful either way. If you consider arrays over some finite set $A$, there are

$\qquad\displaystyle \sum_{i=1}^n |A|^i = \frac{|A|^{n+1} - |A|}{|A| - 1}$

many arrays of size at most $n$. $\pi^+$ has to encode them all, so the integers might overflow quickly if $|A|$ and $n$ are not both small.

$\endgroup$
  • $\begingroup$ Thank you for your nice suggestion. Luckily I do not need the inverse function, so I will implement the Cantor pairing function and compare it to the suggestion of @Aryabhata. $\endgroup$ – Nejc Apr 8 '13 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.