The problem can be easily modeled as a CSP problem with 2 sets of N/2 variables (called A_{i} and B_{i}, i in 1..N/2) whose initial domain are the set of integers {1..N}. The variables are constrained as follows:

• all variables are different
• $\Sigma_{i=1}^{N/2} A_i = \Sigma_{i=1}^{N/2} B_i = N * (N+1) / 2 / 2$
• $\Sigma_{i=1}^{N/2} A_i^2 = Sigma_{i=1}^{N/2} B_i^2 = N * (N+1) * (2*N+1) / 6 / 2$

To break symmetries (avoiding permutations of a group, and swapping the two groups) it is better to add these redundant constraints:

• $A_1 < A_2 < … < A_{N/2}$
• $B_1 < B_2 < … < B_{N/2}$
• $A_1 = 1$ (the value 1 is always in the first group))

A good heuristic consists in iteratively placing the biggest missing value (thus in descending order). NB: doing so the “all different” constraint is not needed (only different values are assigned one by one).

If only the first solution is wanted then it is further preferable to first try to put this value in the set which has the smallest sum (sum of already placed values). If all solutions are wanted this value will also be tried in the other group so the test on the sums can involve a little overhead.

File Type Notes
set_partition.lp4 ASP Gringo 4
set_partition_bp.pl B-Prolog
set_partition.co Comet
set_partition.ecl ECLiPSe
set_partition_full.essence Essence
set_partition_simple.essence Essence
set_partition.eprime EssencePrime
set_partition.cpp Gecode
SetPartition_jsr331.java JSR-331
partition.mzn MiniZinc
set_partition.mzn MiniZinc
NumberPartitioning.py Numberjack
set_partition.cs or-tools/C#
set_partition_ortools.py or-tools/Python
SetPartition_oscar.scala OscaR
set_partition_sicstus.pl SICStus Prolog