Круговая свертка с использованием матричного метода

Опубликовано: 5 Января, 2022

Учитывая два массива X [] и H [] длины N и M соответственно, задача состоит в том, чтобы найти круговую свертку данных массивов с помощью метода Matrix. Умножение матрицы с круговым сдвигом и вектора-столбца является круговой сверткой массивов.

Примеры:

Input: X[] = {1, 2, 4, 2}, H[] = {1, 1, 1}
Output: 7 5 7 8

Input: X[] = {5, 7, 3, 2}, H[] = {1, 5}
Output: 15 32 38 17

Объяснение:

  • Создание циклического сдвига матрицы circular_shift_mat из K * K с использованием элементов массива, длина которого является максимальным (Х п в данном случае) , где К MAX (N, M).

    Циркулярно сдвинутая матрица массива X n .

  • Создайте вектор-столбец col_vec длины K
  • Вставьте элементы массива H m в col_vec в позициях [0, m).
  • Поскольку K = max (N, M), здесь N; M <K. Поэтому оставшиеся позиции col_vec [m, K) заполним 0.
  • Следовательно, col_vec будет
    col_vec = {1, 1, 1, 0}
  • Умножьте circular_shift_mat и col_vec
  • Умножение матрицы с круговым смещением (round_shift_mat) и вектора-столбца (col_vec) является круговой сверткой массивов.

Подход:

  • Создайте матрицу с круговым сдвигом N * N, используя элементы массива максимальной длины.
  • Создайте вектор-столбец длины N, используя элементы другого массива, и заполните остальные позиции на 0.
  • Умножение матрицы и вектора-столбца - это круговая свертка массивов.

Ниже представлена реализация описанного выше подхода.

C ++

// C++ program to compute circular
// convolution of two arrays
#include <iostream>
using namespace std;
#define MAX_SIZE 10
// Function to find circular convolution
void convolution( int * x, int * h, int n, int m)
{
int row_vec[MAX_SIZE], col_vec[MAX_SIZE];
int out[MAX_SIZE] = { 0 };
int circular_shift_mat[MAX_SIZE][MAX_SIZE];
// Finding the maximum size between the
// two input sequence sizes
int maxSize = n > m ? n : m;
// Copying elements of x to row_vec and padding
// zeros if size of x < maxSize
for ( int i = 0; i < maxSize; i++) {
if (i >= n) {
row_vec[i] = 0;
}
else {
row_vec[i] = x[i];
}
}
// Copying elements of h to col_vec and padding
// zeros if size of h is less than maxSize
for ( int i = 0; i < maxSize; i++) {
if (i >= m) {
col_vec[i] = 0;
}
else {
col_vec[i] = h[i];
}
}
// Generating 2D matrix of
// circularly shifted elements
int k = 0, d = 0;
for ( int i = 0; i < maxSize; i++) {
int curIndex = k - d;
for ( int j = 0; j < maxSize; j++) {
circular_shift_mat[j][i] = row_vec
[curIndex % maxSize];
curIndex++;
}
k = maxSize;
d++;
}
// Computing result by matrix
// multiplication and printing results
for ( int i = 0; i < maxSize; i++) {
for ( int j = 0; j < maxSize; j++) {
out[i] += circular_shift_mat[i][j]
* col_vec[j];
}
cout << out[i] << " " ;
}
}
// Driver program
int main()
{
int x[] = { 5, 7, 3, 2 };
int n = sizeof (x) / sizeof ( int );
int h[] = { 1, 5 };
int m = sizeof (h) / sizeof ( int );
convolution(x, h, n, m);
return 0;
}

Джава

// Java program to compute circular
// convolution of two arrays
class GFG
{
final static int MAX_SIZE = 10 ;
// Function to find circular convolution
static void convolution( int []x, int []h, int n, int m)
{
int row_vec[] = new int [MAX_SIZE];
int col_vec[] = new int [MAX_SIZE];
int out[] = new int [MAX_SIZE];
int circular_shift_mat[][] = new int [MAX_SIZE][MAX_SIZE];
// Finding the maximum size between the
// two input sequence sizes
int maxSize = n > m ? n : m;
// Copying elements of x to row_vec and padding
// zeros if size of x < maxSize
for ( int i = 0 ; i < maxSize; i++)
{
if (i >= n)
{
row_vec[i] = 0 ;
}
else
{
row_vec[i] = x[i];
}
}
// Copying elements of h to col_vec and padding
// zeros if size of h is less than maxSize
for ( int i = 0 ; i < maxSize; i++)
{
if (i >= m)
{
col_vec[i] = 0 ;
}
else
{
col_vec[i] = h[i];
}
}
// Generating 2D matrix of
// circularly shifted elements
int k = 0 , d = 0 ;
for ( int i = 0 ; i < maxSize; i++)
{
int curIndex = k - d;
for ( int j = 0 ; j < maxSize; j++)
{
circular_shift_mat[j][i] =
row_vec[curIndex % maxSize];
curIndex++;
}
k = maxSize;
d++;
}
// Computing result by matrix
// multiplication and printing results
for ( int i = 0 ; i < maxSize; i++)
{
for ( int j = 0 ; j < maxSize; j++)
{
out[i] += circular_shift_mat[i][j] * col_vec[j];
}
System.out.print(out[i] + " " );
}
}
// Driver program
public static void main (String[] args)
{
int x[] = { 5 , 7 , 3 , 2 };
int n = x.length;
int h[] = { 1 , 5 };
int m = h.length;
convolution(x, h, n, m);
}
}
// This code is contributed by AnkitRai01

Python3

# Python program to compute circular
# convolution of two arrays
MAX_SIZE = 10 ;
# Function to find circular convolution
def convolution(x, h, n, m):
row_vec = [ 0 ] * MAX_SIZE;
col_vec = [ 0 ] * MAX_SIZE;
out = [ 0 ] * MAX_SIZE;
circular_shift_mat = [[ 0 for i in range (MAX_SIZE)]
for j in range (MAX_SIZE)] ;
# Finding the maximum size between the
# two input sequence sizes
if (n > m ):
maxSize = n;
else :
maxSize = m;
# Copying elements of x to row_vec and padding
# zeros if size of x < maxSize
for i in range (maxSize):
if (i > = n):
row_vec[i] = 0 ;
else :
row_vec[i] = x[i];
# Copying elements of h to col_vec and padding
# zeros if size of h is less than maxSize
for i in range (maxSize):
if (i > = m):
col_vec[i] = 0 ;
else :
col_vec[i] = h[i];
# Generating 2D matrix of
# circularly shifted elements
k = 0 ;
d = 0 ;
for i in range (maxSize):
curIndex = k - d;
for j in range (maxSize):
circular_shift_mat[j][i] =
row_vec[curIndex % maxSize];
curIndex + = 1 ;
k = maxSize;
d + = 1 ;
# Computing result by matrix
# multiplication and printing results
for i in range (maxSize):
for j in range (maxSize):
out[i] + = circular_shift_mat[i][j] *
col_vec[j];
print (out[i], end = " " );
# Driver program
if __name__ = = '__main__' :
x = [ 5 , 7 , 3 , 2 ];
n = len (x);
h = [ 1 , 5 ];
m = len (h);
convolution(x, h, n, m);
# This code is contributed by 29AjayKumar

C #

// C# program to compute circular
// convolution of two arrays
using System;
class GFG
{
readonly static int MAX_SIZE = 10 ;
// Function to find circular convolution
static convolution( void int []x, int []h,
int n, int m)
{
int []row_vec = new int [MAX_SIZE];
int []col_vec = new int [MAX_SIZE];
int []out_ = new int [MAX_SIZE];
int [,]circular_shift_mat =
new int [MAX_SIZE,MAX_SIZE];
// Finding the maximum size between the
// two input sequence sizes
int maxSize = n > m ? n : m;
// Copying elements of x to row_vec and padding
// zeros if size of x < maxSize
for ( int i = 0; i < maxSize; i++)
{
if (i >= n)
{
row_vec[i] = 0;
}
else
{
row_vec[i] = x[i];
}
}
// Copying elements of h to col_vec and padding
// zeros if size of h is less than maxSize
for ( int i = 0; i < maxSize; i++)
{
if (i >= m)
{
col_vec[i] = 0;
}
else
{
col_vec[i] = h[i];
}
}
// Generating 2D matrix of
// circularly shifted elements
int k = 0, d = 0;
for ( int i = 0; i < maxSize; i++)
{
int curIndex = k - d;
for ( int j = 0; j < maxSize; j++)
{
circular_shift_mat[j, i] =
row_vec[curIndex % maxSize];
curIndex++;
}
k = maxSize;
d++;
}
// Computing result by matrix
// multiplication and printing results
for ( int i = 0; i < maxSize; i++)
{
for ( int j = 0; j < maxSize; j++)
{
out_[i] += circular_shift_mat[i, j] *
col_vec[j];
}
Console.Write(out_[i] + " " );
}
}
// Driver program
public static void Main(String[] args)
{
int []x = {5, 7, 3, 2};
int n = x.Length;
int []h = {1, 5};
int m = h.Length;
convolution(x, h, n, m);
}
}
// This code is contributed by PrinciRaj1992
Выход:
15 32 38 17

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023