//
//
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//
// Unless required by applicable law or agreed to in writing, software
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

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 <num_sets; i++) {
for(int j = 0; j <num_sets; j++) {
if (i != j) {
// b = solver.Sum([x[i,k]*x[j,k] for k in range(n)]);
solver.Add( (from k in Enumerable.Range(0, n)
select (x[i,k]*x[j,k])).
ToArray().Sum() == 0);
}
}
}

// ensure that all integers is in
// (exactly) one partition
solver.Add( (from i in Enumerable.Range(0, num_sets)
from j in Enumerable.Range(0, n)
select x[i,j]).ToArray().Sum() == n);
}

/**
*
* Set partition problem.
*
* Problem formulation from
* http://www.koalog.com/resources/samples/PartitionProblem.java.html
* """
* This is a partition problem.
* Given the set S = {1, 2, ..., n},
* it consists in finding two sets A and B such that:
*
*  A U B = S,
*  |A| = |B|,
*  sum(A) = sum(B),
*  sum_squares(A) = sum_squares(B)
*
* """
*
* This model uses a binary matrix to represent the sets.
*
*
* Also see http://www.hakank.org/or-tools/set_partition.py
*
*/
private static void Solve(int n=16, int num_sets=2)
{

Solver solver = new Solver("SetPartition");

Console.WriteLine("n: {0}", n);
Console.WriteLine("num_sets: {0}", num_sets);

IEnumerable<int> Sets = Enumerable.Range(0, num_sets);
IEnumerable<int> 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
(from k in NRange select a[i,k]).ToArray().Sum()
==
(from k in NRange select a[j,k]).ToArray().Sum());

// same sum
(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
(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) {
}

//
// 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);
}
}
}