Posted on by Kalkicode
Code Matrix

# Sparse matrix implementation

The problem at hand involves the implementation of a sparse matrix representation. Sparse matrices are matrices in which most of the elements are zero. Representing such matrices efficiently can save memory and computation time.

## Problem Statement

Given a dense matrix (a matrix with mostly zero elements), the goal is to convert it into its sparse representation. The sparse representation stores only the non-zero elements along with their row and column indices.

## Solution Approach

The provided code offers a solution by implementing the following steps:

1. Display the original dense matrix using the `show_data` function.
2. Count the number of non-zero elements in the matrix using a nested loop.
3. If there are more than one non-zero elements, initialize a result matrix to store the sparse representation.
4. Iterate through the dense matrix and for each non-zero element: a. Store its row index in the result matrix's current row. b. Store its column index in the result matrix's current row. c. Store the element value in the result matrix's current row.
5. Display the sparse representation in the format: "Row Column Value".

## Pseudocode

``````function show_data(matrix):
for i from 0 to ROW - 1:
for j from 0 to COL - 1:
print matrix[i][j]
print newline

function sparse_matrix(matrix):
counter = 0
for i from 0 to ROW - 1:
for j from 0 to COL - 1:
if matrix[i][j] is not zero:
increment counter
if counter > 1:
initialize result matrix of size counter x 3
counter = 0
for i from 0 to ROW - 1:
for j from 0 to COL - 1:
if matrix[i][j] is not zero:
store i in result[counter][0]
store j in result[counter][1]
store matrix[i][j] in result[counter][2]
increment counter
print "ROW Col Value"
for i from 0 to counter - 1:
print result[i][0], result[i][1], result[i][2]

matrix = predefined dense matrix
show_data(matrix)
sparse_matrix(matrix)``````

## Algorithm Explanation

1. The `show_data` function displays the elements of the dense matrix row by row.
2. The `sparse_matrix` function counts the non-zero elements in the dense matrix.
3. If there's more than one non-zero element, the function initializes a result matrix to store the sparse representation.
4. It iterates through the dense matrix and for each non-zero element: a. Stores its row index in the result matrix. b. Stores its column index in the result matrix. c. Stores the element value in the result matrix.
5. The sparse representation is displayed in the format "Row Column Value".

## Code Solution

``````/*
C Program
+ Sparse matrix representation
*/
#include <stdio.h>
#define ROW 5
#define COL 4

//Display element of matrix
void show_data(int matrix[][COL])
{
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
printf("%3d",matrix[i][j] );
}
printf("\n");
}
printf("\n");
}

void sparse_matrix(int matrix[ROW][COL])
{
int counter=0;
//Get number of non zero element
for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
if(matrix[i][j] != 0)
{
//When number is not zero
counter++;
}
}
}
if(counter>1)
{

//Row Column And value container
int result[counter][3];

counter=0;

for (int i = 0; i < ROW; ++i)
{
for (int j = 0; j < COL; ++j)
{
if(matrix[i][j]!=0)
{
//Assign row value
result[counter][0]=i;
//Assign column value
result[counter][1]=j;
//Assign value
result[counter][2]=matrix[i][j];

counter++;
}
}

}
printf("\n ROW Col Value \n");
//Print resultant matrix
for (int i = 0; i < counter; ++i)
{

printf("%3d  %2d  %2d \n",result[i][0],result[i][1],result[i][2]);

}

}
}
int main(){

int matrix[ROW][COL] = {
{ 0, 1, 0, 0 },
{ 0, 0, 2, 0 },
{ 0, 3, 0, 0 },
{ 1, 0, 5, 0 },
{ 0, 6, 0, 4 } };

show_data(matrix);
sparse_matrix(matrix);

return 0;
}```
```

#### Output

``````  0  1  0  0
0  0  2  0
0  3  0  0
1  0  5  0
0  6  0  4

ROW Col Value
0   1   1
1   2   2
2   1   3
3   0   1
3   2   5
4   1   6
4   3   4``````
``````/*
C++ Program
Sparse matrix representation
*/
#include<iostream>
#define ROW 5
#define COL 4
using namespace std;

class MyMatrix {
public:
int row;
int col;
MyMatrix() {
//Get the size of matrix
this->row = ROW;
this->col = COL;
}
//Display element of matrix
void show_data(int matrix[][COL]) {
for (int i = 0; i < this->row; ++i) {
for (int j = 0; j < this->col; ++j) {
cout << " " << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
void sparse_matrix(int matrix[][COL]) {
int counter = 0;
//Get number of non zero element
for (int i = 0; i < this->row; ++i) {
for (int j = 0; j < this->col; ++j) {
if (matrix[i][j] != 0) {
//When number is not zero
counter++;
}
}
}
if (counter > 1) {
int result[counter][3];
counter = 0;
for (int i = 0; i < this->row; ++i) {
for (int j = 0; j < this->col; ++j) {
if (matrix[i][j] != 0) {
//Assign row value
result[counter][0] = i;
//Assign column value
result[counter][1] = j;
//Assign value
result[counter][2] = matrix[i][j];
counter++;
}
}
}
cout << " row col Value \n";
//Print resultant matrix
for (int i = 0; i < counter; ++i) {
cout << "   " << result[i][0] << "  " << result[i][1] << "  " << result[i][2] << " \n";
}
}
}
};
int main() {
MyMatrix obj;
int matrix[][COL] = {
{ 0, 1, 0, 0 },
{ 0, 0, 2, 0 },
{ 0, 3, 0, 0 },
{ 1, 0, 5, 0 },
{ 0, 6, 0, 4 }
};

obj.show_data(matrix);
obj.sparse_matrix(matrix);
return 0;
}```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0  1  1
1  2  2
2  1  3
3  0  1
3  2  5
4  1  6
4  3  4``````
``````/*
Java Program
Sparse matrix representation
*/
public class MyMatrix {

public int row;
public int col;
public MyMatrix(int [][]matrix)
{
//Get the size of matrix
this.row=matrix.length;
this.col=matrix[0].length;
}
//Display element of matrix
public void show_data(int [][]matrix)
{
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
System.out.print("  "+matrix[i][j] );
}
System.out.print("\n");
}
System.out.print("\n");
}

public void sparse_matrix(int [][]matrix)
{
int counter=0;
//Get number of non zero element
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
if(matrix[i][j] != 0)
{
//When number is not zero
counter++;
}
}
}
if(counter>1)
{

//row column And value container
int [][]result= new int[counter][3];

counter=0;

for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
if(matrix[i][j]!=0)
{
//Assign row value
result[counter][0]=i;
//Assign column value
result[counter][1]=j;
//Assign value
result[counter][2]=matrix[i][j];

counter++;
}
}

}
System.out.print(" row col Value \n");
//Print resultant matrix
for (int i = 0; i < counter; ++i)
{

System.out.print("  "+result[i][0]+"   "+result[i][1]+"   "+result[i][2]+" \n");

}

}
}

public static void main(String[] args) {

//Define matrix
int [][]matrix = {
{ 0, 1, 0, 0 },
{ 0, 0, 2, 0 },
{ 0, 3, 0, 0 },
{ 1, 0, 5, 0 },
{ 0, 6, 0, 4 }
};

MyMatrix obj = new MyMatrix(matrix);
obj.show_data(matrix);
obj.sparse_matrix(matrix);

}
}```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0  1  1
1  2  2
2  1  3
3  0  1
3  2  5
4  1  6
4  3  4``````
``````/*
C# Program
Sparse matrix representation
*/
using System;
public class MyMatrix {

public int row;
public int col;
public MyMatrix(int[,] matrix) {
//Get the size of matrix
this.row = matrix.GetLength(0);
this.col = matrix.GetLength(1);
}
//Display element of matrix
public void show_data(int[,] matrix) {
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
Console.Write("  " + matrix[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}

public void sparse_matrix(int[,] matrix) {
int counter = 0;
//Get number of non zero element
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (matrix[i,j] != 0) {
//When number is not zero
counter++;
}
}
}
if (counter > 1) {

//row column And value container
int[,] result = new int[counter,3];

counter = 0;

for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (matrix[i,j] != 0) {
//Assign row value
result[counter,0] = i;
//Assign column value
result[counter,1] = j;
//Assign value
result[counter,2] = matrix[i,j];

counter++;
}
}

}
Console.Write(" row col Value \n");
//Print resultant matrix
for (int i = 0; i < counter; ++i) {

Console.Write("  " + result[i,0] + "   " + result[i,1] + "   " + result[i,2] + " \n");

}

}
}

public static void Main(String[] args) {

//Define matrix
int[,] matrix = {
{
0,
1,
0,
0
},
{
0,
0,
2,
0
},
{
0,
3,
0,
0
},
{
1,
0,
5,
0
},
{
0,
6,
0,
4
}
};

MyMatrix obj = new MyMatrix(matrix);
obj.show_data(matrix);
obj.sparse_matrix(matrix);

}
}```
```

#### Output

``````  0  1  0  0
0  0  2  0
0  3  0  0
1  0  5  0
0  6  0  4

row col Value
0   1   1
1   2   2
2   1   3
3   0   1
3   2   5
4   1   6
4   3   4``````
``````<?php
/*
Php Program
Sparse matrix representation
*/
class MyMatrix {
public \$row;
public \$col;

function __construct(\$matrix) {
//Get the size of matrix
\$this->row = count(\$matrix);
\$this->col = count(\$matrix[0]);
}

//Display element of matrix

public 	function show_data(\$matrix) {
for (\$i = 0; \$i < \$this->row; ++\$i) {
for (\$j = 0; \$j < \$this->col; ++\$j) {
echo(" ". \$matrix[\$i][\$j]);
}

echo("\n");
}

echo("\n");
}

public 	function sparse_matrix(\$matrix) {
\$counter = 0;
//Get number of non zero element

for (\$i = 0; \$i < \$this->row; ++\$i) {
for (\$j = 0; \$j < \$this->col; ++\$j) {
if (\$matrix[\$i][\$j] != 0) {
//When number is not zero
\$counter++;
}
}
}

if (\$counter > 1) {
//row column And value container
\$result = array_fill(0, \$counter, array_fill(0, 3, 0));
\$counter = 0;
for (\$i = 0; \$i < \$this->row; ++\$i) {
for (\$j = 0; \$j < \$this->col; ++\$j) {
if (\$matrix[\$i][\$j] != 0) {
//Assign row value
\$result[\$counter][0] = \$i;
//Assign column value
\$result[\$counter][1] = \$j;
//Assign value
\$result[\$counter][2] = \$matrix[\$i][\$j];
\$counter++;
}
}
}

echo(" row col Value \n");
//Print resultant matrix

for (\$i = 0; \$i < \$counter; ++\$i) {
echo("  ". \$result[\$i][0] ."  ". \$result[\$i][1] ."  ". \$result[\$i][2] ." \n");
}
}
}
}

function main() {
//Define matrix
\$matrix = array(array(0, 1, 0, 0), array(0, 0, 2, 0), array(0, 3, 0, 0), array(1, 0, 5, 0), array(0, 6, 0, 4));
\$obj = new MyMatrix(\$matrix);
\$obj->show_data(\$matrix);
\$obj->sparse_matrix(\$matrix);

}
main();```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0  1  1
1  2  2
2  1  3
3  0  1
3  2  5
4  1  6
4  3  4``````
``````/*
Node Js Program
Sparse matrix representation
*/
class MyMatrix {

constructor(matrix) {
//Get the size of matrix
this.row = matrix.length;
this.col = matrix[0].length;
}

//Display element of matrix
show_data(matrix) {
for (var i = 0; i < this.row; ++i) {
for (var j = 0; j < this.col; ++j) {
process.stdout.write(" " + matrix[i][j]);
}

process.stdout.write("\n");
}

process.stdout.write("\n");
}
sparse_matrix(matrix) {
var counter = 0;
//Get number of non zero element

for (var i = 0; i < this.row; ++i) {
for (var j = 0; j < this.col; ++j) {
if (matrix[i][j] != 0) {
//When number is not zero
counter++;
}
}
}

if (counter > 1) {
//row column And value container
var result = Array(counter).fill(0).map(() => new Array(3).fill(0));
counter = 0;
for (var i = 0; i < this.row; ++i) {
for (var j = 0; j < this.col; ++j) {
if (matrix[i][j] != 0) {
//Assign row value
result[counter][0] = i;
//Assign column value
result[counter][1] = j;
//Assign value
result[counter][2] = matrix[i][j];
counter++;
}
}
}

process.stdout.write(" row col Value \n");
//Print resultant matrix

for (var i = 0; i < counter; ++i) {
process.stdout.write("   " + result[i][0] + "  " + result[i][1] + "  " + result[i][2] + " \n");
}
}
}
}

function main(args) {
//Define matrix
var matrix = [
[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 3, 0, 0],
[1, 0, 5, 0],
[0, 6, 0, 4]
];
var obj = new MyMatrix(matrix);
obj.show_data(matrix);
obj.sparse_matrix(matrix);
}
main();```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0  1  1
1  2  2
2  1  3
3  0  1
3  2  5
4  1  6
4  3  4``````
``````# Python 3 Program
# Sparse matrix representation
class MyMatrix :

def __init__(self, matrix) :
# Get the size of matrix
self.row = len(matrix)
self.col = len(matrix[0])

# Display element of matrix
def show_data(self, matrix) :
i = 0
while (i < self.row) :
j = 0
while (j < self.col) :
print(" ", matrix[i][j], end= "")
j += 1

print("\n", end= "")
i += 1

print("\n", end= "")

def sparse_matrix(self, matrix) :
counter = 0
# Get number of non zero element
i = 0
while (i < self.row) :
j = 0
while (j < self.col) :
if (matrix[i][j] != 0) :
# When number is not zero
counter += 1

j += 1

i += 1

if (counter > 1) :
result = [
[0] * 3
for _ in range(counter)
]
counter = 0
i = 0
while (i < self.row) :
j = 0
while (j < self.col) :
if (matrix[i][j] != 0) :
# Assign row value
result[counter][0] = i
# Assign column value
result[counter][1] = j
# Assign value
result[counter][2] = matrix[i][j]
counter += 1

j += 1

i += 1

print(" row col Value \n", end= "")
# Print resultant matrix
i = 0
while (i < counter) :
print(" ", result[i][0] ," ", result[i][1] ," ", result[i][2] ," \n", end= "")
i += 1

def main() :
matrix = [
[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 3, 0, 0],
[1, 0, 5, 0],
[0, 6, 0, 4]
]
obj = MyMatrix(matrix)
obj.show_data(matrix)
obj.sparse_matrix(matrix)

if __name__ == "__main__":
main()```
```

#### Output

``````  0  1  0  0
0  0  2  0
0  3  0  0
1  0  5  0
0  6  0  4

row col Value
0   1   1
1   2   2
2   1   3
3   0   1
3   2   5
4   1   6
4   3   4  ``````
``````# Ruby Program
# Sparse matrix representation
class MyMatrix
# Define the accessor and reader of class MyMatrix
attr_accessor :row, :col
def initialize(matrix)
# Get the size of matrix
self.row = matrix.length
self.col = matrix[0].length
end
# Display element of matrix
def show_data(matrix)
i = 0
while (i < @row)
j = 0
while (j < @col)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
def sparse_matrix(matrix)
counter = 0
# Get number of non zero element
i = 0
while (i < @row)
j = 0
while (j < @col)
if (matrix[i][j] != 0)
# When number is not zero
counter += 1
end
j += 1
end
i += 1
end
if (counter > 1)
result = Array.new(counter) { Array.new(3, 0) }
counter = 0
i = 0
while (i < @row)
j = 0
while (j < @col)
if (matrix[i][j] != 0)
# Assign row value
result[counter][0] = i
# Assign column value
result[counter][1] = j
# Assign value
result[counter][2] = matrix[i][j]
counter += 1
end
j += 1
end
i += 1
end
print(" row col Value \n")
# Print resultant matrix
i = 0
while (i < counter)
print("  ", result[i][0] ,"  ", result[i][1] ,"  ", result[i][2] ," \n")
i += 1
end
end
end
end
def main()
matrix = [
[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 3, 0, 0],
[1, 0, 5, 0],
[0, 6, 0, 4]
]
obj = MyMatrix.new(matrix)
obj.show_data(matrix)
obj.sparse_matrix(matrix)
end

main()```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0  1  1
1  2  2
2  1  3
3  0  1
3  2  5
4  1  6
4  3  4
``````
``````/*
Scala Program
Sparse matrix representation
*/
class MyMatrix (var row: Int,var col: Int) {

def this(matrix: Array[Array[Int]]) {
//Get the size of matrix
this(matrix.length,matrix(0).length);
}
//Display element of matrix
def show_data(matrix: Array[Array[Int]]): Unit = {
var i: Int = 0;
while (i < this.row) {
var j: Int = 0;
while (j < this.col) {
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
def sparse_matrix(matrix: Array[Array[Int]]): Unit = {
var counter: Int = 0;

//Get number of non zero element
var i: Int = 0;
var j: Int = 0;
while (i < this.row) {
j = 0;
while (j < this.col) {
if (matrix(i)(j) != 0) {
//When number is not zero
counter += 1;
}
j += 1;
}
i += 1;
}
if (counter > 1) {
var result: Array[Array[Int]] = Array.fill[Int](counter, 3)(0);
counter = 0;
i = 0;
while (i < this.row) {
j = 0;
while (j < this.col) {
if (matrix(i)(j) != 0) {
//Assign row value
result(counter)(0) = i;

//Assign column value
result(counter)(1) = j;

//Assign value
result(counter)(2) = matrix(i)(j);
counter += 1;
}
j += 1;
}
i += 1;
}
print(" row col Value \n");

//Print resultant matrix
i = 0;
while (i < counter) {
print(" " + result(i)(0) + " " + result(i)(1) + " " + result(i)(2) + " \n");
i += 1;
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val matrix: Array[Array[Int]] = Array(
Array(0, 1, 0, 0),
Array(0, 0, 2, 0),
Array(0, 3, 0, 0),
Array(1, 0, 5, 0),
Array(0, 6, 0, 4));
val obj: MyMatrix = new MyMatrix(matrix);
obj.show_data(matrix);
obj.sparse_matrix(matrix);
}
}```
```

#### Output

`````` 0 1 0 0
0 0 2 0
0 3 0 0
1 0 5 0
0 6 0 4

row col Value
0 1 1
1 2 2
2 1 3
3 0 1
3 2 5
4 1 6
4 3 4``````
``````/*
Swift 4 Program
Sparse matrix representation
*/
class MyMatrix {
var  row: Int;
var  col: Int;
init(_ matrix: [
[Int]
]) {
//Get the size of matrix
self.row = matrix.count;
self.col = matrix[0].count;
}
//Display element of matrix
func show_data(_ matrix: [
[Int]
]) {
var i: Int = 0;
var j: Int = 0;
while (i < self.row) {
j = 0;
while (j < self.col) {
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
func sparse_matrix(_ matrix: [
[Int]
]) {
var counter: Int = 0;
//Get number of non zero element
var i: Int = 0;
var j: Int = 0;
while (i < self.row) {
j = 0;
while (j < self.col) {
if (matrix[i][j] != 0) {
//When number is not zero
counter += 1;
}
j += 1;
}
i += 1;
}
if (counter > 1) {
var result: [
[Int]
] = Array(repeating: Array(repeating: 0, count: 3), count: counter);
counter = 0;
i = 0;
while (i < self.row) {
j = 0;
while (j < self.col) {
if (matrix[i][j] != 0) {
//Assign row value
result[counter][0] = i;
//Assign column value
result[counter][1] = j;
//Assign value
result[counter][2] = matrix[i][j];
counter += 1;
}
j += 1;
}
i += 1;
}
print(" row col Value \n", terminator: "");
//Print resultant matrix
i = 0;
while (i < counter) {
print(" ", result[i][0] ," ", result[i][1] ," ", result[i][2] ," \n", terminator: "");
i += 1;
}
}
}
}
func main() {
let matrix: [
[Int]
] = [
[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 3, 0, 0],
[1, 0, 5, 0],
[0, 6, 0, 4]
];
let obj: MyMatrix = MyMatrix(matrix);
obj.show_data(matrix);
obj.sparse_matrix(matrix);
}
main();```
```

#### Output

``````  0  1  0  0
0  0  2  0
0  3  0  0
1  0  5  0
0  6  0  4

row col Value
0   1   1
1   2   2
2   1   3
3   0   1
3   2   5
4   1   6
4   3   4``````

## Time Complexity

1. The `show_data` function has a time complexity of O(ROW * COL), where ROW is the number of rows and COL is the number of columns in the matrix.
2. The `sparse_matrix` function iterates through the entire matrix to count the non-zero elements, which takes O(ROW * COL) time.
3. The second loop in the `sparse_matrix` function also iterates through the entire matrix, taking O(ROW * COL) time.
4. Overall, the time complexity of the given code is O(ROW * COL).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post