Anonymous user
Index finite lists of positive integers: Difference between revisions
Index finite lists of positive integers (view source)
Revision as of 04:56, 10 May 2014
, 10 years ago→{{header|Python}}: bijection
(→{{header|Python}}: bijection) |
|||
Line 251:
14307647611639042485573
[1, 2, 3, 10, 100, 987654321]
</pre>
=== Bijection ===
Each number in the list is stored as a length of 1s, separated by 0s, and the resulting string is prefixed by '1' and subtracted by 1 (to make 0 a valid index), then taken as a binary number. Don't use it on large numbers.
<lang python>def unrank(n):
return map(len, bin(n + 1)[3:].split("0"))
def rank(x):
return int('1' + '0'.join('1'*a for a in x), 2) - 1
for x in range(11):
print x, unrank(x), rank(unrank(x))
print #extra test
x = [1, 2, 3, 5, 8];
print x, rank(x), unrank(rank(x))</lang>
{{out}}
<pre>
0 [0] 0
1 [0, 0] 1
2 [1] 2
3 [0, 0, 0] 3
4 [0, 1] 4
5 [1, 0] 5
6 [2] 6
7 [0, 0, 0, 0] 7
8 [0, 0, 1] 8
9 [0, 1, 0] 9
10 [0, 2] 10
[1, 2, 3, 5, 8] 14401278 [1, 2, 3, 5, 8]
</pre>
| |||