Add an integer to a set and take it back out Definition: a set is a datatype which allows testing of inclusion ("does set X contain element Y?") but does not have order. Its size is the number of distinct elements it contains.

Define an efficiently invertible injection from sets of k integers in the range 0 to 1000 inclusive to sets of k+1 integers in the range 0 to 1000 inclusive such that each set maps to a superset of itself. This is not possible for all k: indicate for what range of k your code works. An answer will not be accepted unless it works for at least one k &gt; 4.

Equivalently, provide two functions:


f takes a set of integers between 0 and 1000 (inclusive), and outputs a set of integers in the same range. The output set contains all of the elements of the input set and exactly one element not in the input set.
g inverts f: that is to say, given the output of f it removes the element which f added, and gives back the input of f.


The winner: The encoder/decoder that can handle the longest input set for all permutations of a set of that length.

For sake of space, it is acceptable to post code for only the encoder or decoder, provided that it is clear that the other half the transcoder works.

Inspired by this question.

Edit:

This should be possible for sets of at least five.

Here is an example for a set of three (800 is an arbitrary number; the encoder's implementation and the actual input set will dictate what it is).


Input set: {78, 4, 5}
Output of f({78, 4, 5}): {78, 4, 5, 800}
Output of g({78, 4, 5, 800}): {4, 5, 78}
C#

void Encode(HashSet&lt;int&gt; set)
{
    set.Add((set.Single() + 1) % 1001);
}

void Decode(HashSet&lt;int&gt; set)
{
    set.Remove(set.Equals(new HashSet&lt;int&gt;() { 0, 1000 }) ? 0 : set.Max());
}


Works for a set of length 1.