// A sparse matrix is a matrix in which the majority of elements are zero.
// To compact a sparse matrix, use a method to store only the non‑zero
// entries using a triplet representation (row, column, value).
// This reduces memory usage.
object CompactSparseMatrix {
// Convert a sparse matrix into compact (triplet) form
def compactMatrix(matrix: Vector[Vector[Int]]): Vector[Vector[Int]] = {
val rows = matrix.length
val cols = matrix(0).length
// Count non-zero elements
val count =
(for {
i <- 0 until rows
j <- 0 until cols
if matrix(i)(j) != 0
} yield 1).sum
// Compact matrix has 3 rows: row index, col index, value
val compact = Array.fill(3, count)(0)
var k = 0
// Fill compact matrix
for {
i <- 0 until rows
j <- 0 until cols
if matrix(i)(j) != 0
} {
compact(0)(k) = i // row
compact(1)(k) = j // column
compact(2)(k) = matrix(i)(j) // value
k += 1
}
compact.map(_.toVector).toVector
}
def main(args: Array[String]): Unit = {
val matrix = Vector(
Vector(0, 0, 3, 0, 8, 0, 0, 0, 0),
Vector(0, 0, 5, 7, 0, 0, 1, 0, 0),
Vector(0, 0, 0, 0, 0, 0, 0, 0, 0),
Vector(0, 2, 6, 0, 0, 4, 0, 0, 0),
Vector(0, 0, 0, 0, 9, 0, 0, 0, 0)
)
val compact = compactMatrix(matrix)
println("Compact matrix:")
for (i <- 0 until 3) {
println(compact(i).mkString(" "))
}
}
}
/*
run:
Compact matrix:
0 0 1 1 1 3 3 3 4
2 4 2 3 6 1 2 5 4
3 8 5 7 1 2 6 4 9
*/
