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

Given a matrix, write a function to find whether all rows are circular rotations of each other or not

Example

INPUT
s[3][3] =  a b c
        c b a
        a c b

OUTPUT
FALSE

As we can see in second row(ie, c b a) is not a rotated or circular permutation of  a b c

Algorithm

1. Create a string with first row elements and concatenate the string with itself.

2. Now, traverse through all the remaining rows, check if the current row string is a substring of concatenated string or not.

3. If yes, return TRUE

C++ Program

#include <bits/stdc++.h>
#include <string>
#include <sstream>
using namespace std;
#define n 3
 
//checks whether all row are rotations of each other or not
bool arePermutations(int s[n][n])
{

    ostringstream os ;
    //To concatenate strings
    string c = "";
    for (int i = 0 ; i < n ; i++)
    {
        os<<s[0][i];
        c = c + "-" + os.str();
        os.str("");
        os.clear();

    }
 
    //concatenate strings
    c = c + c;

    // Start traversing remaining rows
    for (int i=1; i<n; i++)
    {
        // Store the matrix into vector in the form
        // of strings
        string temp = "";
        for (int j = 0 ; j < n ; j++)
        {
            os<<s[i][j];
            temp = temp + "-" + os.str();
            //clearing data in osstream
            os.str("");
            os.clear();
        }
 
        // Check if the current string is present in
        // the concatenated string or not
        if (c.find(temp) == string::npos)
            return false;
    }
 
    return true;
}
 

int main()
{
    int s[n][n] = {{1, 2, 3},
        {3, 1, 2},
        {2, 3, 1}
    };
    if(arePermutations(s))
    { 
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top