Given an array A[], the task is to find the circulant matrix made by this array.
A circulant matrix is a square matrix of order N x N, where each column is composed of the same elements, but each column is rotated one element to the bottom relative to the preceding column. It is a particular kind of Toeplitz matrix.
Here is the general form of a circulant matrix.
General structure of Circulant Matrix
Examples:
Input: a[] = {2, 3, 4, 5}.
Output: Then the resultant circulant matrix should be:
2 3 4 5
3 4 5 2
4 5 2 3
5 2 3 4Input: a[] = {0, 4, 0, 7, 9, 12, 17}.
Output: The resultant circulant matrix should be:
0 4 0 7 9 12 17
4 0 7 9 12 17 0
0 7 9 12 17 0 4
7 9 12 17 0 4 0
9 12 17 0 4 0 7
12 17 0 4 0 7 9
17 0 4 0 7 9 12
Approach: This is a simple implementation based problem based on the following idea:
For each ith column, insert the first element of the array at ith row and insert all the other elements iterating through the column in a circular manner.
Follow the below steps to solve the problem:
- Initialize an empty matrix (say c[][])of order N.
- Iterate through the columns from i = 0 to N-1:
- Iterate through the rows using a nested loop from j = 0 to N-1.
- if (i > 0), then assign c[j][i] = c[j – 1][i – 1].
- else, assign c[j][i] = c[N – 1][i – 1].
- Iterate through the rows using a nested loop from j = 0 to N-1.
- At last, display the circulant matrix.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <iostream>using namespace std;// Circulant function defined herevoid circulant(int arr[], int n){ // Initializing an empty // 2D matrix of order n int c[n][n]; for (int k = 0; k <= n - 1; k++) c[k][0] = arr[k]; // Forming the circulant matrix for (int i = 1; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { if (j - 1 >= 0) c[j][i] = c[j - 1][i - 1]; else c[j][i] = c[n - 1][i - 1]; } } // Displaying the circulant matrix for (int i = 0; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { cout << c[i][j] << "\t"; } cout << "\n"; }}// Driver Codeint main(){ int N = 4; int A[] = { 2, 3, 4, 5 }; // Function call circulant(A, N); return 0;}// This code is contributed by Rohit Pradhan |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Circulant function defined here public static void circulant(int arr[], int n) { // Initializing an empty // 2D matrix of order n int c[][] = new int[n][n]; for (int k = 0; k <= n - 1; k++) c[k][0] = arr[k]; // Forming the circulant matrix for (int i = 1; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { if (j - 1 >= 0) c[j][i] = c[j - 1][i - 1]; else c[j][i] = c[n - 1][i - 1]; } } // Displaying the circulant matrix for (int i = 0; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { System.out.print(c[i][j] + "\t"); } System.out.println(); } } // Driver code public static void main(String[] args) { int N = 4; int A[] = { 2, 3, 4, 5 }; circulant(A, N); }} |
Python3
# Python code to implement the approach# Circulant function defined heredef circulant( arr, n): # Initializing an empty # 2D matrix of order n c = [[0 for i in range(n)] for j in range(n)] for k in range(n): c[k][0] = arr[k] # Forming the circulant matrix for i in range(1,n): for j in range(n): if (j - 1 >= 0): c[j][i] = c[j - 1][i - 1] else: c[j][i] = c[n - 1][i - 1] # Displaying the circulant matrix for i in range(n): for j in range(n): print(c[i][j] ,end="\t") print() # Driver codeN = 4A = [2, 3, 4, 5 ]circulant(A, N) # This code is contributed by rohitsingh07052 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Circulant function defined here public static void circulant(int[] arr, int n) { // Initializing an empty // 2D matrix of order n int[,] c = new int[n, n]; for (int k = 0; k <= n - 1; k++) c[k, 0] = arr[k]; // Forming the circulant matrix for (int i = 1; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { if (j - 1 >= 0) c[j, i] = c[j - 1, i - 1]; else c[j, i] = c[n - 1, i - 1]; } } // Displaying the circulant matrix for (int i = 0; i <= n - 1; i++) { for (int j = 0; j <= n - 1; j++) { Console.Write(c[i, j] + "\t"); } Console.WriteLine(); } }// Driver Codepublic static void Main(){ int N = 4; int[] A = { 2, 3, 4, 5 }; circulant(A, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// JavaScript code to implement the approach// Circulant function defined herefunction circulant(arr, n){ // Initializing an empty // 2D matrix of order n let c = new Array(n).fill(0).map(()=>new Array(n)); for (let k = 0; k <= n - 1; k++) c[k][0] = arr[k]; // Forming the circulant matrix for (let i = 1; i <= n - 1; i++) { for (let j = 0; j <= n - 1; j++) { if (j - 1 >= 0) c[j][i] = c[j - 1][i - 1]; else c[j][i] = c[n - 1][i - 1]; } } // Displaying the circulant matrix for (let i = 0; i <= n - 1; i++) { for (let j = 0; j <= n - 1; j++) { document.write(`${c[i][j]} \t`) } document.write("</br>") }}// Driver Codelet N = 4let A = [ 2, 3, 4, 5 ]// Function callcirculant(A, N)// This code is contributed by shinjanpatra</script> |
2 5 4 3 3 2 5 4 4 3 2 5 5 4 3 2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
