# A partition problem

I want to find all partitions of the set $\{1,2,\ldots,40\}$ into disjoint sets $A$ and $B$ such that no subset of $B$ has a sum that is a member of $A$?

I have an algorithm for doing this although it is too slow for a set this size. Is anyone aware of an efficient method? Or does unavoidably reduce to a subset-sum problem?

• There are going to be A LOT of valid partitions... The number of subsets of Range[40] is Sum[Binomial[40, n], {n, 0, 40}], that is, 1 099 511 627 776. Fitting a Exp[b x] to the actual number of valid partitions of Range[m] from m 3 to 15 gives that the number of valid subsets for Range[40] should be ballpark $2 \times 10^7$. What will you be doing with them? – Marius Ladegård Meyer Dec 27 '16 at 16:40
• Thanks, Marius. I will evaluating a function for each valid partition. I've come up with a more efficient way of finding the valid partitions recursively. I haven't run it yet, but it shouldn't take the lifetime of the universe this time! – Auslander Dec 27 '16 at 22:04
• Then consider self-posting that solution so others (like me) can learn :) I'll compare your solution to mine and consider posting it. – Marius Ladegård Meyer Dec 27 '16 at 22:06
• I'll iron it out and then post - hopefully in the next day. – Auslander Dec 28 '16 at 2:18

I will do this recursively, by ensuring in each recursive call that the solutions produced satisfy the criterion in the OP. It suffices to consider $B$: $A$ can always be found by Complement[Range[n], b] if needed.

The recursive function is

rec[set_, totals_, ind_] := Block[{next, newset, newtotals},
Sow[set];
next = Complement[Range[ind, n], set];
Do[
newset = Union[set, {j}];
newtotals = Select[Union[totals, totals + j], # <= n &];
{newset, newtotals} = necessary[newset, newtotals];
rec[newset, newtotals, j + 1]
, {j, next}
]
]


The idea is that, starting from a given set set with known subset sums totals, the new subset sums that appear by adding a number j to set is simply totals + j, as long as we include the empty subset and its sum, 0. For instance, the set {2, 5} has subsets {{}, {2}, {5}, {2,5}} with sums {0, 2, 5, 7}. If we add 8 to this set, the new subsets are {{8}, {2,8}, {5,8}, {2,5,8}}, with sums {8, 10, 13, 15}, of course equal to {0, 2, 5, 7} + 8.

Now, to satisfy the criterion in the OP, we need to check that any number in totals in the range Range[n] is present in set. This is taken care of by the function necessary, that, after adding an "optional" value j to set, continues to add values until newset satisfies the criterion. The function is:

necessary[set_, totals_] := Block[{missing},
missing = Complement[Rest@totals, set];
If[Length@missing == 0, {set, totals},
necessary @@
Fold[
Function[{settot, miss},
{Union[settot[[1]], {miss}],
Select[Union[settot[[2]], settot[[2]] + miss], # <= n &]}],
{set, totals}, missing]
]
]


Finally, the recursive code is called from a wrapper

validPartitions[range_] :=
Block[{n = range},
Reap[rec[{}, {0}, 1]][[2, 1]]
]


Testing:

AbsoluteTiming[MaxMemoryUsed[v40 = validPartitions[40];]]


{484.299998, 1 801 941 672}

Length[v40]


11 347 437

• Hi Marius. That is a great answer - similar but (much) cleaner than mine. Sorry that I hadn't had the time to type it up. – Auslander Dec 30 '16 at 3:45