Рубрики

Проверьте, все ли строки матрицы являются круговыми вращениями друг друга

Учитывая матрицу размера n * n, задача состоит в том, чтобы определить, все ли строки имеют круговые вращения друг относительно друга или нет.
Примеры:

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

Идея основана на статье ниже.
Программа для проверки, являются ли строки вращением друг друга или нет

Шаги:

  1. Создайте строку из элементов первой строки и объедините строку с собой, чтобы операции поиска строки могли быть эффективно выполнены. Пусть эта строка будет str_cat.
  2. Пройдите через все оставшиеся ряды. Для каждой пройденной строки создайте строку str_curr из текущих элементов строки. Если str_curr не является подстрокой str_cat, вернуть false.
  3. Верните истину.

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ программа для проверки, все ли строки матрицы
// это вращения друг друга
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000;

  
// Возвращает true, если все строки mat [0..n-1] [0..n-1]
// это вращения друг друга.

bool isPermutedMatrix( int mat[MAX][MAX], int n)

{

    // Создание строки, содержащей элементы первого

    // строка.

    string str_cat = "";

    for (int i = 0 ; i < n ; i++)

        str_cat = str_cat + "-" + to_string(mat[0][i]);

  

    // Объединяем строку с собой так, чтобы

    // операции поиска подстроки могут быть выполнены на

    // это

    str_cat = str_cat + str_cat;

  

    // Начать обход оставшихся строк

    for (int i=1; i<n; i++)

    {

        // Сохраняем матрицу в вектор в виде

        // строк

        string curr_str = "";

        for (int j = 0 ; j < n ; j++)

            curr_str = curr_str + "-" + to_string(mat[i][j]);

  

        // Проверяем, присутствует ли текущая строка в

        // конкатенированная строка или нет

        if (str_cat.find(curr_str) == string::npos)

            return false;

    }

  

    return true;

}

  
// Код драйвера

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-программа для проверки, все ли строки матрицы
// это вращения друг друга

class GFG 

{

  

    static int MAX = 1000;

  

    // Возвращает true, если все строки mat [0..n-1] [0..n-1]

    // это вращения друг друга.

    static boolean isPermutedMatrix(int mat[][], int n) 

    {

        // Создание строки, содержащей

        // элементы первого ряда.

        String str_cat = "";

        for (int i = 0; i < n; i++) 

        {

            str_cat = str_cat + "-" + String.valueOf(mat[0][i]);

        }

  

        // Конкатенация строки с самой собой

        // чтобы операции поиска подстроки

        // можно выполнить на этом

        str_cat = str_cat + str_cat;

  

        // Начать обход оставшихся строк

        for (int i = 1; i < n; i++)

        {

            // Сохраняем матрицу в вектор в виде

            // строк

            String curr_str = "";

            for (int j = 0; j < n; j++) 

            {

                curr_str = curr_str + "-" + String.valueOf(mat[i][j]);

            }

  

            // Проверяем, присутствует ли текущая строка в

            // конкатенированная строка или нет

            if (str_cat.contentEquals(curr_str)) 

            {

                return false;

            }

        }

  

        return true;

    }

  

    // Код драйвера

    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");

        }

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

python3

# Python3 программа для проверки, все ли строки
# матрицы - это вращения друг друга

  

MAX = 1000

  
# Возвращает true, если все строки матрицы [0..n-1] [0..n-1]
# являются вращениями друг друга.

def isPermutedMatrix(mat, n) :

      

    # Создание строки, содержащей

    # элементы первого ряда.

    str_cat = ""

    for i in range(n) :

        str_cat = str_cat + "-" + str(mat[0][i])

  

    # Конкатенация строки с самой собой

    # так что подстрока поисковых операций

    # можно выполнить на этом

    str_cat = str_cat + str_cat

  

    # Начать обход оставшихся строк

    for i in range(1, n) :

          

        # Сохранить матрицу в вектор

        # в виде строк

        curr_str = ""

          

        for j in range(n) :

            curr_str = curr_str + "-" + str(mat[i][j])

  

        # Проверьте, присутствует ли текущая строка

        # в объединенной строке или нет

        if (str_cat.find(curr_str)) : 

            return True

              

    return False

  
# Код драйвера

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")

          
# Этот код предоставлен Ryuga

C #

// C # программа для проверки, все ли строки матрицы
// это вращения друг друга

using System;

  

class GFG 

{

  

    // static int MAX = 1000;

  

    // Возвращает true, если все строки mat [0..n-1,0..n-1]

    // это вращения друг друга.

    static bool isPermutedMatrix(int [,]mat, int n) 

    {

        // Создание строки, содержащей

        // элементы первого ряда.

        string str_cat = "";

        for (int i = 0; i < n; i++) 

        {

            str_cat = str_cat + "-" + mat[0,i].ToString();

        }

  

        // Конкатенация строки с самой собой

        // чтобы операции поиска подстроки

        // можно выполнить на этом

        str_cat = str_cat + str_cat;

  

        // Начать обход оставшихся строк

        for (int i = 1; i < n; i++)

        {

            // Сохраняем матрицу в вектор в виде

            // строк

            string curr_str = "";

            for (int j = 0; j < n; j++) 

            {

                curr_str = curr_str + "-" + mat[i,j].ToString();

            }

  

            // Проверяем, присутствует ли текущая строка в

            // конкатенированная строка или нет

            if (str_cat.Equals(curr_str)) 

            {

                return false;

            }

        }

  

        return true;

    }

  

    // Код драйвера

    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");

        }

    }

}

  
/ * Этот код предоставлен mits * /

PHP

<?php 
// PHP-программа для проверки, все ли строки
// матрица - это вращения друг друга

$MAX = 1000;

  
// Возвращает true, если все строки mat [0..n-1] [0..n-1]
// это вращения друг друга.

function isPermutedMatrix( &$mat, $n)

{

    // Создание строки, содержащей

    // элементы первого ряда.

    $str_cat = "";

    for ($i = 0 ; $i < $n ; $i++)

        $str_cat = $str_cat . "-"

                   strval($mat[0][$i]);

  

    // Конкатенация строки с самой собой

    // чтобы операции поиска подстроки

    // можно выполнить на этом

    $str_cat = $str_cat . $str_cat;

  

    // Начать обход оставшихся строк

    for ($i = 1; $i < $n; $i++)

    {

        // Сохраняем матрицу в вектор

        // в виде строк

        $curr_str = "";

        for ($j = 0 ; $j < $n ; $j++)

            $curr_str = $curr_str . "-" .

                        strval($mat[$i][$j]);

  

        // Проверяем, присутствует ли текущая строка

        // в объединенной строке или нет

        if (strpos($str_cat, $curr_str))

            return true;

    }

  

    return false;

}

  
// Код драйвера

$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";

  
// Этот код предоставлен ita_c
?>


Выход:

Yes

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, все ли строки матрицы являются круговыми вращениями друг друга

0.00 (0%) 0 votes