LubbersSolver.java

   1 import java.util.ArrayList;
   2 import java.util.LinkedList;
   3 import java.util.Collections;
   4 import java.util.Random;
   5 import java.util.Arrays;
   6 import java.util.List;
   7 import java.util.Comparator;
   8
   9
  10 /**
  11  * Class that implements the pot problem solver.
  12  *
  13  * @author Mart Lubbers
  14  */
  15 public class LubbersSolver implements IPetproblemSolver {
  16
  17         private class Tuple {
  18                 public int[] list;
  19                 public int score;
  20
  21                 public Tuple(int[] l, int s) {
  22                         list = l;
  23                         score = s;
  24                 }
  25
  26                 @Override
  27                 public String toString() {
  28                         return score + ": " + Arrays.toString(list);
  29                 }
  30         }
  31
  32         public int factorial(int n) {
  33                 return n==1 ? 1 : n*factorial(n-1);
  34         }
  35
  36         public void permute(int[] num, int start, List<int[]> result) {
  37                 if(start == num.length) {
  38                         result.add(num.clone());
  39                 }
  40                 for(int i = start; i<num.length; i++){
  41                         int t = num[start];
  42                         num[start] = num[i];
  43                         num[i] = t;
  44                         permute(num, start+1, result);
  45                         t = num[start];
  46                         num[start] = num[i];
  47                         num[i] = t;
  48                 }
  49         }
  50
  51         private static int computeCompatibility(int[][] matrix, int[] pairing)
  52         {
  53                 int sum = 0;
  54                 for(int n_i = 0; n_i < pairing.length; n_i++)
  55                 {
  56                         int m_i = pairing[n_i];
  57                         if(m_i == -1)
  58                                 continue;
  59                         sum += matrix[n_i][m_i];
  60                 }
  61
  62                 return sum;
  63         }
  64
  65         /**
  66          * Mart Lubbers' implementation of the pet problem
  67          *
  68          * @param n the amount of children
  69          * @param m the amount of pets
  70          * @param compatibility the compatibility matrix of pets and children
  71          * @return the optimal distribution of pets and children
  72          */
  73         @Override
  74         public int[] solve(int n, int m, final int[][] compatibility) {
  75                 System.out.println("n: " + n + " m: " + m);
  76                 int[] possibilities = new int[n];
  77                 for(int i = 0; i<n; i++){
  78                         possibilities[i] = i>=m ? -1 : i;
  79                 }
  80
  81                 List<int[]> ps = new LinkedList<int[]>();
  82                 permute(possibilities, 0, ps);
  83
  84                 return Collections.max(ps, new Comparator<int[]>(){
  85                         @Override
  86                         public int compare(int[] a, int[] b){
  87                                 return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
  88                         }
  89                 });
  90         }
  91 }