Tag Archives: matrix

DeterminantOfMatrix


4. Determinant of a 2D matrix

Problem:

Given a 2D matrix, Determine it’s Determinant.

Solution:

This implementation is done using C#.NET. Rectangular Matrix is declared using int[,] syntax.

public static long EvaluateDeterminant(int[,] matrix)
{
long determinant = 0;

if (matrix == null || matrix.GetUpperBound(0) != matrix.GetUpperBound(1))
{
Console.WriteLine("Non-square matrix can't have a determinant");

return determinant;
}

int row_UB = matrix.GetUpperBound(0);

determinant = Determinant(matrix, row_UB + 1);

return determinant;
}

private static long Determinant(int[,] matrix, int size)
{
long determinant = 0;

if (size == 1) // 1x1 MAtrix
{
determinant = matrix[0, 0];
}
else if (size == 2) // 2x2 MAtrix
{
determinant = matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]; // can hash this multiplication
}
else
{
int multiplier = 1;

for (int i = 0; i < size; i++)
{
multiplier = (i % 2 == 0) ? 1 : -1;

determinant += multiplier * matrix[0, i] * Determinant(GetMinor(matrix, size, 0, i), size - 1);
}
}

return determinant;
}

/// <summary>
/// Gets the Minor of a Square Matrix
/// </summary>
/// <param name="matrix"></param>
/// <param name="size"></param>
/// <param name="rowIndex"></param>
/// <param name="colIndex"></param>
/// <returns></returns>
/// <remarks>
/// If function has to be Public, Certain checks on rowIndex, ColIndex should be made and size need not to be passed
/// </remarks>

private static int[,] GetMinor(int[,] matrix, int size, int rowIndex, int colIndex)
{
int minorSize = size - 1;
int[,] minor = new int[minorSize, minorSize];

for (int i = 0; i < rowIndex; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i, j] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i - 1, j] = matrix[i, j];
}
}

for (int i = 0; i < rowIndex; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i, j - 1] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i - 1, j - 1] = matrix[i, j];
}
}

return minor;
}

Advertisements

SpiralTraversalOfMatrix


1. Spiral Traversal of a 2D matrix

Problem:

Given a 2D matrix, traverse all it’s elements in a spiral form.
Referring the below matrix as an input (Red line shows a spiral traversal),

output should be: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Solution:

This implementation is done using C#.NET. Rectangular Matrix is declared using int[,] syntax.

public void DoSpiralTraversal(int[, ]rectArray) {
        if (rectArray != null && rectArray.Length > 0) {
            Console.WriteLine("Doing Spiral Traversal on a 2D array:");

            int noOfElementsTraversed = 0, row_LB = 0, row_UB = rectArray.GetUpperBound(0), col_LB = 0, col_UB =
                    rectArray.GetUpperBound(1), iter;

            while (true) {
                // Move downwards
                for (iter = row_LB; iter = rectArray.Length) {
                    break;
                }

                col_LB++;

                // Move Left to Right
                for (iter = col_LB; iter = rectArray.Length) {
                    break;
                }

                row_UB–-;

                // Move upwards
                for (iter = row_UB; iter >= row_LB; iter–)
                {
                    Console.Write(rectArray[iter, col_UB]+”“);

                    noOfElementsTraversed++;
                }

                if (noOfElementsTraversed >= rectArray.Length) {
                    break;
                }

                col_UB–-;

                // Move right to Left
                for (iter = col_UB; iter >= col_LB; iter–)
                {
                    Console.Write(rectArray[row_LB, iter]+”“);

                    noOfElementsTraversed++;
                }

                if (noOfElementsTraversed >= rectArray.Length) {
                    break;
                }
                
                row_LB++;
            }
        }
    }