Set transformation

Question

I'm looking for a way to transform a set, and having trouble. This is because the requirements are rather rigorous.

Set A contains a bunch of integers, the details are really irrelevant.
Set B contains a bunch of integers, such that:

• Each value in A directly maps to one and only one value in B.
• Each bit is true in one, and only one, value in B.
• The sum of any N values in B has a strict relation to (the sum of) it's original values in A. This relation may not depend on knowing the actual N values in question, although other things like knowing the number of values summed is fine.

It's mainly a thought exercise rather than an actual implementation, so detailing the realities of, for example, the memory constraints which would grow hugely with the size of A.

For example, you could satisfy the first two requirements by simply saying that B[i] = 2^A[i]. But that's not useful, because if you did 2^x = 2^A[i] + 2^A[j], you can't infer that the sum of A[i] and A[j] is x or some other expression which does not involve A[i] or A[j].

I'm tending towards such a transformation being impossible, but thought I'd throw it out there just in case.

Edit: I've been unclear. Sorry. This idea exists mainly in my head.

I already know the sum of the B values. The problem is that I start with the sum of the B values and find the values in B which sum to it, which is trivial due to the unique-bits restriction. The trouble is that the sum is initially expressed in A values, so I have to be able to transform the sum from a sum of A values to a sum of B values. This is useless to me if I have to transform it separately for every possible sum because the transformation depends on the values I'm summing.

More edit: Also, my reverse mechanism from B[i] to A[i] is a lookup table. Don't need an actual existent mathematical function. Any A[i] is unique from any other A[j].

Answer 1

I think your third constraint poses a problem. When you say A is one-to-one onto B, that means there exists an invertible mapping F: A->B and its inverse F': B->A such that F'(F(x))=x. Now, "the sum of any N values in B has a strict relation to the sum of the original values in A". This means that there exists some G such that G(A_1+A_2+...+A_n)=B_1+B_2+...+B_n; the sum of the B-values are related to the A-values. But, because of the first clause, we've established that A_1=F'(B_1), so "knowing the actual N values in question" (A_1 through A_n, although your original question leaves it ambiguous to which values you refer) is the same as "knowing" the B-values, due to the one-to-one correspondence. Thus it is not possible to satisfy constraints one and three simultaneously for a finite set of integers; if you are instructed to "sum these n B-values", you must already know the A-values - just apply the inverse transform.

Answer 2

The trouble is that the sum is initially expressed in A values, so I have to be able to transform the sum from a sum of A values to a sum of B values.

That translates to finding the A values from a sum of A values, which I don't think is possible if the A values are arbitrary.

EDIT: The way you described it, this problem appears to be the subset sum problem, which is NP-complete. You can use dynamic programming to improve its performance, but I don't know if you can go much beyond that.

Answer 3

Given (A_1 + ... + A_n), can we assume each A_i is unique? If not, the problem is impossible: adding A_1 to itself A_2 times gives the same result as adding A_2 to itself A_1 times. If each A_i IS unique, then what are we allowed to assume about the bijection between A and B? For example, if N is known, then A[i] = B[i] + d is trivially reversible for all d. Even if we can assume each A_i in the sum is unique, the problem of recovering the B_i is possible if (and only if) no two subsets of A sum to the same value. How easily the B_i can be recovered depends on the nature of the bijection.