How to identify permutations in matrix columns in C++

Question

In college, I need to do an exercise --- the statement is low --- in which they test with matrices of different dimensions, that is, I need to do a program that reads matrix and writes the matrix that the test program gives input. I made a code in python, but I couldn’t translate it to C++.

Follow the code that reads and writes in python:

    quantidade_linhas = 0
def ler_matriz():
    m = []
    ler_linha = input()
    global quantidade_linhas
    while ler_linha:
        m.append([int(i) for i in ler_linha.split(' ') if i])
        ler_linha = input()
        quantidade_linhas += 1
    return m

Here’s what I tried to do in C++:

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;

vector<vector<int> > leiaMatriz(int L, int C) {
  vector<vector<int> > m;
  for (int i = 0; i < L; i++) {
    vector<int> v1;
    for (int j = 0; j < C; j++) {
      int aux;
      cin >> aux;
      v1.push_back(aux); 
    }
    m.push_back(v1); 
  }  
  return m;
}
void escrevaMatriz(vector<vector<int> > m) {
  for (int i = 0; i < m.size(); i++) {
    for (int j = 0; j < m[0].size(); j++) {
       cout << m[i][j] << "\t ";
    }
    cout << "\n";
  }
}

I will also leave an example of exercise that ask for this uniqueness:

Could give me a light?

Answer 1

C++ and C does not have this notion of matrices as in FORTRAN. There is only vector, and a matrix is a vector vector, or a vector vector vector and so on. In your case dared for example vector<vector<int>>

An array is just an address, given by name, and dimensions. Note that you can write

    using Matriz = vector<vector<int>>;
    vector<vector<int>> teste;
    Matriz outra;

and testing and other will be vector vectors of int

Back on the show

To know whether or not the elements of a vector are permutation of the values of another vector in general, a bit vector is used, with one bit for each element, to mark the elements it has already found, and in a loop it searches all elements of the original vector. And it marks in the bit vector, since they can have repeated values, as in the case of your example. If you find all then you have clear a permutation.

As in your case the values are already in a read matrix it may not make sense to extract the vectors corresponding to the even columns to see later if they are all permutations, as the statement asks.

C++ allocates vectors per line, so considering their example matrix

    int const M[6][4] =
    {
        { 8, 3, 7, 1 },
        { 5, 8, 8, 8 },
        { 7, 1, 6, 1 },
        { 8, 6, 8, 7 },
        { 6, 7, 6, 1 },
        { 6, 1, 5, 1 }
    };

these values will be in memory so

         8, 3, 7, 1, 5, 8, 8, 8, 7, 1, 6, 1, ...

So the elements of a certain column are at a fixed distance from each other, and that distance is the number of columns. And the elements of a line are aligned one after the other.

It may be advantage then to use the matrix simply as int* and move the dimensions to a function that checks the permutation without extract the columns, without create the bit array and without touch the original matrix to mark the found elements. Something like

int cpp_matriz (const int A, const int B, int* const M, int l, int c);

Where

• A and B are the columns,
• M is the matrix
• l and c are the dimensions

and returns 1 if A and B are permutations of the same elements

I’ll show you an example in C++, which compiles in C as well, and does this. There’s not much advantage to using vector or classes for such a case, since it is only memory manipulation.

An example in C++

This example compiles in C as well. I did not find relevant the difference here because the idea is the same. And I did not see advantage in using STL.

Example output

        matriz exemplo 6x4

        8    3    7    1
        5    8    8    8
        7    1    6    1
        8    6    8    7
        6    7    6    1
        6    1    5    1

original    8    5    7    8    6    6
alvo        8    5    7    8    6    6
colunas (0,0) = permutacao

original    8    5    7    8    6    6
alvo        3    8    1    6    7    1
colunas (1,0) = NAO permutacao

original    8    5    7    8    6    6
alvo        7    8    6    8    6    5
colunas (2,0) = permutacao

original    8    5    7    8    6    6
alvo        1    8    1    7    1    1
colunas (3,0) = NAO permutacao

the algorithm

The program merely replicates what would be done with pen and paper. comparing the values of columns A and B using an index vector that shows the elements not yet used in the other column, and uses this vector to guide comparisons. At the end it must be empty.

Here is the relevant code

int cpp_matriz(const int A, const int B, int* const M, int l, int c)
{
    // prepara ix[], vetor de indices
    int* ix = (int*)malloc( (1 + l) * sizeof(int) );
    for (int i = 0; i < l; i += 1) ix[1 + i] = i;
    ix[0] = l;
    // procura todos de A em B
    for (int li = 0, fim = l*c; li < fim; li += c)
    {   // usa so os que sobraram de B, que estao em ix[]
        for (int j = 1; j <= ix[0]; j += 1)
        {
            if ( *(M + A + li) == *(M + B + ix[j] * c))
            {   // achou esse
                // se nao for o ultimo inverte
                if (j != ix[0]) ix[j] = ix[ix[0]];
                ix[0] -= 1; // um a menos
                break;       // esse tinha
            };  // if()
        }; // for(j)
    }; // for(li)
    int res = (ix[0] == 0);  // se nao sobrou = permutacao
    free(ix);
    return res;
};  // cpp_matriz()

The summary of the summary

            if ( *(M + A + li) == *(M + B + ix[j] * c))

This is the comparison that solves the problem. A and B are the columns and M the matrix with li lines and c columns. And the vector ix brings the elements not yet used

The complete code

#include <cstdio>
#include <cstdlib>
using namespace std;

int cpp_matriz (const int A, const int B, int* const M, int l, int c);
int mostra_coluna(int const coluna, int* const M, int l, int c, const char* tit);
int mostra_matriz(
    int* const M, int const l, int const, char const* tit);


int main(void)
{
    int       res     = 0;
    int const M[6][4] =
    {
        { 8, 3, 7, 1 },
        { 5, 8, 8, 8 },
        { 7, 1, 6, 1 },
        { 8, 6, 8, 7 },
        { 6, 7, 6, 1 },
        { 6, 1, 5, 1 }
    };  //  permutacao exemplo

    mostra_matriz((int* const)M, 6, 4, "\n\tmatriz exemplo 6x4\n");
    int base = 0;  // compara com todas as outras
    for (int alvo = 0; alvo < 4; alvo += 1)
    {
        mostra_coluna(base, (int* const)M, 6, 4, "\noriginal");
        mostra_coluna(alvo, (int* const)M, 6, 4, "alvo    ");
        res = cpp_matriz(base, alvo, (int* const)M, 6, 4);
        if (res)
            printf("colunas (%d,%d) = permutacao\n", alvo, base);
        else
            printf("colunas (%d,%d) = NAO permutacao\n", alvo, base);
    };  // for()
    return 0;
}


// retorna 1 se colunas A e B em M[l][c] forem permutacoes
int cpp_matriz(const int A, const int B, int* const M, int l, int c)
{
    // prepara ix[], vetor de indices
    int* ix = (int*)malloc( (1 + l) * sizeof(int) );
    for (int i = 0; i < l; i += 1) ix[1 + i] = i;
    ix[0] = l;
    // procura todos de A em B
    for (int li = 0, fim = l*c; li < fim; li += c)
    {   // usa so os que sobraram de B, que estao em ix[]
        for (int j = 1; j <= ix[0]; j += 1)
        {
            if ( *(M + A + li) == *(M + B + ix[j] * c))
            {   // achou esse
                // se nao for o ultimo inverte
                if (j != ix[0]) ix[j] = ix[ix[0]];
                ix[0] -= 1; // um a menos
                break;       // esse tinha
            };  // if()
        }; // for(j)
    }; // for(li)
    int res = (ix[0] == 0);  // se nao sobrou = permutacao
    free(ix);
    return res;
};  // cpp_matriz()


int mostra_coluna(
    int const coluna, int* const M, int l, int c, const char* tit)
{  // mostra a coluna 'coluna'
    if (tit != NULL)
        printf("%s", tit);
    else
        printf("coluna %d: ", coluna);
    for (int j = 0, fim = l * c; j < fim; j += c)
        printf("%5d", *(M + coluna + j));
    printf("\n");
    return 0;
}


int mostra_matriz(int* const M, int l, int c, char const* tit)
{
    if (tit != NULL) printf("%s\n", tit);
    for (int i = 0; i < l; i += 1)
    {
        printf("    "); // margem esquerda
        for (int j = 0; j < c; j += 1)
        {
            printf("%5d", *(M + (c * i) + j));
        }
        printf("\n");
    }
    return 0;
}
/*
https//pt.stackoverflow.com/questions/519189/
como-fazer-um-m%c3%a9todo-de-leitura-e-escrita-de-matriz-em-c
*/```