Check if all rows of a matrix are circular rotations of each other
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 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 above steps.
C++
// C++ program to check if all rows of a matrix // are rotations of each other #include <bits/stdc++.h> using namespace std; const int MAX = 1000; // Returns true if all rows of mat[0..n-1][0..n-1] // are rotations of each other. bool isPermutedMatrix( int mat[MAX][MAX], 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 + "-" + to_string(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 + "-" + to_string(mat[i][j]); // Check if the current string is present in // the concatenated string or not if (str_cat.find(curr_str) == string::npos) return false ; } return true ; } // Drivers code int main() { int n = 4 ; int mat[MAX][MAX] = {{1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1} }; isPermutedMatrix(mat, n)? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check if all rows of a matrix // are rotations of each other import java.io.*; 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 */ |
Python3
# Python3 program to check if all rows # of a matrix are rotations of each other MAX = 1000 # Returns true if all rows of mat[0..n-1][0..n-1] # are rotations of each other. def isPermutedMatrix(mat, n) : # Creating a string that contains # elements of first row. str_cat = "" for i in range (n) : str_cat = str_cat + "-" + str (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 i in range ( 1 , n) : # Store the matrix into vector # in the form of strings curr_str = "" for j in range (n) : curr_str = curr_str + "-" + str (mat[i][j]) # Check if the current string is present # in the concatenated string or not if (str_cat.find(curr_str)) : return True return False # Driver code if __name__ = = "__main__" : n = 4 mat = [[ 1 , 2 , 3 , 4 ], [ 4 , 1 , 2 , 3 ], [ 3 , 4 , 1 , 2 ], [ 2 , 3 , 4 , 1 ]] if (isPermutedMatrix(mat, n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Ryuga |
C#
// C# program to check if all rows of a matrix // are rotations of each other using System; 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 bool 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 + "-" + mat[0,i].ToString(); } // 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 + "-" + mat[i,j].ToString(); } // Check if the current string is present in // the concatenated string or not if (str_cat.Equals(curr_str)) { return false ; } } return true ; } // Driver code static void Main() { 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)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } /* This code contributed by mits */ |
PHP
<?php // PHP program to check if all rows of a // matrix are rotations of each other $MAX = 1000; // Returns true if all rows of mat[0..n-1][0..n-1] // are rotations of each other. function isPermutedMatrix( & $mat , $n ) { // Creating a string that contains // elements of first row. $str_cat = "" ; for ( $i = 0 ; $i < $n ; $i ++) $str_cat = $str_cat . "-" . strval ( $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 ( $i = 1; $i < $n ; $i ++) { // Store the matrix into vector // in the form of strings $curr_str = "" ; for ( $j = 0 ; $j < $n ; $j ++) $curr_str = $curr_str . "-" . strval ( $mat [ $i ][ $j ]); // Check if the current string is present // in the concatenated string or not if ( strpos ( $str_cat , $curr_str )) return true; } return false; } // Driver Code $n = 4; $mat = array ( array (1, 2, 3, 4), array (4, 1, 2, 3), array (3, 4, 1, 2), array (2, 3, 4, 1)); if (isPermutedMatrix( $mat , $n )) echo "Yes" ; else echo "No" ; // This code is contributed by ita_c ?> |
Javascript
<script> // Javascript program to check if all rows of a matrix // are rotations of each other // Returns true if all rows of mat[0..n-1][0..n-1] // are rotations of each other. function isPermutedMatrix(mat, n) { // Creating a string that contains // elements of first row. let str_cat = "" ; for (let i = 0; i < n; i++) { str_cat = str_cat + "-" + (mat[0][i]).toString(); } // 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 (let i = 1; i < n; i++) { // Store the matrix into vector in the form // of strings let curr_str = "" ; for (let j = 0; j < n; j++) { curr_str = curr_str + "-" + (mat[i][j]).toString(); } // Check if the current string is present in // the concatenated string or not if (str_cat.includes(curr_str)) { return true ; } } return false ; } // Drivers code let n = 4; let mat = [ [ 1, 2, 3, 4 ], [ 4, 1, 2, 3 ], [ 3, 4, 1, 2 ], [ 2, 3, 4, 1 ] ]; if (isPermutedMatrix(mat, n)) document.write( "Yes" ) else document.write( "No" ) // This code is contributed by rag2127 </script> |
Output
Yes
Time complexity: O(n3)
Auxiliary Space: O(n), since n extra space has been taken.
Contact Us