Encuentre una array simétrica de orden N que contenga números enteros de 0 a N-1 y la diagonal principal debe contener solo 0

Posted on by Rudeus Greyrat

Dado un número entero N . La tarea es generar una array simétrica de orden N*N que tenga las siguientes propiedades. 
 

  1. La diagonal principal debe contener solo 0
  2. La array debe contener elementos de 0 a N-1 únicamente.

Ejemplos: 
 

Entrada: N = 4 
Salida: 
0 2 3 1 
2 0 1 3 
3 1 0 
2 1 3 2 0
Entrada: N = 5 
Salida: 
0 2 3 4 1 
2 0 4 1 3 3 
4 0 2 1 4 
1 2 0 3 
1 3 1 3 0 
 

Enfoque: dado que la array requerida tiene que ser una array cuadrada, podemos generar una array simétrica que contenga un elemento de 1 a n-1, excluyendo 0. Trataremos el caso de 0 más adelante. 
Tomemos por ejemplo cuando N = 4: 
Primero generamos una array simétrica, y se puede hacer fácilmente llenando cada fila desde 1 hasta n-1 en orden cíclico, es decir, llenando la primera fila por 1 2 3, y haciendo esto para todos filas subsiguientes en orden cíclico. 
 

Entonces, la array final será, 
1 2 3 
2 3 
1 3 1 2 
 

Ahora, hemos generado una array simétrica que contiene elementos de 1 a n. Discutamos el caso 0. Tomaremos el beneficio de que la array anterior es simétrica, agregaremos una columna de 0 y filas de 0 como esta, 
 

1 2 3 0 
2 3 1 0 3 
1 2 
0 0 0 0 0 
 

Ahora, tenemos que poner todos los 0 en diagonal. Para esto, comenzaremos con la primera fila hasta la última fila 1 e intercambiaremos todos los 0 con el número que está allí en cada fila y también haremos un cambio en la última fila como este: 
 

Para la fila 1, intercambiamos 0 y 1 y también colocamos el primer elemento de la última fila con el número que intercambiamos, es decir, 1. 
0 2 3 1 
2 3 1 0 
3 1 2 0 
1 0 0 0
Para la fila 2, intercambiamos 0 y 3, y haga que el segundo elemento de la última fila también sea 3. 
0 2 3 1 
2 0 1 3 
3 1 2 0 
1 3 0 0 
y así sucesivamente… 
La array final generada será la array requerida. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to generate the required matrix
void solve(long long n)
{
    long long initial_array[n - 1][n - 1], final_array[n][n];
 
    for (long long i = 0; i < n - 1; ++i)
        initial_array[0][i] = i + 1;
 
    // Form cyclic array of elements 1 to n-1
    for (long long i = 1; i < n - 1; ++i)
        for (long long j = 0; j < n - 1; ++j)
            initial_array[i][j]
                = initial_array[i - 1][(j + 1) % (n - 1)];
 
    // Store initial array into final array
    for (long long i = 0; i < n - 1; ++i)
        for (long long j = 0; j < n - 1; ++j)
            final_array[i][j] = initial_array[i][j];
 
    // Fill the last row and column with 0's
    for (long long i = 0; i < n; ++i)
        final_array[i][n - 1] = final_array[n - 1][i] = 0;
 
    for (long long i = 0; i < n; ++i) {
        long long t0 = final_array[i][i];
        long long t1 = final_array[i][n - 1];
 
        // Swap 0 and the number present
        // at the current indexed row
        swap(final_array[i][i], final_array[i][n - 1]);
 
        // Also make changes in the last row
        // with the number we swapped
        final_array[n - 1][i] = t0;
    }
 
    // Print the final array
    for (long long i = 0; i < n; ++i) {
        for (long long j = 0; j < n; ++j)
            cout << final_array[i][j] << " ";
        cout << endl;
    }
}
 
// Driver code
int main()
{
    long long n = 5;
    solve(n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
// Function to generate the required matrix
static void solve(long n)
{
    long initial_array[][]= new long[(int)n - 1][(int)n - 1],
                    final_array[][]= new long[(int)n][(int)n];
 
    for (long i = 0; i < n - 1; ++i)
        initial_array[0][(int)i] = i + 1;
 
    // Form cyclic array of elements 1 to n-1
    for (long i = 1; i < n - 1; ++i)
        for (long j = 0; j < n - 1; ++j)
            initial_array[(int)i][(int)j]
                = initial_array[(int)i - 1][(int)((int)j + 1) % ((int)n - 1)];
 
    // Store initial array into final array
    for (long i = 0; i < n - 1; ++i)
        for (long j = 0; j < n - 1; ++j)
            final_array[(int)i][(int)j] = initial_array[(int)i][(int)j];
 
    // Fill the last row and column with 0's
    for (long i = 0; i < n; ++i)
        final_array[(int)i][(int)n - 1] = final_array[(int)n - 1][(int)i] = 0;
 
    for (long i = 0; i < n; ++i)
    {
        long t0 = final_array[(int)i][(int)i];
        long t1 = final_array[(int)i][(int)n - 1];
 
        // Swap 0 and the number present
        // at the current indexed row
        long s = final_array[(int)i][(int)i];
        final_array[(int)i][(int)i]=final_array[(int)i][(int)n - 1];
        final_array[(int)i][(int)n - 1]=s;
 
        // Also make changes in the last row
        // with the number we swapped
        final_array[(int)n - 1][(int)i] = t0;
    }
 
    // Print the final array
    for (long i = 0; i < n; ++i)
    {
        for (long j = 0; j < n; ++j)
            System.out.print( final_array[(int)i][(int)j] + " ");
        System.out.println();
    }
}
 
// Driver code
public static void main(String args[])
{
    long n = 5;
    solve(n);
}
}
 
// This code is contributed by Arnab Kundu
   

Python3

# Python 3 implementation of the approach
 
# Function to generate the required matrix
def solve(n):
    initial_array = [[0 for i in range(n-1)] for j in range(n-1)]
    final_array = [[0 for i in range(n)]for j in range(n)]
 
    for i in range(n - 1):
        initial_array[0][i] = i + 1
 
    # Form cyclic array of elements 1 to n-1
    for i in range(1, n - 1):
        for j in range(n - 1):
            initial_array[i][j] = initial_array[i - 1][(j + 1) % (n - 1)]
 
    # Store initial array into final array
    for i in range(n-1):
        for j in range(n-1):
            final_array[i][j] = initial_array[i][j]
 
    # Fill the last row and column with 0's
    for i in range(n):
        final_array[i][n - 1] = final_array[n - 1][i] = 0
 
    for i in range(n):
        t0 = final_array[i][i]
        t1 = final_array[i][n - 1]
 
        # Swap 0 and the number present
        # at the current indexed row
        temp = final_array[i][i]
        final_array[i][i] = final_array[i][n - 1]
        final_array[i][n - 1] = temp
 
        # Also make changes in the last row
        # with the number we swapped
        final_array[n - 1][i] = t0
 
    # Print the final array
    for i in range(n):
        for j in range(n):
            print(final_array[i][j],end = " ")
        print("\n",end = "")
 
# Driver code
if __name__ == '__main__':
    n = 5
    solve(n)
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to generate the required matrix
static void solve(long n)
{
    long [,]initial_array = new long[(int)n - 1,(int)n - 1];
    long [,]final_array = new long[(int)n,(int)n];
 
    for (long i = 0; i < n - 1; ++i)
        initial_array[0,(int)i] = i + 1;
 
    // Form cyclic array of elements 1 to n-1
    for (long i = 1; i < n - 1; ++i)
        for (long j = 0; j < n - 1; ++j)
            initial_array[(int)i,(int)j]
                = initial_array[(int)i - 1,(int)((int)j + 1) % ((int)n - 1)];
 
    // Store initial array into final array
    for (long i = 0; i < n - 1; ++i)
        for (long j = 0; j < n - 1; ++j)
            final_array[(int)i,(int)j] = initial_array[(int)i,(int)j];
 
    // Fill the last row and column with 0's
    for (long i = 0; i < n; ++i)
        final_array[(int)i,(int)n - 1] = final_array[(int)n - 1,(int)i] = 0;
 
    for (long i = 0; i < n; ++i)
    {
        long t0 = final_array[(int)i, (int)i];
        long t1 = final_array[(int)i, (int)n - 1];
 
        // Swap 0 and the number present
        // at the current indexed row
        long s = final_array[(int)i,(int)i];
        final_array[(int)i,(int)i] = final_array[(int)i, (int)n - 1];
        final_array[(int)i,(int)n - 1] = s;
 
        // Also make changes in the last row
        // with the number we swapped
        final_array[(int)n - 1,(int)i] = t0;
    }
 
    // Print the final array
    for (long i = 0; i < n; ++i)
    {
        for (long j = 0; j < n; ++j)
            Console.Write( final_array[(int)i,(int)j] + " ");
        Console.WriteLine();
    }
}
 
// Driver code
public static void Main(String []args)
{
    long n = 5;
    solve(n);
}
}
 
// This code contributed by Rajput-Ji

PHP

<?php
// Php implementation of the approach
 
// Function to generate the required matrix
function solve($n)
{
    $initial_array = array(array()) ;
    $final_array = array(array()) ;
 
    for ($i = 0; $i < $n - 1; ++$i)
        $initial_array[0][$i] = $i + 1;
 
    // Form cyclic array of elements 1 to n-1
    for ($i = 1; $i < $n - 1; ++$i)
        for ($j = 0; $j < $n - 1; ++$j)
            $initial_array[$i][$j] =
                $initial_array[$i - 1][($j + 1) % ($n - 1)];
 
    // Store initial array into final array
    for ($i = 0; $i < $n - 1; ++$i)
        for ($j = 0; $j < $n - 1; ++$j)
            $final_array[$i][$j] = $initial_array[$i][$j];
 
    // Fill the last row and column with 0's
    for ($i = 0; $i < $n; ++$i)
        $final_array[$i][$n - 1] = $final_array[$n - 1][$i] = 0;
 
    for ($i = 0; $i < $n; ++$i)
    {
        $t0 = $final_array[$i][$i];
        $t1 = $final_array[$i][$n - 1];
 
        // Swap 0 and the number present
        // at the current indexed row
        $temp = $final_array[$i][$i] ;
        $final_array[$i][$i] = $final_array[$i][$n - 1] ;
        $final_array[$i][$n - 1] = $temp ;
 
        // Also make changes in the last row
        // with the number we swapped
        $final_array[$n - 1][$i] = $t0;
    }
 
    // Print the final array
    for ($i = 0; $i < $n; ++$i)
    {
        for ($j = 0; $j < $n; ++$j)
            echo $final_array[$i][$j]," ";
        echo "\n";
    }
}
 
    // Driver code
    $n = 5;
    solve($n);
     
// This code is contributed by Ryuga
?>

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to generate the required matrix
function solve(n)
{
    let initial_array = new Array(n-1);
    for (var i = 0; i < initial_array.length; i++) {
    initial_array[i] = new Array(2);
    }
     
    let final_array = new Array(n);
    for (var i = 0; i < final_array.length; i++) {
    final_array[i] = new Array(2);
    }
   
    for (let i = 0; i < n - 1; ++i)
        initial_array[0][i] = i + 1;
   
    // Form cyclic array of elements 1 to n-1
    for (let i = 1; i < n - 1; ++i)
        for (let j = 0; j < n - 1; ++j)
            initial_array[i][j]
                = initial_array[i - 1][(j + 1) % (n - 1)];
   
    // Store initial array into final array
    for (let i = 0; i < n - 1; ++i)
        for (let j = 0; j < n - 1; ++j)
            final_array[i][j] = initial_array[i][j];
   
    // Fill the last row and column with 0's
    for (let i = 0; i < n; ++i)
        final_array[i][n - 1] = final_array[n - 1][i] = 0;
   
    for (let i = 0; i < n; ++i)
    {
        let t0 = final_array[i][i];
        let t1 = final_array[i][n - 1];
   
        // Swap 0 and the number present
        // at the current indexed row
        let s = final_array[i][i];
        final_array[i][i]=final_array[i][n - 1];
        final_array[i][n - 1]=s;
   
        // Also make changes in the last row
        // with the number we swapped
        final_array[n - 1][i] = t0;
    }
   
    // Print the final array
    for (let i = 0; i < n; ++i)
    {
        for (let j = 0; j < n; ++j)
            document.write( final_array[i][j] + " ");
        document.write("<br/>");
    }
}  
 
// Driver Code
    let n = 5;
    solve(n);
   
  // This code is contributed by target_2.
</script>
Producción

0 2 3 4 1 
2 0 4 1 3 
3 4 0 2 1 
4 1 2 0 3 
1 3 1 3 0

Complejidad del Tiempo: O(N 2 )

Espacio Auxiliar: O(N 2 )

Publicación traducida automáticamente

Artículo escrito por ajourney y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *