Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 17:27, 13 February 2022
, 2 years ago→Explicit version
(→{{header|Ruby}}: updated syntax) |
|||
Line 430:
4 5 7 9 0 8 8 7 4 8 8 4 1</lang>
Explanation. We treat the sequence as an n digit number in base m where n is the length of the list and m is 1+the largest value in the list. (This is equivalent to treating it as a polynomial in m with coefficients which are the values of the list, with powers of m increasing from right to left.) In other words 4 5 7 9 0 8 8 7 4 8 8 4 1 becomes 4579088748841. Now we just need to encode the base (10, in this case). To do that we treat this number as a sequence of bits and prepend it with 1 1 1 1 0 1 0 1 0. This is a sequence of '1's whose length matches the number of bits needed to represent the base of our polynomial, followed by a 0 followed by the base of our polynomial.
To extract the original list we reverse this process: Find the position of the first zero, that's the size of our base, extract the base and then use that to find the coefficients of our polynomial, which is or original list.
Whether this is an efficient representation or not depends, of course, on the nature of the list being represented.
=== Tacit versions ===
| |||