JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
a matrix solution | Reply
Hello,

Thanks for posting your article. Just wanted to add that you set up the matrix solution
nicely too and thought I would add that here.

You've created a matrix and want to determine the minimum of the solutions,
where a solution follows the matching rules.

One can use a pattern like the co-factor and determinant pattern for a matrix to find
the total N! solutions for the matrix. afterwards, one can find the minimum of those
N! solutions.

To simplify the determinant determination, sub arrays of the matrix are created that
exclude the column and row of the co-add term (which is similar to pattern for
co-factor term). To reduce the number of subarrays created, I created a pool
of subarrays for re-use in the initialization stage.

The code below could be improved by replacing the String[][] for tracking the
matrix cell positions with char[][][], but that needs additional code to check and expand
bounds of the inner arrays.

The method with that logic below is *sumEachCombination*.

Note, I had to remove some of the boiler plate code because it exceeded message size.

:)
-Nichole


public class MinCostBipartite {

protected List<SubSumTotal> totals = new ArrayList<SubSumTotal>();
protected int[][][] pool;
protected String[][][] poolInd;
protected int length = -1;

protected void initPool(int n) {...}


protected void sumEachCombination(int[][] a, String[][] ind) {

int len = a.length;

// a SubSumTotal is one solution for the matrix. For example: cell[0][0] + cell[1][1] + cell[2][2]

if (len == 1) {

SubSumTotal st = new SubSumTotal(a[0][0], ind[0][0]);
totals.add(st);

return;

} else if (len == 2) {

SubSumTotal st0 = new SubSumTotal(a[0][1], ind[0][1]);
st0.add(a[1][0], ind[1][0]);
totals.add(st0);

SubSumTotal st1 = new SubSumTotal(a[0][0], ind[0][0]);
st1.add(a[1][1], ind[1][1]);
totals.add(st1);

return;
}

for (int row = 0; row <= len; row++) {

int[][] subarray = makeCopy(a);
String[][] indarray = makeCopy(ind);

len = subarray.length;

SubSumTotal st = null;

while (len > 2) {

if (st == null) {
st = new SubSumTotal(subarray[0][row], indarray[0][row]);
} else {
st.add(subarray[0][row], indarray[0][row]);
}

subarray = makeSubarray(subarray, row);

indarray = makeSubarray(indarray, row);

len = subarray.length;
}

if (len == 0) {

totals.add(st);

} else if (len == 1) {

st.add(subarray[0][0], indarray[0][0]);

totals.add(st);

} else if (len == 2) {

SubSumTotal st0 = st.clone();
st0.add(subarray[0][1], indarray[0][1]);
st0.add(subarray[1][0], indarray[1][0]);
totals.add(st0);

SubSumTotal st1 = st.clone();
st1.add(subarray[0][0], indarray[0][0]);
st1.add(subarray[1][1], indarray[1][1]);
totals.add(st1);

}
}
}

public Cell[] findMinCombination(int[][] a) {

if (a == null) {
throw new IllegalArgumentException("a cannot be null");
}
if (a.length != a[0].length) {
throw new IllegalArgumentException("a dimensions must be equal");
}

length = a.length;

initPool(length);

String[][] indarray = new String[length][];
for (int i = 0; i < length; i++) {
indarray[i] = new String[length];
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
indarray[i][j] = i + ":" + j;
}
}

// this occurs N! times --> O(N^2)
sumEachCombination(a, indarray);

// iterate over the N! solutions --> O(N^2)
Cell[] cells = findBestSolution(length);

return cells;
}

protected Cell[] findBestSolution(int n) {
// find in totals, the SubSumTotal with smallest sum and construct a Cell[] from parsed paths in sb
return cells;
}

protected int[][] makeCopy(int[][] a) {
...
}
protected String[][] makeCopy(String[][] a) {
...
}


protected int[][] makeSubarray(int[][] a, int excludeRow) {

// assumes we are always excluding column 0 as our "co-add" column

int len = a.length;

// make sub arrays
int[][] subarray = null;
if ((len-1) > 1) {
subarray = pool[len-1];
} else {
subarray = new int[len-1][];
for (int i = 0; i < (len - 1); i++) {
subarray[i] = new int[len - 1];
}
}

for (int col = 1; col < len; col++) {
System.arraycopy(a[col], 0, subarray[col-1], 0, excludeRow);
System.arraycopy(a[col], (excludeRow + 1), subarray[col-1], excludeRow, (len - (excludeRow + 1)));
}

return subarray;
}

protected String[][] makeSubarray(String[][] a, int excludeRow) {
// similar as for makeSubarray(int[][]
}

public class Cell {
int i = -1;
int j = -1;
public Cell(String[] xy) {
if (xy == null) {
throw new IllegalStateException("xy cannot be null");
}
if (xy.length != 2) {
throw new IllegalStateException("xy has to be 2 elements");
}
i = Integer.valueOf(xy[0]);
j = Integer.valueOf(xy[1]);
}
}
public class SubSumTotal {
protected int sum = 0;
protected StringBuilder sb = new StringBuilder();
public SubSumTotal(int amnt, String amntIndexesStr) {

add(amnt, amntIndexesStr);
}

public void add(int amnt, String amntIndexesStr) {
sum += amnt;
if (sb.length() > 0) {
sb.append(",");
}
sb.append(amntIndexesStr);
}
public SubSumTotal clone() {
SubSumTotal st = new SubSumTotal(sum, sb.toString());
return st;
}
}
Re: a matrix solution (response to post by nkin) | Reply
One could also use Ford-Fulkerson maximum flow algorithm by adding a source to the front of the bipartite graph and a sink to the back of the bipartite graph to make a runtime complexity closer to linear with respect to the number of edges, but make the algorithm minimize the cost.
RSS