Матрица Уолша представляет собой особый вид квадратной матрицы с применением в квантовых вычислениях (и , возможно , в другом месте, но я только заботиться о квантовых вычислениях).

Свойства матриц Уолша

Размеры такие же , силы 2. Таким образом, мы можем обратиться к этим матрицам до два экспонента здесь, называя их W(0), W(1), W(2)...

W(0)определяется как [[1]].

Для n>0, W(n)выглядит следующим образом :

[[W(n-1)  W(n-1)]
 [W(n-1) -W(n-1)]]

Так и W(1)есть:

[[1  1]
 [1 -1]]

И W(2)это:

[[1  1  1  1]
 [1 -1  1 -1]
 [1  1 -1 -1]
 [1 -1 -1  1]]

Картина продолжается ...

Твое задание

Напишите программу или функцию, которая принимает в качестве входных данных целое число nи печатает / возвращает W(n)в любом удобном формате. Это может быть массив массивов, сплющенный массив логических выражений, .svgизображение, назовите его, если оно правильное.

Стандартные лазейки запрещены.

Пара вещей:

Для W(0), то 1нужно не быть обернуты даже один раз. Это может быть просто целое число.

Вам разрешено 1-индексировать результаты - W(1)тогда будет [[1]].

Контрольные примеры

0 -> [[1]]
1 -> [[1  1]
      [1 -1]]
2 -> [[1  1  1  1]
      [1 -1  1 -1]
      [1  1 -1 -1]
      [1 -1 -1  1]]
3 -> [[1  1  1  1  1  1  1  1]
      [1 -1  1 -1  1 -1  1 -1]
      [1  1 -1 -1  1  1 -1 -1]
      [1 -1 -1  1  1 -1 -1  1]
      [1  1  1  1 -1 -1 -1 -1]
      [1 -1  1 -1 -1  1 -1  1]
      [1  1 -1 -1 -1 -1  1  1]
      [1 -1 -1  1 -1  1  1 -1]]

8 -> Pastebin

Это код-гольф , поэтому выигрывает самое короткое решение на каждом языке! Удачного игры в гольф!

Perl 6 , 63 44 40 байт

{map {:3(.base(2))%2},[X+&] ^2**$_ xx 2}

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

Нерекурсивный подход, использующий тот факт, что значение в координатах x, y есть (-1)**popcount(x&y). Возвращает сплющенный массив логических значений.

-4 байт благодаря XNOR «s бит четности трюк .

MATL , 4 байта

W4YL

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

Как это работает:

W       % Push 2 raised to (implicit) input
4YL     % (Walsh-)Hadamard matrix of that size. Display (implicit)

Без встроенного: 11 байт

1i:"th1M_hv

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

Как это работает :

Для каждой матрицы Уолша W следующая матрица вычисляется как [ W W ; W - W ], как описано в вызове. Код делает это nраз, начиная с матрицы 1 × 1 [1].

1       % Push 1. This is equivalent to the 1×1 matrix [1]
i:"     % Input n. Do the following n times
  t     %   Duplicate
  h     %   Concatenate horizontally
  1M    %   Push the inputs of the latest function call
  _     %   Negate
  h     %   Concatenate horizontally
  v     %   Concatenate vertically
        % End (implicit). Display (implicit)

Haskell , 57 56 байт

(iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!)

Попробуйте онлайн! Это реализует данную рекурсивную конструкцию.

-1 байт благодаря Эрджану Йохансену !

Октава со встроенным, 18 17 байт

@(x)hadamard(2^x)

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

Октава без встроенного, 56 51 47 байт

function r=f(x)r=1;if x,r=[x=f(x-1) x;x -x];end

Попробуйте онлайн! Спасибо @Luis Mendo за -4.

Октава с рекурсивной лямбдой, 54 53 52 48 байтов

f(f=@(f)@(x){@()[x=f(f)(x-1) x;x -x],1}{1+~x}())

Попробуйте онлайн! Спасибо за этот ответ и этот вопрос для вдохновения.

APL (Dyalog Unicode) , 12 байт

(⍪⍨,⊢⍪-)⍣⎕⍪1

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

Выход представляет собой двумерный массив.

Python 2 , 75 71 байт

r=range(2**input())
print[[int(bin(x&y),13)%2or-1for x in r]for y in r]

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

Матрица Уолша, кажется, связана со злыми числами. Если x&y(побитовое и координат 0 на основе) представляет собой число зла, значение в матрице 1, -1для одиозных чисел. Расчет четности по битам int(bin(n),13)%2взят из комментария Noodle9 к этому ответу .

R , 61 56 53 50 байт

w=function(n)"if"(n,w(n-1)%x%matrix(1-2*!3:0,2),1)

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

Рекурсивно вычисляет матрицу по произведению Кронекера и возвращает 1 для n=0 случая (спасибо Джузеппе за указание на это, а также JAD за помощь в начальном варианте игры в гольф).

Еще -3 байта снова благодаря Джузеппе.

Желе , 14 байт

1WW;"Ѐ,N$ẎƊ⁸¡

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

Изменение Gк ŒṘв сноске , чтобы увидеть фактический выход.

JavaScript (ES6), 77 байт

n=>[...Array(1<<n)].map((_,i,a)=>a.map((_,j)=>1|-f(i&j)),f=n=>n&&n%2^f(n>>1))

Наивный расчет начинается с принятия 0 <= X, Y <= 2**Nв W[N]. Простой случай , когда либо Xили Yменьше 2**(N-1), в этом случае мы рекурсию на X%2**(N-1)и Y%2**(N-1). В случае Xи Yтого, и другого по крайней мере 2**(N-1)рекурсивный вызов должен быть отменен.

Если вместо сравнения используется битовая маска Xили Yменьше, то это ненулевое значение, когда рекурсивный вызов должен быть отменен, и нулевое значение, если это не так. Это также позволяет избежать необходимости уменьшения по модулю .2**(N-1)X&Y&2**(N-1)2**(N-1)

Разумеется, биты могут быть проверены в обратном порядке на тот же результат. Тогда вместо того, чтобы удваивать битовую маску каждый раз, когда мы определяем его координаты, вместо этого можно делить пополам, что позволяет получить результаты XORed, в результате чего конечный результат 0означает отсутствие отрицания и 1означает отрицание.

Пари / ГП , 41 байт

f(n)=if(n,matconcat([m=f(n-1),m;m,-m]),1)

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

К (нгн / к) , 18 байт

{x{(x,x),'x,-x}/1}

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

05AB1E , 16 байтов

oFoL<N&b0м€g®smˆ

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

объяснение

oF                 # for N in 2**input do:
  oL<              # push range [1..2**input]-1
     N&            # bitwise AND with N
       b           # convert to binary
        0м         # remove zeroes
          €g       # length of each
            ®sm    # raise -1 to the power of each
               ˆ   # add to global array

Хотелось бы мне знать более короткий способ вычисления веса Хэмминга.
1δ¢˜такой же длины, как 0м€g.

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

!¡§z+DS+†_;;1

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

1-индексироваться.

объяснение

!¡§z+DS+†_;;1
 ¡        ;;1    Iterate the following function starting from the matrix [[1]]
  §z+              Concatenate horizontally
     D               The matrix with its lines doubled
      S+†_           and the matrix concatenated vertically with its negation
!                Finally, return the result after as many iterations as specified
                 by the input (where the original matrix [[1]] is at index 1)

JavaScript (Node.js) , 100 89 79 байт

f=n=>n?[...(m=F=>r.map(x=>[...x,...x.map(y=>y*F)]))(1,r=f(n-1)),...m(-1)]:[[1]]

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

Python 2 , 80 79 байт

f=lambda n:n<1and[[1]]or[r*2for r in f(n-1)]+[r+[-x for x in r]for r in f(n-1)]

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

Python 2 , 49 байт

Демонстрируем пару подходов с использованием дополнительных библиотек. Этот опирается на встроенный в Scipy:

lambda n:hadamard(2**n)
from scipy.linalg import*

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

Python 2 , 65 байт

И этот использует только Numpy и решает по продукту Kronecker, аналогично моему ответу R :

from numpy import*
w=lambda n:0**n or kron(w(n-1),[[1,1],[1,-1]])

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

Stax , 20 байт

àΩ2┤â#╣_ê|ª⌐╦è│╞►═∞H

Запустите и отладьте его на staxlang.xyz!

Я подумал, что через некоторое время попробую сам. Нерекурсивный подход. Не слишком конкурентоспособен по сравнению с другими языками игры в гольф ...

Распакованный (24 байта) и пояснения

|2c{ci{ci|&:B|+|1p}a*d}*
|2                          Power of 2
  c                         Copy on the stack.
   {                  }     Block:
    c                         Copy on stack.
     i                        Push iteration index (starts at 0).
      {           }           Block:
       ci                       Copy top of stack. Push iteration index.
         |&                     Bitwise and
           :B                   To binary digits
             |+                 Sum
               |1               Power of -1
                 p              Pop and print
                   a          Move third element (2^n) to top...
                    *         And execute block that many times.
                     d        Pop and discard
                       *    Execute block (2^n) times