patternMinor
Efficient algorithm for 'unsumming' a set of sums
Viewed 0 times
efficientalgorithmunsummingforsumsset
Problem
Given a multiset of natural numbers X, consider the set of all possible sums:
$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$
For example, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ while $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$.
What is the most efficient algorithm for calculating the inverse operation (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:
$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$
For example, $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$ while $\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$.
What is the most efficient algorithm for calculating the inverse operation (measured in terms of the size of the input set of sums)? Specifically is it possible to efficiently calculate any of the following:
- Whether a given set is a valid set of sums. (For example, $\left\{0,1,2\right\}$ is valid but $\left\{0,1,3\right\}$ is not.)
- A multiset that sums to the given set.
- The smallest multiset that sums to the given set. (For example, $\left\{1,2\right\}$ and $\left\{1,1,1\right\}$ both sum to $\left\{0,1,2,3\right\}$ but the former is smaller.)
Solution
Solution
Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.
Minimal set algorithm
-
Find maximal element $a_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.
-
Unless there is only one group, represent $a_{m}$ in all possible ways as a pair of sums that add up to $a_{m}$, $S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$
-
Check that all elements from the set of sums are included.
-
Find maximal element $a_{s}$ from all $S_{ij}$ (meaning together) with the following property: for each $S_{ij}$, $a_{s}$ is either in $S_{ij}$, or we can find $a_{p}$ from the set of sums so that $a_{p}+a_{s}$ is in $S_{ij}$.
-
If it is the case that $S_{ij}$ does not contain $a_{s}$, just the sum $a_{s}+a_{p}$, remove $a_{p}+a_{s}$ from $S_{ij}$ (or just set a mark to ignore it) and insert $a_{p}$ and $a_{s}$ in $S_{ij}$ instead.
-
If an element is present in every $S_{ij}$ remove it from all $S_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.
-
Repeat until all $S_{ij}$ are empty
-
If some of $S_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S_{ij}$.
-
Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)
(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)
Example:
$$\{2,3,5,7,8,10,12,13,15\}$$
Represent 15 in all possible ways as a sum of two numbers from the set of sums.
$$(13,2),(12,3),(10,5),(8,7)$$
Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.
13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.
Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
5 is repeating in all groups so we extract it $P=\{5\}$. We extract 5 only once from each group.
$$(8,2),(7,3),(5,5),(3,7)$$
Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine
$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$
Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\{5,5\}$
$$(3,2),(2,3),(5),(3,2)$$
Now we try with 3 and have 5=3+2. Add it to the group.
$$(3,2),(2,3),(3,2),(3,2)$$
Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\{5,5,3,2\}$ and the groups are empty.
$$(),(),(),()$$
Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S_{ij}$ just placing them in $P$ and marking not to alter it any longer.
$$(13,2),(12,3),(10,5),(8,7)$$
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$
Power set coverage
The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)
$$(2=[1],3=[2],5=[4],5=[8])$$
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$
with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.
$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$
$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$
Intermediate sums $(1,2,3,4,5,8,9,10)$
$$((14),1),((13),2),((7),8),(15)$$
Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$
$$\{(15),(15),(15),(15)\}$$
-
Check that the result is $2^m-1$, where $m$ is the number of elements in the soluti
Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.
Minimal set algorithm
-
Find maximal element $a_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.
-
Unless there is only one group, represent $a_{m}$ in all possible ways as a pair of sums that add up to $a_{m}$, $S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$
-
Check that all elements from the set of sums are included.
-
Find maximal element $a_{s}$ from all $S_{ij}$ (meaning together) with the following property: for each $S_{ij}$, $a_{s}$ is either in $S_{ij}$, or we can find $a_{p}$ from the set of sums so that $a_{p}+a_{s}$ is in $S_{ij}$.
-
If it is the case that $S_{ij}$ does not contain $a_{s}$, just the sum $a_{s}+a_{p}$, remove $a_{p}+a_{s}$ from $S_{ij}$ (or just set a mark to ignore it) and insert $a_{p}$ and $a_{s}$ in $S_{ij}$ instead.
-
If an element is present in every $S_{ij}$ remove it from all $S_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.
-
Repeat until all $S_{ij}$ are empty
-
If some of $S_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S_{ij}$.
-
Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)
(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)
Example:
$$\{2,3,5,7,8,10,12,13,15\}$$
Represent 15 in all possible ways as a sum of two numbers from the set of sums.
$$(13,2),(12,3),(10,5),(8,7)$$
Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.
13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.
Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
5 is repeating in all groups so we extract it $P=\{5\}$. We extract 5 only once from each group.
$$(8,2),(7,3),(5,5),(3,7)$$
Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine
$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$
Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\{5,5\}$
$$(3,2),(2,3),(5),(3,2)$$
Now we try with 3 and have 5=3+2. Add it to the group.
$$(3,2),(2,3),(3,2),(3,2)$$
Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\{5,5,3,2\}$ and the groups are empty.
$$(),(),(),()$$
Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S_{ij}$ just placing them in $P$ and marking not to alter it any longer.
$$(13,2),(12,3),(10,5),(8,7)$$
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$
Power set coverage
The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)
- Encode all elements from the minimal set using successive powers of 2. The order is not important. Encode the same element with a new value as many times as it is repeating. Start from C=1, every next element has C=2C.
$$(2=[1],3=[2],5=[4],5=[8])$$
- Replace the elements in the restored recursion list,
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$
with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.
$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$
- Collect all intermediate sums, at the moment we have (1,2,4,8)
$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$
Intermediate sums $(1,2,3,4,5,8,9,10)$
$$((14),1),((13),2),((7),8),(15)$$
Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$
$$\{(15),(15),(15),(15)\}$$
-
Check that the result is $2^m-1$, where $m$ is the number of elements in the soluti
Context
StackExchange Computer Science Q#45525, answer score: 9
Revisions (0)
No revisions yet.