4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Marius Ladegård Meyer Dec 27 '16 at 16:40
  • $\begingroup$ 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! $\endgroup$ – Auslander Dec 27 '16 at 22:04
  • $\begingroup$ Then consider self-posting that solution so others (like me) can learn :) I'll compare your solution to mine and consider posting it. $\endgroup$ – Marius Ladegård Meyer Dec 27 '16 at 22:06
  • $\begingroup$ I'll iron it out and then post - hopefully in the next day. $\endgroup$ – Auslander Dec 28 '16 at 2:18
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Auslander Dec 30 '16 at 3:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.