I have a set $S$, which contains $n$ real numbers, which generically are all different. Now suppose I know all the sums of its subsets, can I recover the original set $S$?
I have $2^n $ data. This is far more than $n$, the number of unknowns.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ "I have $2^n$ data" -- but, importantly, you don't have $2^n$ equations (if all you have is the set of sums. Otherwise, the problem is trivial). $\endgroup$– John ColemanAug 2, 2021 at 22:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
No you can't. Consider any set $S=\{a,b,c\}$ with $a+b+c=0$, and the set $S'=\{a+b,b+c,c+a\}$.
The subset sums for $S$ are $0, a, b, c, a+b, b+c, c+a, a+b+c=0$.
The subset sums for $S'$ are $0, a+b, b+c, c+a, a+2b+c=b, b+2c+a=c, c+2a+b = a, 2(a+b+c)=0$.
Hence, you can't distinguish $S$ and $S'$ from the subset sums: $0, a, b, c, a+b, b+c, c+a, 0$.
If all elements are non-negative, then the smallest subset sums should respectively correspond to the empty set and the singletons made up of the smallest two elements, thus you can know the smallest two elements. Once you know the smallest $k$ elements, you can know the subset sums corresponding to the subsets made up of these $k$ elements. Extract them, then the smallest subset sum should correspond to the $(k+1)$-th smallest element. Repeat the process above, you will finally get all elements.
-
2
-
5$\begingroup$ The final algorithm assumes that no subset sum is also one of the original elements. For example, the subset sums for $\{1,2,3\}$ would be $\{0,1,2,3,4,5,6\}$, from which your algorithm would return $\{1,2,4\}$ as the original set. If we allow duplicates in the subset-sums though (so there are always $2^n$ elements), I believe it should work. $\endgroup$ Aug 3, 2021 at 19:07
$\begingroup$
$\endgroup$
2
If you know the sums of all the two element subsets you can recover the elements unless $n$ is a power of $2$. See
- Jan Boman, Ethan D. Bolker, Patrick O'Neil, The Combinatorial Radon Transform modulo the Symmetric Group, Advances in Applied Mathematics, Volume 12, Issue 4, December 1991, Pages 400-411.
-
1$\begingroup$ This assumes you can distinguish the 2-element sums from other n-element sums. We clearly can't assume we know how many elements went into each sum, since the 1-element sums would just be the elements themselves. $\endgroup$ Aug 3, 2021 at 18:59
-
1$\begingroup$ @BlueRaja-DannyPflughoeft Agreed. This theorem assumes you have only the two element sums, so there's nothing to distinguish. So it's is not an answer to the exact question asked. But often here the exact question asked is not exactly what the OP needs. I posted because it might turn out useful. $\endgroup$ Aug 3, 2021 at 21:59