In this challenge, we consider an encoding from positive integers (up to a limit) to binary sequences. Some examples:
A. 1 -> 00, 2 -> 01, 3 -> 10, 4 -> 11
B. 1 -> 0, 2 -> 1, 3 -> 01
C. 1 -> (empty sequence)
A prefix code is a coding where no code is a prefix of another. B is not a prefix code because the code for 1 (0) is a prefix of that for 3 (01). Fibonacci coding and Elias omega coding are examples of prefix codes that can encode all positive integers.
It is possible to construct a prefix code where 1 encodes to a code of length \$l_1\$, 2 to \$l_2\$, ..., \$n\$ to \$l_n\$ if the sum of \$\tfrac{1}{2}\$ raised to the power of each length does not exceed 1, i.e. \$\sum_{i=1}^{n}{\tfrac{1}{2^{l_i}}} \le 1\$. Your task is to construct such a prefix code where \$l_1, \cdots, l_n\$ is the input.
The following I/O are allowed:
- Take the list as input, and output the list or mapping of encodings for each positive integer
- Take the list and a number to encode as input, and output the encoding for the given number
Each encoding (binary sequence) can be given as a list or a string. Outputting as a single integer is not allowed, as leading zeros are not representable. You can choose to output an encoding for \$0, \cdots, n-1\$ instead of \$1, \cdots, n\$.
Examples
[0] -> {1 -> ""}
[1, 1] -> {1 -> "0", 2 -> "1"}
[2, 3, 4, 4, 5, 5, 5] ->
{1 -> "11"
2 -> "011"
3 -> "0011"
4 -> "1011"
5 -> "00011"
6 -> "10011"
7 -> "01011"}
[3, 3, 3, 1, 3] ->
{1 -> "101"
2 -> "111"
3 -> "110"
4 -> "0"
5 -> "100"}
[5, 4, 3, 2, 5, 4, 3, 2] ->
{1 -> "10101"
2 -> "1011"
3 -> "000"
4 -> "01"
5 -> "10100"
6 -> "1001"
7 -> "001"
8 -> "11"}
