It can be easily proven using Hall's marriage theorem that given fixed \$n\$ and \$k<n/2\$, there is an injective (one-to-one) function from all \$n\$-bit strings with \$k\$ ones to \$n\$-bit strings with \$k+1\$ ones such that an input and its corresponding output differ by exactly one bit. For example, with \$n=5,k=2\$:
00011 -> 00111 00110 -> 01110 01100 -> 11100 11000 -> 11001 10001 -> 10011 00101 -> 01101 01010 -> 11010 10100 -> 10101 01001 -> 01011 10010 -> 10110
However, the proof is non-constructive. It would be nice to have an explicit construction.
Given a nonempty \$n\$-bit string with \$k<n/2\$ ones, output an \$n\$-bit string with \$k+1\$ ones formed only by changing one zero in the input to one, such that the \$\binom nk\$ distinct inputs map to \$\binom nk\$ distinct outputs. You must prove that your program has this property.
The bit strings may be represented in any reasonable format, including as decimal numbers and as subsets of a specified \$n\$-element set. You may also simply output the index of the changed bit rather than the full string.
The output must be deterministic — it is not allowed to simply change the first zero in the input each time for example; there must be exactly one mapping implemented for each valid \$(n,k)\$ pair. The program or function must also work for all valid \$(n,k)\$ pairs in theory, and have at most polynomial time complexity in \$n\$.
Otherwise this is code-golf; fewest bytes wins.
This question was based on this MathsSE post, which at the time of posting this question had no answers. There is now an answer by Mike Earnest giving an injection that satisfies this challenge's constraints:
- Repeatedly delete occurrences of
10in the bitstring. This leaves a string of the form
0...01...1with at least one zero.
- Change the rightmost remaining zero (at its original location) to a one.
100011010001011 XX XXXX XX 001 00 11 X X 00 0 11 ^ change this to 1