Дискретная свертка или полиномиальное умножение

19

Учитывая два непустых списка целых чисел, ваше представление должно вычислить и вернуть дискретную свертку двух. Интересно, что если вы рассматриваете элементы списка как коэффициенты многочленов, свертка двух списков представляет коэффициенты произведения двух многочленов.

Определение

Учитывая списки A=[a(0),a(1),a(2),...,a(n)]и B=[b(0),b(1),b(2),...,b(m)](установка a(k)=0 for k<0 and k>nи b(k)=0 for k<0 and k>m), тогда свертка двух определяется как A*B=[c(0),c(1),...,c(m+n)]гдеc(k) = sum [ a(x)*b(y) for all integers x y such that x+y=k]

правила

  • Допускается любое удобное форматирование ввода и вывода для вашего языка.
  • Встроенные модули для свертки, создания матриц свертки, корреляции и полиномиального умножения не допускаются.

Примеры

[1,1]*[1] = [1,1]
[1,1]*[1,1] = [1,2,1]
[1,1]*[1,2,1] = [1,3,3,1]
[1,1]*[1,3,3,1] = [1,4,6,4,1]
[1,1]*[1,4,6,4,1] = [1,5,10,10,5,1]

[1,-1]*[1,1,1,1,1] = [1,0,0,0,0,-1]
[80085,1337]*[-24319,406] = [-1947587115,7,542822]
flawr
источник
3
Спецификация подразумевает, что входные данные длины n, m должны создавать выходные данные длины n + m - 1, но это не выполняется для вашего тестового примера [1,1]*[] = []и не может быть возможным для []*[] = ?. Свертка не четко определена в пустых списках. Я думаю, вы должны гарантировать, что списки ввода непусты.
Андерс Касеорг
1
@AndersKaseorg Вы правы, я изменю это.
flawr
связанные: codegolf.stackexchange.com/q/67289/29325
sergiol

Ответы:

14

J 10 8 байт

[:+//.*/

Использование:

ppc =: [:+//.*/    NB. polynomial product coefficients 
80085 1337 ppc _24319 406
_1947587115 7 542822

Описание: Программа берет два списка, составляет таблицу умножения, затем добавляет числа на положительных диагоналях.

ljeabmreosn
источник
Очень умный подход!
Луис Мендо
Вам не нужно считать скобки. Выражение внутри них оценивается как молчаливый глагол, который можно присвоить переменной.
Деннис
Отличный пример наречий!
мили
6

MATL , 19 байт

PiYdt"TF2&YStpsw]xx

Попробуйте онлайн!

объяснение

Это создает блочно-диагональную матрицу с двумя входами, обращая первый. Например, с входами [1 4 3 5], [1 3 2]матрица

[ 5 3 4 1 0 0 0
  0 0 0 0 1 3 2 ]

Каждая запись свертки получается путем смещения первой строки на одну позицию вправо, вычисления произведения каждого столбца и суммирования всех результатов.

В принципе, сдвиг должен выполняться с нулями слева. Эквивалентно, круговое смещение может использоваться, потому что матрица содержит нули в соответствующих записях.

Например, первый результат получается из смещенной матрицы

[ 0 5 3 4 1 0 0
  0 0 0 0 1 3 2 ]

и таким образом 1*1 == 1. Второй получается из

[ 0 0 5 3 4 1 0
  0 0 0 0 1 3 2 ]

и, таким образом 4*1+1*3 == 7, и т. д. Это должно быть сделано m+n-1раз, где mи nдлина ввода. Код использует цикл с m+nитерациями (который сохраняет несколько байтов) и отбрасывает последний результат.

P          % Take first input (numeric vactor) implicitly and reverse it
i          % Take second input (numeric vactor) 
Yd         % Build diagonal matrix with the two vectors
t          % Duplicate
"          % For each column of the matrix
  TF2&YS   %   Circularly shift first row 1 step to the right
  t        %   Duplicate
  p        %   Product of each column
  s        %   Sum all those products
  w        %   Swap top two elements in stack. The shifted matrix is left on top
]          % End for
xx         % Delete matrix and last result. Implicitly display
Луис Мендо
источник
4

Haskell, 55 49 байтов

(a:b)#c=zipWith(+)(0:b#c)$map(a*)c++[]#b
_#c=0<$c

Определяет оператора #.

Андерс Касеорг
источник
1
Я думаю, что отступы [0,0..]могут (0<$b)дать точно необходимую длину, оставляя пустым базовый случай _#b=0<$b.
xnor
@xnor Действительно, это экономит 6 байтов.
Андерс Касеорг
Теперь, когда я наконец понял ваш ответ, я должен сказать, что это чертовски умно! Я впечатлен!
flawr
3

Matlab / Octave, 41 байт

@(p,q)poly([roots(p);roots(q)])*p(1)*q(1)

Это определяет анонимную функцию. Чтобы вызвать его, присвойте его переменной или используйте ans.

Попробуй это здесь .

объяснение

Это использует факты, которые

  • Корни (возможно, повторяющиеся) характеризуют многочлен с точностью до его ведущего коэффициента.
  • Произведение двух полиномов имеет корни обоих.

Код вычисляет корни двух полиномов (функции roots) и объединяет их в массив столбцов. Отсюда получаются коэффициенты многочлена произведения с лидирующей 1(функцией poly). Наконец, результат умножается на старшие коэффициенты двух полиномов.

Луис Мендо
источник
3

Октава , 48 байт

@(p,q)ifft(fft([p q*0]).*fft([q p*0]))(1:end-1)

Попробуй это здесь .

объяснение

Дискретная свертка соответствует умножению (дискретного времени) преобразований Фурье. Таким образом, одним из способов умножения многочленов будет преобразование их, умножение преобразованных последовательностей и обратное преобразование.

Если вместо преобразования Фурье используется дискретное преобразование Фурье (ДПФ) , результатом является циклическая свертка исходных последовательностей полиномиальных коэффициентов. Код следует этому маршруту. Чтобы сделать круговую свертку равной стандартной свертке, последовательности дополняются нулями, а результат обрезается.

Луис Мендо
источник
Черт, я все еще мог бы забанить ффт, но хорошая работа!
flawr
@flawr Да, я думаю, что мы говорили об этом ...? :-P
Луис Мендо
2

05AB1E , 18 17 байт

Код

0Ev²¹g<Å0«y*NFÁ}+

объяснение

Теория позади:

Чтобы найти свертку, давайте рассмотрим пример [1, 2, 3], [3, 4, 5]. Мы позиционируем значения первого массива вверх ногами и вертикально, вот так:

3
2
1

Теперь мы помещаем второй массив как лестницу и умножаем его на:

3 ×       [3  4  5]
2 ×    [3  4  5]
1 × [3  4  5]

В результате чего:

        9   12   15
    6   8   10
3   4   5

Затем мы складываем их, получая в результате:

        9   12   15
    6   8   10
3   4   5       

3   10  22  22   15

Итак, свертка есть [3, 10, 22, 22, 15].

Сам код:

Мы будем делать это шаг за шагом , используя [1, 2, 3], в [3, 4, 5]качестве тестового примера.

0Ev²¹g<Å0«y*NFÁ}+

Сначала мы нажимаем, 0а затем Eоцениваем первый входной массив. Мы наносим на карту каждый элемент, используя v.

Таким образом, для каждого элемента мы добавляем второй массив, ²а затем используем длину первого массива ¹gи уменьшаем его на 1 (с <). Мы конвертируем это в список нулей с (длина 1-го массива - 1) нулей, используя Å0и добавляем это в наш список. Теперь наш стек выглядит следующим образом для первого элемента в списке ввода:

[3, 4, 5, 0, 0]

Мы умножаем этот массив на текущий элемент, сделанный с y*. После этого мы нажимаем N, что указывает на индекс текущего элемента (с нулевым индексом) и поворачиваем массив, который много раз вправо, используя FÁ}. Наконец, мы добавляем это к нашему начальному значению ( 0). Итак, в основном делается следующее:

[0, 0, 9, 12, 15] +
[0, 6, 8, 10, 0] +
[3, 4, 5, 0, 0] =

[3, 10, 22, 22, 15]

Который затем неявно печатается. Использует кодировку CP-1252 . Попробуйте онлайн! ,

Аднан
источник
2

Желе , 9 байт

0;+
×'Ṛç/

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это устроено

×'Ṛç/  Main link. Arguments: p, q (lists)

×'     Spawned multiplication; multiply each item of p with each item of q.
  Ṛ    Reverse the rows of the result.
   ç/  Reduce the rows by the helper link.


0;+    Helper link. Arguments: p, q (lists)

0;     Prepend a 0 to p.
  +    Perform vectorized addition of the result and q.
Деннис
источник
Что желе дольше, чем J? Это невозможно по определению!
Адам
2

Шелуха , 5 байт

mΣ∂Ṫ*

Попробуйте онлайн!

Примечание: при предоставлении нулевого полиномиального / пустого списка вам необходимо указать его тип (т.е. []:LN)!

объяснение

mΣ∂Ṫ*  -- implicit inputs xs ys, for example: [1,-1] [1,1]
   Ṫ*  -- compute the outer product xsᵀ·ys: [[1,1],[-1,-1]]
  ∂    -- diagonals: [[1],[1,-1],[-1]]
mΣ     -- map sum: [1,0,1]
ბიმო
источник
2

Matlab, 33 байта

@(x,y)sum(spdiags(flip(x').*y),1)

Попробуйте онлайн!

Создает матрицу всех поэлементных произведений входных данных, затем суммирует по диагонали. В ,1конце вынуждает matlab суммировать вдоль правильного направления, когда один из входных векторов имеет длину 1.

В Octave spdiagsне работает для векторов, что приводит к ошибке, когда один из входов имеет длину 1. Matlab 2016b или новее требуется для явного расширения поэлементного произведения.

LUKEŠ
источник
Хороший подход !!
Луис Мендо
1

Python, 90 байт

lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in range(k+1))for k in range(len(p+q)-1)]
orlp
источник
1

JavaScript (ES6), 64 байта

(a,b)=>a.map((n,i)=>b.map((m,j)=>r[j+=i]=m*n+(r[j]||0)),r=[])&&r

Возвращает пустой массив, если любой из входных данных пуст. На основании моего ответа на полиномиал .

Нил
источник
1

Clojure, 104 байта

#(vals(apply merge-with +(sorted-map)(for[i(range(count %))j(range(count %2))]{(+ i j)(*(% i)(%2 j))})))

Объединение sorted-mapгарантирует, что значения возвращаются в правильном порядке. Хотелось бы, чтобы было еще несколько тестов.

NikoNyrh
источник