049: Number Partitioning

//
// Copyright 2012 Hakan Kjellerstrand
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using Google.OrTools.ConstraintSolver;

public class SetPartition
{


    //
    // Partition the sets (binary matrix representation).
    //
    public static void partition_sets(Solver solver,
                                      IntVar[,] x, int num_sets, int n)
    {

      for(int i = 0; i  Sets = Enumerable.Range(0, num_sets);
    IEnumerable NRange = Enumerable.Range(0, n);


    //
    // Decision variables
    //
    IntVar[,] a = solver.MakeIntVarMatrix(num_sets, n, 0, 1, "a");
    IntVar[] a_flat = a.Flatten();


    //
    // Constraints
    //

    // partition set
    partition_sets(solver, a, num_sets, n);

    foreach(int i in Sets) {
      foreach(int j in Sets) {

        // same cardinality
        solver.Add(
                   (from k in NRange select a[i,k]).ToArray().Sum()
                   ==
                   (from k in NRange select a[j,k]).ToArray().Sum());

        // same sum
        solver.Add(
                   (from k in NRange select (k*a[i,k])).ToArray().Sum()
                   ==
                   (from k in NRange select (k*a[j,k])).ToArray().Sum());


        // same sum squared
        solver.Add(
                   (from k in NRange select (k*a[i,k]*k*a[i,k])).ToArray().Sum()
                   ==
                   (from k in NRange select (k*a[j,k]*k*a[j,k])).ToArray().Sum());
      }
    }


    // symmetry breaking for num_sets == 2
    if (num_sets == 2) {
      solver.Add(a[0,0] == 1);
    }

    //
    // Search
    //
    DecisionBuilder db = solver.MakePhase(a_flat,
                                          Solver.INT_VAR_DEFAULT,
                                          Solver.INT_VALUE_DEFAULT);

    solver.NewSearch(db);

    while (solver.NextSolution()) {

      int[,] a_val = new int[num_sets, n];
      foreach(int i in Sets) {
        foreach(int j in NRange) {
          a_val[i,j] = (int)a[i,j].Value();
        }
      }
      Console.WriteLine("sums: {0}",
                        (from j in NRange
                         select (j+1)*a_val[0,j]).ToArray().Sum());

      Console.WriteLine("sums squared: {0}",
                        (from j in NRange
                         select (int)Math.Pow((j+1)*a_val[0,j],2)).ToArray().Sum());

      // Show the numbers in each set
      foreach(int i in Sets) {
        if ( (from j in NRange select a_val[i,j]).ToArray().Sum() > 0 ) {
          Console.Write(i+1 + ": ");
          foreach(int j in NRange) {
            if (a_val[i,j] == 1) {
              Console.Write((j+1) + " ");
            }
          }
          Console.WriteLine();
        }
      }
      Console.WriteLine();

    }

    Console.WriteLine("\nSolutions: {0}", solver.Solutions());
    Console.WriteLine("WallTime: {0}ms", solver.WallTime());
    Console.WriteLine("Failures: {0}", solver.Failures());
    Console.WriteLine("Branches: {0} ", solver.Branches());

    solver.EndSearch();

  }

  public static void Main(String[] args)
  {
    int n = 16;
    int num_sets = 2;

    if (args.Length > 0) {
      n = Convert.ToInt32(args[0]);
    }

    if (args.Length > 1) {
      num_sets = Convert.ToInt32(args[1]);
    }

    if (n % num_sets == 0) {

      Solve(n, num_sets);
    } else {
      Console.WriteLine("n {0} num_sets {1}: Equal sets is not possible!",
                        n, num_sets);
    }
  }
}