carraysmatrixrandom-seedsymmetric

Is there a way to generate random square matrixes until there is one that is symmetric? (C)


What I need to do is internally create a random matrix of 3>=n>=8 rows and columns, the program should do so until it finds one that is diagonally symmetric, and then print it, the random numbers must be from 0 to 7, and there should be a functionality in which changing a variable form true to false you could choose to print or not the matrixes that were not symmetric. Ive been able to create random matrixes until it is symmetric, but only for 3x3, any number above will leave my pc perpetually thinking, im sure there must be a more efficient way to do this but im not very good at c heres the code ive got:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int simetria (int n, int matriz[n][n], int transpuesta[n][n]);

int main(void)
{
    setbuf(stdout, NULL);
    srand(time(0));

    int n, r, c, symmetry = 0;

    scanf("%i", &n);

    int matriz [n][n],transpuesta[n][n];

    int contador = ((n*n)-n);

    while(symmetry != contador)
    {
        for(r = 0; r<n; r++){
            for(c = 0; c<n; c++){
                matriz [r][c] = (rand() %8);
            }
        }
        for(r = 0; r<n; r++){
            for(c = 0; c<n; c++){
                transpuesta[c][r] = matriz [r][c];
            }
        }
        symmetry = simetria(n, matriz, transpuesta);

    }
    printf("\n");
    for(r = 0; r<n; r++){
                for(c = 0; c<n; c++){
                    printf("%i \t", matriz [r][c]);
                }
                printf("\n\n");
            }
    return 0;
}

int simetria (int n, int matriz[n][n], int transpuesta[n][n])
{
    int r, c;
    int symmetry = 0;
    for(r = 0; r<n; r++){
                for(c = 0; c<n; c++){
                    if (r!=c){
                        if (transpuesta[r][c] == matriz [r][c]){
                            symmetry++;
                        }
                        else{
                            symmetry = 0;
                            return symmetry;
                        }
                    }
                }
            }
    return symmetry;
}


Solution

  • Converting my comments into an answer.

    For determining whether the matrix is symmetric about the leading diagonal, you just need to check that matrix[r][c] == matrix[c][r]. For efficiency, you should ensure that you don't check the diagonal and don't check anything twice. There's no need to create the transpose as in the question. This will speed the comparison up. Ultimately, though, randomly generating a symmetric matrix is pretty improbable as the matrices get larger.

    If you have a 2x2 matrix with each cell containing integer values in the range 0..7, you have a 1 in 8 chance of getting a matrix that's symmetric about the leading diagonal. If you have a 3x3 matrix, the probability drops to 1 in 8³ or 1:512 because there are 3 cells above the diagonal, and there's a 1 in 8 chance that each of the corresponding cells below the diagonal contains the same value. With a 4x4 matrix, that drops to 1 in 8⁶ or 1:4096; with 5x5, the probability drops to 1 in 8¹⁰ or 1:32767, and so on. For an NxN matrix, the probability is 8 raised to the power of N(N-1)/2.

    I haven't thought of a way of only comparing half of the triangle.

    for (int r = 0; r < n; r++)
    {
        for (int c = r + 1; c < n; c++)
        {
            if (matrix[r][c] != matrix[c][r])
            {
                …asymmetric…
            }
        }
    }
    

    If this is in a boolean function, you can use return false; on detecting asymmetry, and return true; if the loops complete. That starts by comparing matrix[0][1] with matrix[1][0].

    Note that if the goal is to generate a symmetric but random matrix (with each cell containing integer values in the range 0..7, you could use similar loops (but with c = r rather than c = r + 1) and use matrix[r][c] = matrix[c][r] = rand() % 8;. The change in the inner loop start condition assigns to the leading diagonal too. Or you could avoid assigning twice to the elements on the leading diagonal with:

    for (int r = 0; r < n; r++)
    {
        matrix[r][r] = rand() % 8;
        for (int c = r + 1; c < n; c++)
             matrix[r][c] = matrix[c][r] = rand() % 8;
    }