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 /* Generate a random solution which not is necessarily optimal. */
  11 public class LubbersSolver implements IPetproblemSolver {
  12
  13         private class Tuple {
  14                 public int[] list;
  15                 public int score;
  16
  17                 public Tuple(int[] l, int s) {
  18                         list = l;
  19                         score = s;
  20                 }
  21
  22                 @Override
  23                 public String toString() {
  24                         return score + ": " + Arrays.toString(list);
  25                 }
  26         }
  27
  28         public int factorial(int n) {
  29                 return n==1 ? 1 : n*factorial(n-1);
  30         }
  31
  32         public void permute(int[] num, int start, List<int[]> result) {
  33                 if(start == num.length) {
  34                         result.add(num.clone());
  35                 }
  36                 for(int i = start; i<num.length; i++){
  37                         int t = num[start];
  38                         num[start] = num[i];
  39                         num[i] = t;
  40                         permute(num, start+1, result);
  41                         t = num[start];
  42                         num[start] = num[i];
  43                         num[i] = t;
  44                 }
  45         }
  46
  47         private static int computeCompatibility(int[][] matrix, int[] pairing)
  48         {
  49                 int sum = 0;
  50                 for(int n_i = 0; n_i < pairing.length; n_i++)
  51                 {
  52                         int m_i = pairing[n_i];
  53                         if(m_i == -1)
  54                                 continue;
  55                         sum += matrix[n_i][m_i];
  56                 }
  57
  58                 return sum;
  59         }
  60
  61         @Override
  62         public int[] solve(int n, int m, final int[][] compatibility) {
  63                 System.out.println("n: " + n + " m: " + m);
  64                 int[] possibilities = new int[n];
  65                 for(int i = 0; i<n; i++){
  66                         possibilities[i] = i>=m ? -1 : i;
  67                 }
  68
  69                 if(m<n){
  70                         List<int[]> ps = new LinkedList<int[]>();
  71                         permute(possibilities, 0, ps);
  72                         return Collections.max(ps, new Comparator<int[]>(){
  73                                 @Override
  74                                 public int compare(int[] a, int[] b){
  75                                         return computeCompatibility(compatibility, a) - computeCompatibility(compatibility, b);
  76                                 }
  77                         });
  78                 }
  79                 else{
  80                         System.out.println("not equal...");
  81                         return null;
  82                 }
  83
  84         }
  85 }