Java Program to Check if all rows of a matrix are circular rotations of each other

0 0 2 minutes read

Given a matrix of n*n size, the task is to find whether all rows are circular rotations of each other or not.

Examples:

Input: mat[][] = 1, 2, 3

3, 1, 2

2, 3, 1
Output: Yes, All rows are rotated permutation of each other.
Input: mat[3][3] = 1, 2, 3

3, 2, 1

1, 3, 2
Output: No, Explanation : As 3, 2, 1 is not a rotated or circular permutation of 1, 2, 3

The idea is based on the below article.
A Program to check if strings are rotations of each other or not

Steps :

Create a string of first row elements and concatenate the string with itself so that string search operations can be efficiently performed. Let this string be str_cat.
Traverse all remaining rows. For every row being traversed, create a string str_curr of current row elements. If str_curr is not a substring of str_cat, return false.
Return true.

Below is the implementation of the above steps.

Java

// Java program to check if all rows of a matrix
// are rotations of each other
class GFG
{
 
    static int MAX = 1000;
 
    // Returns true if all rows of mat[0..n-1][0..n-1]
    // are rotations of each other.
    static boolean isPermutedMatrix(int mat[][], int n)
    {
        // Creating a string that contains
        // elements of first row.
        String str_cat = "";
        for (int i = 0; i < n; i++)
        {
            str_cat = str_cat + "-" + String.valueOf(mat[0][i]);
        }
 
        // Concatenating the string with itself
        // so that substring search operations 
        // can be performed on this
        str_cat = str_cat + str_cat;
 
        // Start traversing remaining rows
        for (int i = 1; i < n; i++)
        {
            // Store the matrix into vector in the form
            // of strings
            String curr_str = "";
            for (int j = 0; j < n; j++)
            {
                curr_str = curr_str + "-" + String.valueOf(mat[i][j]);
            }
 
            // Check if the current string is present in
            // the concatenated string or not
            if (str_cat.contentEquals(curr_str))
            {
                return false;
            }
        }
 
        return true;
    }
 
    // Drivers code
    public static void main(String[] args)
    {
        int n = 4;
        int mat[][] = {{1, 2, 3, 4},
        {4, 1, 2, 3},
        {3, 4, 1, 2},
        {2, 3, 4, 1}
        };
        if (isPermutedMatrix(mat, n))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    }
}
 
/* This code contributed by PrinciRaj1992 */