Add an integer to a set and take it back out

Question

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 > 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}

Answer 1

C#

void Encode(HashSet<int> set)
{
    set.Add((set.Single() + 1) % 1001);
}

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

Works for a set of length 1.

Answer 2

C#

void Encode(HashSet<int> set)
{
    int x = set.Sum();
    int add;
    if (x % 2 == 0)
    {
        add = x / 2;
    }
    else
    {
        add = (x + 1001) / 2 % 1001;
    }
    set.Add(add);
}

void Decode(HashSet<int> set)
{
    int x = set.Sum();
    if (x % 3 == 1)
    {
        x += 1001;
    }
    else if (x % 3 == 2)
    {
        x -= 1001;
    }
    int remove = x / 3;
    set.Remove(remove);
}

Works for a set of length 2. This is a special case, and only works because 1001 is not divisible by 2 or 3.

Answer 3

Perl 6

Phase 1:

sub add-value(@set) {
    return (0) unless @set.elems >= 1;
    @set .=sort;
    my $sum = [+] @set;
    for ^1009 -> $a {
        my $v = ($sum+$a) % 1009;
        next if $v > 1000;
        next if [or] $v «Z==» @set;
        return (@set, $v) if [and] remove-value((@set, $v)).sort Z== @set
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

Yes, I used the function for phase 3 as extra check in phase 1. It fixes bugs.

Phase 2: Shuffle the set with @set.=pick(*)

Phase 3:

sub remove-value(@set) {
    return () if @set.elems <= 1;
    for ^1009 -> $a {
        for @set.sort -> $b {
            my $sum = 1009 R% [+] $a, @set.grep(* != $b);
            next if $sum > 1000;
            return @set.grep(* != $b) if $sum == $b
        }
    }
    die "Couldn't find anything for " ~ join(',', @set)
}

I lack a bit of processing power to run all combinations atm, but with some 200 random combinations of length 1 through 15 (each) I didn't get any doubles.

Little test script could take about a century or 2 generating roughly 1000! combinations, but will start checking them right after:

for (^1001).combinations -> @set {
    my @newset = add-value(@set);
    @newset = @newset.pick(*);
    my @oldset = remove-value(@newset);
    if not [and] (@oldset.sort() Z== @set.sort()) {
        say "failed for $count, added value $added";
        say join ',', @set.sort;
        say join ',', @oldset.sort;
        die 'bad result';
    }
}

How does it work:

• first calculate $sum of all values already in the set
• for 0 .. 1008 -> $a:
  • $v = sum + $a modulo 1009 (yes, I like prime numbers)
  • if the value $v is over 1000, then try the next number
  • if the value exists already in the set, we can't use it, try next number
  • if running the remove phase on this set gives the wrong result, try next number
  • yay, we found number that works!

Decoding:

• if there's 0 or 1 elements, return empty set
• sort the set to have consistent results
• loop again over all numbers to calculate sum, but
  • get all sets with 1 element removed
  • calculate if that number equals the sum of the other numbers
  • if it's equal, we have a winner

The decoding just removes the first number it finds that equals the sum of the other digits. If none is found it finds the first number that equals the sum of the other numbers + 1. If none ... +2, etc.

Some perl6 syntax:

• ^1009 is same as 0..1008 == (0,1,2,3,4,5,...,1007,1008)
• [+] @set calculates sum of all elements of @set; [and] is also the and operator applied to a list of boolean values
• Z is the zip operator, it zips 2 or more lists into a list of tuples: (1,2) Z (3,4) is same as ((1,3), (2,4))
• Z== applies the == to each pair, giving a list of Booleans
• 1009 R% $sum == $sum % 1009 standard modulo calculation

Answer 4

APL - 73 89 106+ characters, depending on the set's length

Note: So that it'd be easier for the OP to validate, I combined integer a with set b into set c. This way, he could view the set before phase 3 and after phase 3.

n←[enter set's length here]
z←(n+1)?1000
a←z[⍴z]
b←z[⍳(¯1+⍴z)]
c←a,b
c
c[n?n]←c[n?n]
c
c←c-a
d←¯1001×0⍷c
c←c+d
c←c[⍒c]
c←c+a
e←¯1+⍴c
c←e⍴c
a
b[⍒b]
c

Where n is equal to the set's length. Don't forget to set n at the top!

How it works:

n←[enter set's length here] stores the chosen length for the set as n

z←(n+1)?1000 creates an array called z that contains n + 1 unique random numbers from 0 to 1000. We will use the last number of z as the integer to add to the set of other unique numbers

a←z[⍴z] stores the last number of z, or z[length of z], as a, the number we will add to the set

b←z[⍳(¯1+⍴z)] stores all of the data in z, or z[0 thru length of z - 1], as b the set that a will be added to

c←a,b combines arrays a and b into one array, c

c displays c so the OP can see that I added a

c[n?n]←c[n?n] scrambles the data by swapping cells based on n unique random numbers

c, once again, displays c

c←c-a subtracts a from all of the values in c so as to nullify a, which was our added value

d←¯1001×0⍷c creates a new array by multiplying -1001 by a binary "map" of c (which finds our 0 for us and looks something like this: 0 0 0 1 0, where 1 marks the location of the 0 in c)

c←c+d adds to d to c in order to turn the 0 that used to be a into ¯1001, which is one above the maximum number, 1000

c←c[⍒c] orders our data in c from greatest to least. This pushes our ¯1001 all the way to the right

c←c+a restores our original data from b by reversing the c←c=a we did earlier

e←¯1+⍴c creates a variable, e, that is equal to the length of c - 1

c←e⍴c decreases the length of c by 1 and does so by creating a shape with a length equal to e, that contains the data from c, but does not have what used to be a because the length decreased and a was on the right end

a displays a

b[⍒b] displays b from greatest to least

c displays c

Answer 5

366 Characters - Python 2

i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1)
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

Could probably be golfed more, I didn't spend too much time on it. Call a with a list of integers to add a number, and call w with a shuffled version of the new list to remove that number.

Works by appending a loop counter to the sequence, and choosing as the additional number the hash modulo 1001 the concatenated sequence. If the hash generated results in a sequence where there is only one number that can be removed to generate itself for every possible value of the loop counter up to the current one, then output the sequence. Otherwise increment the loop counter and try again. To decode, remove each item from the sequence and see if the hash value of the remaining sequence+loop counter is the removed value. If only one value matches these criteria, it is the solution, otherwise increment the loop counter and try again. This version will hang if faced with an unencodable sequence due to the entire space being taken up by hash collisions, but a check can trivially be added to the a function to simply output that the sequence is unencodable.

Confirmed to work for at least all sets of 2 or less, and works with decreasing probability for larger sets. Higher probabilities might be reachable with a better hash function but that would require more characters. I did some quick random sampling to see what the probability of being able to encode an input sequence of a given size was via this method (you'll notice the precision going down as I got less and less patient):

Size  Probability
  5     100.00%
 10     100.00%
 50     100.00%
100     100.00%
200     98.3%
400     73%
800     8%

Anyone who wants to play with it can use the following version which will output whether a sequence is or is not encodable:

i=lambda v,c,m,j:[h(s(v,m)+[j],x) for x in range(c+1)]
h=lambda v,c:hash(','.join(map(str,sorted(v)+[c])))%1001
a=lambda v,c=0:v+[h(v,c)] if t(h(v,c),v,c) else a(v,c+1) if len(set([n for m in v for n in i(v,c,m,h(v,c))]))<999 else None
s=lambda v,m:[n for n in v if n!=m ]
w=lambda v,c=0:s(v,o(v,c)[0]) if len(o(v,c))==1 else w(v,c+1)
o=lambda v,c:[m for m in v if h(s(v,m),c)==m]
t=lambda j,v,c:all([m not in i(v,c,m,j) for m in v])

if __name__ == "__main__":
    from random import shuffle,randrange,sample
    from operator import eq
    from itertools import combinations
    def random_combination(iterable, r):
        "Random selection from itertools.combinations(iterable, r)"
        pool = tuple(iterable)
        n = len(pool)
        indices = sorted(sample(xrange(n), r))
        return tuple(pool[i] for i in indices)
    valid=invalid=0
    for z in range(100): #change to test more cases
        r=list(sorted(random_combination(range(1001),randrange(1,100)))) #change to test longer sequences
        d=a(r)
        if d is None:
            invalid+=1
            continue
        shuffle(d)
        e=sorted(w(d))
        if not all(map(eq,r,e)):
            raise Exception("Incorrect",r)
        valid+=1
    print "%d Valid, %d Invalid"%(valid,invalid)