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
;
7 import java
.util
.Comparator
;
11 * Class that implements the pot problem solver.
13 * @author Mart Lubbers
15 public class LubbersSolver
implements IPetproblemSolver
{
21 public Tuple(int[] l
, int s
) {
27 public String
toString() {
28 return score
+ ": " + Arrays
.toString(list
);
32 public int factorial(int n
) {
33 return n
==1 ?
1 : n
*factorial(n
-1);
36 public void permute(int[] num
, int start
, List
<int[]> result
) {
37 if(start
== num
.length
) {
38 result
.add(num
.clone());
40 for(int i
= start
; i
<num
.length
; i
++){
44 permute(num
, start
+1, result
);
51 private static int computeCompatibility(int[][] matrix
, int[] pairing
)
54 for(int n_i
= 0; n_i
< pairing
.length
; n_i
++)
56 int m_i
= pairing
[n_i
];
59 sum
+= matrix
[n_i
][m_i
];
66 * Mart Lubbers' implementation of the pet problem
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
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
;
81 List
<int[]> ps
= new LinkedList
<int[]>();
82 permute(possibilities
, 0, ps
);
84 return Collections
.max(ps
, new Comparator
<int[]>(){
86 public int compare(int[] a
, int[] b
){
87 return computeCompatibility(compatibility
, a
) - computeCompatibility(compatibility
, b
);