# Injectively saturate bit strings

It can be easily proven using Hall's marriage theorem that given fixed $$\n\$$ and $$\k, 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 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 ; 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

• Changing the first zero bit to a one bit isn't even injective anyway e.g. n=3, k=1, it would change both 100 and 010 to 110.
– Neil
Feb 20 at 0:31
• @Neil That clause is to prevent answers from effectively returning a new mapping each time. Feb 20 at 0:32
• "be actually able to handle random bit strings in the following cases in reasonable time" Probably better to specify a complexity restraint to make this less subjective. Feb 20 at 4:18
• @Jonah yes, now? Feb 20 at 4:20
• Related: Three other numbers, which asks for the $n=7$, $k=3$ case, but taking the complement of the output set to make it disjoint from rather than a superset of the input.
– xnor
Feb 20 at 5:43

# 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.

# 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 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.

• In your code, rest looks like it's a set, which Python can't index because its sets are unordered. Do you mean to sort it first and make it a list?
– xnor
Feb 23 at 13:46
• @xnor Yes, thanks; I lost the list(..) in some refactoring. I'm not sure if you need to sort or not, but I added it just to be sure. Feb 23 at 14:18
• This answer has been referenced in my answer to the source MSE question! Feb 23 at 19:00

# Mathematica, 75 bytes

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