Injectively saturate bit strings

Question

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.

Task

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 10 in the bitstring. This leaves a string of the form 0...01...1 with 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

Answer 1

Perl 5 -p, 21 bytes

s;((1(?2)*0)|0)*\K0;1

Try it online!

This implements the injection described by Mike Earnest: take the longest prefix consisting of balanced pairs of 1, 0 or unpaired 0s, and change the rightmost unpaired 0 to 1.

Answer 2

Python, 51 bytes

lambda n,k,s:sorted(set(range(n))-s)[-sum(s)%(n-k)]

Attempt This Online!

This is based on hyper-neutrino's answer to the 'three other numbers' challenge. Edit: I now believe I have proved its correctness. Here's a proof by contradiction:

Assume that \$f\$ is not injective. Then there must exist \$s,x,y\$ where \$|s|=k-1\$, \$f(s∪\{x\})=y\$ and \$f(s∪\{y\})=x\$. Take \$x<y\$ without loss of generality, then $$\sum s+y\equiv-p_x\bmod n-k$$ $$\sum s+x\equiv-p_y\bmod n-k$$ $$y-x\equiv p_y-p_x\bmod n-k$$ where \$p_x\$ and \$p_y\$ are the indices into the corresponding 'rest' arrays. But \$p_y-p_x\$ is just the number of integers in between \$x\$ and \$y\$ which are not in \$s\$. Let \$m\$ be the number of values in \$s\$ which are between \$x\$ and \$y\$. We have \$m=(y-x)-1-(p_y-p_x)\$, so \$m\equiv-1\bmod n-k\$. Therefore \$n-k-1\le m\le k-1\$, implying \$k\ge n/2\$. But this contradicts the initial assumption that \$k<n/2\$.

Answer 3

Mathematica, 75 bytes

Modified from @user1502040's answer

Module[{d=-Mod[Total[s],n-k]},Sort[Complement[Rangen-1,s]][[If[d==0,1,d]]]]

Try it online!