Find all permuted rows of a given row in a matrix

Problem Statement

Find all permuted rows of a given row in a matrix states that you are given a matrix of size m*n and a matrix row number says ‘row’. The problem statement asks to find out all the possible rows which are permutation to the given row. This is also said that all the elements in each row are different.

Example

r = 2

mat[][] = {{6, 5, 9, 2},

{1, 6, 9, 3},

{6, 5, 9, 2},

{6, 2, 5, 9}}

0, 3

Explanation: The given row is 2 which contains 6, 5, 2, and 9. Having this only 0^th and 3^rd row are the permutations to the given row number.

Algorithm to find all permuted rows of a given row in a matrix

1. Create a set.
2. Insert the given row elements into the set.
3. Traverse the matrix, and ignore the given row number while traversing.
    1. Check if the set doesn’t contain each value of the traversed row if it doesn’t contain then break the loop and proceed for next row.
    2. Else print the value of i, i.e, the current row number.

Explanation

You are given a matrix of say m rows and n columns and the row number, the row number given is 0 index-based. We have asked to find out if the rows in the matrix other than the given row which are permutations of a given row. Permutation here means we have to find out if the elements in the given list are the same in how many lists, or having the same lists or not. We need to print that row number. For this, we are going to use Set.

First, we need to insert all the values of the given row number into the set. This is treated as a reference in our later operations. We have stored this row into the set. Because we are going to compare this with all other rows except itself.

Traverse the matrix now with the help of the nested loop. We will pick each row and with that row, we will traverse its all elements. We have mentioned a case if the row we will be picking up is the same as the given row. Then ignore it and move for the next row if present. This is because we would not be adding one more value to the answer. And it shows one more row extra which is row itself. That wouldn’t be acceptable. Now when we traverse the elements of the picked row, we will check if the set contains the set element as we are picking up. If the loop doesn’t break at all and comes out this means, the given row is permutated and we are going to print that row number. Proceed further to find out more rows are permutated or not.

Code

C++ code to find all permuted rows of a given row in a matrix

#include<iostream>
#include<unordered_set>

#define MAX 100

using namespace std;

void checkPermutatedRow(int matrix[][MAX], int m, int n, int r)
{
    unordered_set<int> s;

    for (int j=0; j<n; j++)
        s.insert(matrix[r][j]);

    for (int i=0; i<m; i++)
    {
        if (i==r)
            continue;

        int j;
        for (j=0; j<n; j++)
            if (s.find(matrix[i][j]) == s.end())
                break;
        if (j != n)
            continue;

        cout << i << ", ";
    }
}
int main()
{
    int row = 4, col = 4,r = 2;
    int matrix[][MAX] = {{6, 5, 9, 2},
        {1, 6, 9, 3},
        {6, 5, 9, 2},
        {6, 2, 5, 9}
    };
    checkPermutatedRow(matrix, row, col, r);
    return 0;
}

0, 3,

Java Code to find all permuted rows of a given row in a matrix

import java.util.LinkedHashSet;

class Permutations
{
    private static int MAX = 100;

    public static void checkPermutatedRow(int matrix[][], int m, int n, int r)
    {
        LinkedHashSet<Integer> SET = new LinkedHashSet<>();

        for (int j = 0; j < n; j++)
            SET.add(matrix[r][j]);

        for (int i = 0; i < m; i++)
        {
            if (i == r)
                continue;

            int j;
            for (j = 0; j < n; j++)
                if (!SET.contains(matrix[i][j]))
                    break;
            if (j != n)
                continue;

            System.out.print(i+", ");
        }
    }
    public static void main(String[] args)
    {
        int  row= 4, col = 4,r = 2;
        int matrix[][] = {{6, 5, 9, 2},
            {1, 6, 9, 3},
            {6, 5, 9, 2},
            {6, 2, 5, 9}
        };
        checkPermutatedRow(matrix, row, col, r);
    }
}

0, 3,

Complexity Analysis

Time Complexity

O(m*n) where “m” and “n” is the number of rows and columns in the matrix. Since we are simply traversing the matrix and suing HashSet provides to perform operations in O(1).

Space Complexity

O(N) where “N” is the number of elements in the matrix. Since we just stored the input, thus the algorithm has linear space complexity.