I have a sparse matrix like below consisting of data cells (1..9) and empty cells (=zero):
[
[ 1, 2, 0, 3 ],
[ 0, 4, 0, 0 ],
[ 5, 6, 7, 8 ],
]
I'd like to display this as an html table, but there should be no empty cells - they should be "covered" by their neighbouring data cells' row- and colspans:
<table border=1 cellpadding=10>
<tr>
<td rowspan=2>1</td>
<td colspan=2>2</td>
<td>3</td>
</tr>
<tr>
<td colspan=3>4</td>
</tr>
<tr>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
</tr>
</table>
(this is one possible implementation, we could also use colspan=4 on the second row and no rowspan).
Generating actual html is not a problem, but I have trouble writing an algorithm to calculate row and column spans for data cells.
EDIT: still looking for an answer for this. It seems to be trivial to work with colspans only and concatenate each data cell with empty cells on its left/right. However, I'd like cells to be as square shaped as possible, so the answer should include rowspan logic as well. Thanks!
EDIT2: all answers so far summarized here: /
I have a sparse matrix like below consisting of data cells (1..9) and empty cells (=zero):
[
[ 1, 2, 0, 3 ],
[ 0, 4, 0, 0 ],
[ 5, 6, 7, 8 ],
]
I'd like to display this as an html table, but there should be no empty cells - they should be "covered" by their neighbouring data cells' row- and colspans:
<table border=1 cellpadding=10>
<tr>
<td rowspan=2>1</td>
<td colspan=2>2</td>
<td>3</td>
</tr>
<tr>
<td colspan=3>4</td>
</tr>
<tr>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
</tr>
</table>
(this is one possible implementation, we could also use colspan=4 on the second row and no rowspan).
Generating actual html is not a problem, but I have trouble writing an algorithm to calculate row and column spans for data cells.
EDIT: still looking for an answer for this. It seems to be trivial to work with colspans only and concatenate each data cell with empty cells on its left/right. However, I'd like cells to be as square shaped as possible, so the answer should include rowspan logic as well. Thanks!
EDIT2: all answers so far summarized here: http://jsfiddle.net/ThQt4/
Share Improve this question edited May 9, 2014 at 8:32 gog asked Apr 29, 2014 at 11:00 goggog 11.3k2 gold badges27 silver badges42 bronze badges 1- Should a cell be allowed a colspan and a rowspan? – nettux Commented May 8, 2014 at 19:00
6 Answers
Reset to default 5There are a few things to consider in what you want.
If you always prefer squares over the biggest shape, you could end up with a lot of single rows an colums, because a rectangle always starts with a square. And a square or rectangle can only start if the top-left part has a value.
Consider this array:
[1, 2, 3, 4, 5],
[7, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 2, 0, 0, 5]
If you choose squares over the biggest shape you'll end up with a square and three columns
[1] [2] [3] [4] [5] instead of [1] [2] [3] [4] [5]
[ 7 ] [ ] [ ] [ ] [ 7 ]
[ ] [ ] [ ] [ ] [ ]
Furthermore, you could end up with empty single cells:
[1, 1, 2, 0], gives [1] [1] [ 2 ]
[3, 0, 0, 0], [ ] [?] <---
[0, 0, 0, 5], [ 3 ] [5]
[0, 0, 0, 1] [ ] [1]
The largest square here is size 3x3 starting with 3. If you first claim the 3x3 and then the row starting with 2, you'll end up with an empty cell [?] above 5.
One last thing, if you have zeros in the top row or left column, you could also end up in trouble:
V
[1, 0, 0, 2], will leave you with [ 1 ] [?] [2]
[0, 0, 3, 4], [ ] [3] [4]
[0, 5, 6, 7] --->[?] [5] [6] [7]
That said, maybe your array isn't that complicated and maybe you don't mind the empty cells. In either way, it was fun solving this puzzle with your specs. My solution obeys the following rules:
1) squares go first.
2) Size matters. The bigger, the better
3) Rows and colums: Size matters. The biggest go first.
4) Colspan goes over rowspan
Fiddle
var maxv = arr.length;
var maxh = arr[0].length;
var rsv = [];
var rsh = [];
pop_arr();
var shape;
try_sq();
try_rect();
try_loose();
//TRY SQUARES FIRST
function try_sq() {
var sv, sh;
shape = [];
for (sv = 0; sv < maxv - 1; sv++) {
for (sh = 0; sh < maxh - 1; sh++) {
if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) {
continue;
}
check_sq(sv, sh);
}
}
if (shape.length > 0) {
occu();
}
}
//TRY RECTANGLES
function try_rect() {
var sv, sh;
var rect = false;
do {
shape = [];
for (sv = 0; sv < maxv; sv++) {
for (sh = 0; sh < maxh; sh++) {
if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) continue;
check_rec(sv, sh);
}
}
if (shape.length > 0) {
occu();
} else {
rect = false;
}
} while (rect === true);
}
//TRY LOOSE
function try_loose() {
var sv, sh;
//SET THE 1x1 with value
for (sv = 0; sv < maxv; sv++) {
for (sh = 0; sh < maxh; sh++) {
if (arr[sv][sh] !== 0 && (rsv[sv][sh] == -1 || rsh[sv][sh] == -1)) {
rsv[sv][sh] = 1;
rsh[sv][sh] = 1;
}
}
}
//SEARCH FOR rectangles wit no value
var rect = true;
do {
shape = [];
for (sv = 0; sv < maxv; sv++) {
for (sh = 0; sh < maxh; sh++) {
if (arr[sv][sh] !== 0 || (rsv[sv][sh] > -1 || rsh[sv][sh] > -1)) {
continue;
}
rect = check_loose(sv, sh);
}
}
if (shape.length > 0) occu();
else {
rect = false;
}
} while (rect === true);
}
//check SINGLES
function check_loose(start_v, start_h) {
var vd, hd, iv, ih, rect;
var hor = ver = 1;
var horb = 0;
var mxv = maxv - 1;
var mxh = maxh - 1;
rect = true;
vd = start_v + ver;
hd = start_h + hor;
//check horizontal
for (sh = start_h + 1; sh <= mxh; sh++) {
if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) {
break;
}
hor++;
}
//check vertical
for (iv = start_v + 1; iv <= mxv; iv++) {
if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) {
break;
}
ver++;
}
if (hor > ver || hor == ver) {
shape.unshift({
0: (hor),
1: [start_v, start_h, 1, hor]
});
return true;
} else if (ver > hor) {
shape.push({
0: (ver),
1: [start_v, start_h, ver, 1]
});
return true;
}
return false;
}
//check SQUARE
function check_sq(start_v, start_h) {
if (arr[start_v + 1][start_h] !== 0) {
return false;
}
if (arr[start_v][start_h + 1] !== 0) {
return false;
}
var vd, hd, sv, sh, square;
var hor = ver = 1;
var mxv = maxv - 1;
var mxh = maxh - 1;
//CHECK DIAGONAL
do {
square = true;
vd = start_v + ver;
hd = start_h + hor;
//diagonal OK
if (arr[vd][hd] !== 0) {
if (hor == 1) {
if (ver == 1) {
return false;
}
square = false;
break;
}
}
//check horizontal
for (sh = start_h; sh <= hd; sh++) {
if (arr[vd][sh] !== 0) {
square = false;
break;
}
}
if (square === false) break;
//check vertical
for (sv = start_v; sv <= vd; sv++) {
if (arr[sv][hd] !== 0) {
square = false;
break;
}
}
if (square === false) break;
hor++;
ver++;
} while (square === true && vd < mxv && hd < mxh);
//SQUARE OK
if (hor > 1 && ver > 1 && hor == ver) {
shape.push({
0: (hor * ver),
1: [start_v, start_h, ver, hor]
});
}
}
//check RECTANGLE
function check_rec(start_v, start_h) {
var vd, hd, iv, ih, rect;
var hor = ver = 1;
var horb = 0;
var mxv = maxv - 1;
var mxh = maxh - 1;
rect = true;
vd = start_v + ver;
hd = start_h + hor;
//check horizontal
if (start_h < maxh) {
for (sh = start_h + 1; sh <= mxh; sh++) {
if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) break;
hor++;
}
}
//check vertical
if (start_v < maxv) {
for (iv = start_v + 1; iv <= mxv; iv++) {
if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) break;
ver++;
}
}
if (hor == 1 && ver == 1) return false;
if (hor > ver || hor == ver) {
shape.unshift({
0: (hor),
1: [start_v, start_h, 1, hor]
});
return true;
} else {
shape.push({
0: (ver),
1: [start_v, start_h, ver, 1]
});
return true;
}
return false;
}
//FIND LARGEST SHAPE
function occu() {
var le = shape.length;
for (var i = 0; i < le; i++) {
var b = Math.max.apply(Math, shape.map(function (v) {
return v[0];
}));
for (var j = 0; j < shape.length; j++) {
if (shape[j][0] == b) break;
}
var c = shape.splice(j, 1);
claim(c[0][1]);
}
}
//CLAIM SHAPE
function claim(sh) {
var iv, ih;
for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
if (rsv[iv][ih] > -1 || rsh[iv][ih] > -1) return false;
}
}
for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) {
for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) {
rsv[iv][ih] = 0;
rsh[iv][ih] = 0;
}
}
rsv[sh[0]][sh[1]] = sh[2];
rsh[sh[0]][sh[1]] = sh[3];
}
function pop_arr() {
var em = [];
em[0] = arr[0].concat();
for (var i = 0; i < maxh; i++) {
em[0][i] = -1;
}
for (i = 0; i < maxv; i++) {
rsv[i] = em[0].concat();
rsh[i] = em[0].concat();
}
}
You want it as square-shaped as possible? I'd say, you want to prioritize the biggest area. Now to the algoritm. First, let's make the matrix a little bit bigger:
jsFiddle
And this is where I came up with:
jsFiddle
It's using these simple steps:
- It calculates all possible widths and heights a rectangle has to have if it wants to find in the matrix.
- It sorts these values first on if their square or not, prioritizing squares, then on area: from a big area to a small one.
- Then it tries to fit in each rectangle, from big to small.
- A rectangle "fits" if there is 1 number in the rectangle, and at least 1 zero.
- If it fits, he leaves a mark there, so all rectangle after this one can't use those cells.
- It ends when there are no zero's left.
Done.
var Omatrix = [ //Original matrix
[ 1, 2, 0, 3, 4, 0, 2 ],
[ 0, 4, 0, 0, 7, 0, 4 ],
[ 5, 6, 7, 8, 0, 1, 0 ],
[ 1, 0, 0, 0, 4, 0, 0 ],
[ 0, 4, 0, 0, 7, 2, 4 ],
[ 5, 0, 0, 0, 0, 3, 0 ],
[ 0, 0, 0, 0, 4, 9, 3 ],
];
var matrix = []
for (var i = 0; i < Omatrix.length; i++){
matrix[i] = Omatrix[i].slice(0);
}
//calculating all possible lengths
var a = matrix[0].length;
//maximum rectangle width
var b = matrix.length;
//maximum rectangle height
//calculate the area of each rectangle and save it using an array
var array = [];
for (var i = 1; i <= a; i++) {
for (var j = 1; j <= b; j++) {
array.push({"width":i, "height":j, "area":i*j, "square":i===j});
}
}
//sort first on square, then on area: biggest first
array.sort(function(a, b){
if(a.square === b.square){
x = b.area;
y = a.area;
return ((x < y) ? -1 : ((x > y) ? 1 : 0));
}
else{
return a.square? -1:1;
}
});
for(var i = 0; i < array.length; i++){
//working from biggest area to smallest
for(var j = 0; j < matrix.length-array[i].width+1; j++){
//working from left to right
notfound:
for(var k = 0; k < matrix[0].length-array[i].height+1; k++){
//working from top to bottom
var nonzero = false;
var zero = false
//checking if there is exactly one number and atleast one zero
for(var l = 0; l < array[i].width; l++){
//working from left to right
for(var m = 0; m < array[i].height; m++){
//working from top to bottom
if(matrix[j+l][k+m] > 0){
if(!nonzero){
//we have found the first number
//and saved that number for later use
nonzero = matrix[j+l][k+m];
}
else{
//we have found a second number:
//break and go to the next square
continue notfound;
}
}
else if(matrix[j+l][k+m] === 0){
//this is a zero
zero = true;
}
else{
//there is already a square build from this block
continue notfound;
}
}
}
if(!nonzero || !zero){
//there isn't a number here
//or there isn't a zero here
continue notfound;
}
//mark the spots with '-'
for(var l = 0; l < array[i].width; l++){
for(var m = 0; m < array[i].height; m++){
matrix[j+l][k+m] = "-";
}
}
//pack the head of the block with data
matrix[j][k] = array[i].width+"x"+array[i].height+"x"+nonzero;
}
}
}
var tablestring = "";
for(var i = 0; i < Omatrix.length; i++){
tablestring += "<tr>";
for(var j = 0; j < Omatrix[i].length; j++){
tablestring += "<td>"+Omatrix[i][j]+"</td>";
}
tablestring += "</tr>";
}
document.getElementById("table1").innerHTML += tablestring;
var tablestring = "";
for(var i = 0; i < Omatrix.length; i++){
tablestring += "<tr>";
for(var j = 0; j < Omatrix[i].length; j++){
//going trough all the cells
if(matrix[i][j] === "-"){
//a cell with a "-" will not be displayed
continue;
}
else if(typeof(matrix[i][j]) === "string"){
//a cell with a string is the head of a big block of cells.
var add = "";
var data = matrix[i][j].split("x");
if(data[0] !== "1"){
add += " rowspan="+data[0];
}
if(data[1] !== "1"){
add += " colspan="+data[1];
}
tablestring += "<td"+add+">"+data[2]+"</td>";
}
else{
//a normal cell
tablestring += "<td>"+Omatrix[i][j]+"</td>";
}
}
tablestring += "</tr>";
}
document.getElementById("table2").innerHTML += tablestring;
Interesting question. This works in most browsers. It uses the array method reduce which is perfect for these type of problems.
var matrix = [
[ 1, 2, 0, 3 ],
[ 0, 4, 0, 0 ],
[ 5, 6, 7, 8 ],
];
var table = matrix.reduce(function(rows, row){
rows.push(row.reduce(function(newRow, col){
var lastCol = newRow[newRow.length - 1];
if (!col && lastCol) {
lastCol.colspan = (lastCol.colspan || 1) + 1;
} else if (!col && !lastCol) {
var lastRowCol = rows[rows.length-1][newRow.length];
if (lastRowCol) lastRowCol.rowspan = (lastRowCol.rowspan || 1) + 1;
} else {
newRow.push({value:col});
}
return newRow;
}, []));
return rows;
}, []);
var expected = [
[{value : 1, rowspan: 2}, {value:2, colspan: 2}, {value:3}],
[{value : 4, colspan: 3}],
[{value : 5}, {value:6}, {value:7}, {value:8}]
];
table.should.eql(expected); // Passed OK
Note
When I wrote this answer, I hadn't yet read through your comments, where you expressed a preference for sqare representations (ie: colspan=2 rowspan=2 for 3). I'll add a more flexible answer once I find the time.
A simple loop approach might just be enough to tackle this:
var cells = [
[ 1, 2, 0, 3 ],
[ 0, 4, 0, 0 ],
[ 5, 6, 7, 8 ]
],i, j, c, r,tmpString, tbl = [];
for (i=0;i<cells.length;++i)
{
tbl[i] = [];
for (j=0;j<cells[i].length;++j)
{
if (cells[i][j] !== 0)
{
if (j === 0)
{//This only works for first indexes (if not, cells[0][3] + cells[1][3] yields rowspan, too)
r = 1;
while(i+r < cells.length && cells[i+r][j] === 0)
++r;//while next row == 0, add rowspan count
}
c = 1;
while(c+j < cells[i].length && cells[i][j+c] === 0)
++c;
tmpString = '<td';
if (j === 0 && r > 1)
tmpString += ' rowspan="' + r + '"';
if (c > 1)
tmpString += ' colspan="' + c + '"';
tmpString += '>'+cells[i][j]+'</td>';
tbl[i].push(tmpString);
}
}
tbl[i] = tbl[i].join('');
}
console.log('<table border=1 cellpadding=10><tr>' + tbl.join('</tr><tr>') + '</tr></table>');
The varnames are clumsy (at best), but the names are i and j are just simple index/loop counter variables. c counts the colspans that'll be required at any given time, and r does the same for the rowspans. tbl is an is an array of arrays that'll be used to build the table string.
tmpString is just a variable that is used to concat each cell together. Its main reason of existence is to avoid horrid statements like:
tmp[i].push('<td' + (j === 0 && r > 1 ? ' rowspan="' + r + '"' : '')
+ (c > 1 ? ' colspan="' + c +'"' : '') + '>' + cells[i][j] + '</td>'
);
Anyway, the output, after some indentation has been added is this:
<table border=1 cellpadding=10>
<tr>
<td rowspan="2">1</td>
<td colspan="2">2</td>
<td>3</td>
</tr>
<tr>
<td colspan="3">4</td>
</tr>
<tr>
<td>5</td>
<td>6</td>
<td>7</td>
<td>8</td>
</tr>
</table>
Which is, I'd say, pretty close to what you were after
From your example, the colspan is the one plus the number of empty cells to the right of a none empty cell and the rowspan is similarly one plus the number of empty cells below a none empty cell.
Where things get more interesting is when a none empty cell has empty cells both to the right and below. How do you want to handle that situation?
Here In your Java script you have to do following
var str="<table border=1 cellpadding=10>"
var rows=data.lenght();
if(rows>0)
{
for(int r=0;r<rows;r++)
{
var cols=data[r].lenght();
if(cols>0)
{
str+="<tr>";
for(int c=0;c<cols;c++)
{
var colstospan=getnext0(r,c,0); //This function will give you columns to be span... defination given below
str+="<td colspan="+colstospan+">"+data[r][c]+"</td>";
}
str+="</tr>";
}
}
}
str+="</table>";
str will give you table you require...
Here is the Defination of getnext0
function getnext0(rows,cols,count)
{
if(data[rows][cols+1]==0)
{
return getnext0(rows,cols+1,count+1);
}
return count;
}
I hope this will work for you....
please ignore if syntax error in lenght() function...