0

I'm working on a data warehousing project and need to assign a unique value to a permutation and store that value as dimension in the data warehouse. Currently, I'm relying upon a rather large lookup table to determine the unique value and I'm curious if it would be possible to achieve the same result via a function or algorithm.

Here is a small scale example of what I'm trying to accomplish.

Assume you have three values: 1, 2 and 3. Assuming order does not matter there are $3 \times 3 \times 3$ possible permutation. If you were develop a lookup table with all the possibilities it might look something like the following:

  1. 111
  2. 112
  3. 113
  4. ... ...
  5. 333

Now if I code the sequences 112 and 333 I would assign the values of 2 and 27, respectively. The look-up table approach works fine when you have three possible values in three possible position, but as the values and positions increase the look-up approach quickly loses its appeal.

My question is it possible to right a function (psuedo code or otherwise) that given a combination it yields the permutation's or unique value). Alternatively, is there a hash function that would have desirable properties.

Mutuelinvestor
  • 103
  • use the factorial number system. – abel May 24 '15 at 14:30
  • @abel thanks for the response. I just went to Wikipedia to read up on the factorial number system and I'm a little bit out of my depth. Could I trouble you to perhaps demonstrate its application to my example. Thanks again – Mutuelinvestor May 24 '15 at 14:51

1 Answers1

1

You probably just want to code in base three, that is associate to the triple $a_{1} a_{2} a_{3}$ the number $$ 1 + (a_{1} - 1) \cdot 9 + (a_{2} - 1) \cdot 3 + (a_{3} - 1). $$

This becomes much cleaner if you use $0, 1, 2$, and start counting at $0$, then it's $$ b_{2} b_{1} b_{0} \mapsto b_{2} \cdot 9 + b_{1} \cdot 3 + b_{0} $$, that is

  • $000 \mapsto 0$
  • $001 \mapsto 1$
  • etc
  • $222 \mapsto 26$

Conversely, given a number $c$ between $0$ and $26$, you reconstruct $b_{0}, b_{1}, b_{2}$ by first dividing $c$ by $3$ to get $b_{0}$: $$ c = 3 c_{1} + b_{0}, 0 \le b_{0} < 3 $$ then dividing $c_{1}$ by $3$ to get $b_{1}, b_{2}$: $$ c_{1} = 3 b_{2} + b_{1}, 0 \le b_{1} < 3. $$

Andreas Caranti
  • 68,873
  • Andreas -Thanks! - this is exactly what I was looking for. How would this equation change if I had 8 values instead of three (i.e. a1a2a3a4a5a6a7a8) – Mutuelinvestor May 24 '15 at 14:59
  • $b_{7} b_{6} \dots b_{1} b_{0} \mapsto b_{7} \cdot n^{7} + b_{6} \cdot n^{6} + \dots + b_{0}$ if each $b_{i}$ takes $n$ values – Andreas Caranti May 24 '15 at 15:01