How a sequence of numbers can be converted to a single number?

Question

I want to convert a sequence of numbers to a single number which will retain individual values as well as their position. e.g. the following sequence is provided-

1,6,7,8,9,45,67

here,take for example,if I apply simple addition i.e. 1+6+7+8+9+45+67 then a number will be generated. But from that no. we can't extract the individual numbers with their ordering[i.e. 1,6,7,8,9,...].

Is there any way to achieve this feature without any ambiguous deduction [i.e only 1 unique set of numbers will be extracted from a number.]? Is there any mathematical function which will be helpful to get back the individual elements from that number?

Answer 1

You can convert this to a base-N number, where N is one larger than the largest value that will appear in your input sequence.

UPDATE

Based on the various comments, I would like to offer an alternative solution that may be easier to implement. You can consider the sequence to be a UTF-8 encoded string and use Huffman coding with a custom dictionary to achieve a compact representation.

The custom dictionary allows you to store very common characters with very few bits (for example, the sequence separator ',' and the individual characters '0'..'9' can be stored with as few as 3 bits, but also other numbers that you find to be statistically likely to occur can be stored in a short bit sequence. For example, if you find that "42" occurs frequently, you could store "42" in just a few bits.

If you only assign special codes to ',' and '0' to '9', you will average less than 4 bits per character in the input string while retaining the comma separating sequence members. Finding common, multi-character substrings and adding them to the dictionary will only improve on that ratio.

Using a custom dictionary also means that you do not have to store the dictionary in the header of the compressed data, since it is well-known to you.

I did something just like this using SharpZipLib

http://www.icsharpcode.net/opensource/sharpziplib/

http://community.sharpdevelop.net/forums/p/8255/23219.aspx

It is also easy to do with zlib

Compressing small piece of data

Answer 2

It's mathematically possible to do it for finite sequences, but not very practical because the numbers required get very big very quickly: there are 67⁷ (about 2⁴²) different length-7 sequences of integers from 1 ... 67, let alone longer sequences and larger integers.

For a simple example of such a function, map the sequence [1,6,7,8,9,45,67] to the value 2¹ * 3⁶ * 5⁷ * 7⁸ * 11⁹ * 13⁴⁵ * 17⁶⁷. The bases are the prime numbers, the powers are the elements in the sequence.

The reverse mapping is computed by division -- the number of times you can divide your value by 2 is the first element in the sequence, etc. The largest prime factor of the value tells you how long the sequence is.

If you want to allow 0 in the sequence as well as positive numbers, then add 1 to all the elements when you raise the primes to the powers. Or alternatively use the power of 2 to give the length of the sequence, then start encoding the elements starting with 3.

Goedel used encodings like this in his proof of his Incompleteness Theorems.

As Kendall Frey says, it is not possible to define a function that maps each infinite sequence of integers to a different integer. This is a consequence of Cantor's proof that the power set of the natural numbers is uncountable: you can't even injectively map all infinite sequences of elements from {true, false} to the integers, let alone all infinite sequences of elements from the integers.

For more practical approaches, think in terms of encoding your sequence of integers as a sequence of bytes, rather than as a number. A finite sequence of bytes can easily be considered to be a binary value, hence it's a number, you just don't really use it as such. A common representation of your example sequence is the sequence of bytes: [1,6,7,8,9,45,67], used for example in JSON. This is a 136-bit number. The mathematical function to reverse this mapping involves arithmetic modulo powers of 256, subtraction of the number 48, multiplication by 10, and suchlike :-)