Sebuah Walsh matriks adalah jenis khusus dari matriks persegi dengan aplikasi di kuantum komputasi (dan mungkin di tempat lain, tapi aku hanya peduli tentang komputasi kuantum).

Properti dari matriks Walsh

Dimensi adalah kekuatan yang sama dari 2. Oleh karena itu, kita dapat merujuk matriks ini oleh dua ini eksponen sini, menyebut mereka W(0), W(1), W(2)...

W(0)didefinisikan sebagai [[1]].

Sebab n>0, W(n)terlihat seperti:

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

Begitu W(1)juga:

[[1  1]
 [1 -1]]

Dan W(2)adalah:

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

Polanya berlanjut ...

Tugas Anda

Tulis program atau fungsi yang mengambil input integer ndan mencetak / mengembalikan W(n)dalam format apa pun yang nyaman. Ini bisa berupa array array, array boolean yang rata, .svggambar, apa saja, asalkan itu benar.

Celah standar dilarang.

Beberapa hal:

Sebab W(0), 1tidak perlu dibungkus sekali pun. Ini bisa menjadi bilangan bulat belaka.

Anda diizinkan untuk hasil 1-indeks W(1)kemudian akan [[1]].

Uji kasus

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

Ini adalah kode-golf , jadi solusi terpendek dalam setiap bahasa menang! Selamat bermain golf!

Perl 6 , 63 44 40 byte

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

Cobalah online!

Pendekatan non-rekursif, mengeksploitasi fakta bahwa nilai pada koordinat x, y adalah (-1)**popcount(x&y). Mengembalikan array Boolean yang diratakan.

-4 byte berkat xnor 's bit paritas trik .

MATL , 4 byte

W4YL

Cobalah online!

Bagaimana itu bekerja:

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

Tanpa built-in: 11 byte

1i:"th1M_hv

Cobalah online!

Cara kerjanya :

Untuk setiap matriks Walsh W , matriks berikutnya dihitung sebagai [ W W ; W - W ], seperti yang dijelaskan dalam tantangan. Kode melakukan itu nkali, mulai dari matriks 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 byte

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

Cobalah online! Ini mengimplementasikan konstruksi rekursif yang diberikan.

-1 byte terima kasih kepada Ørjan Johansen !

Oktaf dengan builtin, 18 17 byte

@(x)hadamard(2^x)

Cobalah online!

Oktaf tanpa builtin, 56 51 47 byte

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

Cobalah online! Terima kasih kepada @Luis Mendo untuk -4.

Oktaf dengan lambda rekursif, 54 53 52 48 byte

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

Cobalah online! Terima kasih atas jawaban ini dan pertanyaan ini untuk inspirasi.

APL (Dyalog Unicode) , 12 byte

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

Cobalah online!

Output adalah array 2 dimensi.

Python 2 , 75 71 byte

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

Cobalah online!

Matriks Walsh tampaknya terkait dengan angka-angka jahat. Jika x&y(bitwise dan, koordinat berbasis 0) adalah angka jahat, nilai dalam matriks adalah 1, -1untuk angka najis. Perhitungan bit paritas int(bin(n),13)%2diambil dari komentar Noodle9 pada jawaban ini .

R , 61 56 53 50 byte

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

Cobalah online!

Secara rekursif menghitung matriks dengan produk Kronecker, dan mengembalikan 1 untuk n=0kasing (terima kasih kepada Giuseppe karena menunjukkan ini, dan juga kepada JAD karena telah membantu golf versi awal).

Tambahan -3 byte lagi terima kasih kepada Giuseppe.

Jelly , 14 byte

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

Cobalah online!

Ubah Gto ŒṘdi dalam footer untuk melihat output aktual.

JavaScript (ES6), 77 byte

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

Perhitungan naif dimulai dengan mengambil 0 <= X, Y <= 2**Ndi W[N]. Kasus sederhana adalah ketika salah satu Xatau Ykurang dari 2**(N-1), dalam hal ini kita berulang X%2**(N-1)dan Y%2**(N-1). Dalam hal keduanya Xdan Ysetidaknya 2**(N-1)panggilan rekursif perlu dinegasikan.

Jika daripada membandingkan Xatau Ykurang dari 2**(N-1)bitmask X&Y&2**(N-1)diambil maka ini bukan nol ketika panggilan rekursif perlu dinegasikan dan nol ketika tidak. Ini juga menghindari keharusan mengurangi modulo 2**(N-1).

Bit tentu saja dapat diuji dalam urutan terbalik untuk hasil yang sama. Kemudian daripada menggandakan bitmask setiap kali kita mengoordinasikannya dapat dibelah dua sebagai gantinya, membiarkan hasilnya menjadi XOR, di mana hasil akhir 0berarti tidak ada negasi dan 1berarti negasi.

Pari / GP , 41 byte

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

Cobalah online!

K (ngn / k) , 18 byte

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

Cobalah online!

05AB1E , 16 byte

oFoL<N&b0м€g®smˆ

Cobalah online!

Penjelasan

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

Saya berharap saya tahu cara yang lebih singkat untuk menghitung Berat Hamming.
1δ¢˜panjangnya sama dengan 0м€g.

Sekam , 13 byte

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

Cobalah online!

1-diindeks.

Penjelasan

!¡§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 byte

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

Cobalah online!

Python 2 , 80 79 byte

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)]

Cobalah online!

Python 2 , 49 byte

Menampilkan beberapa pendekatan menggunakan perpustakaan tambahan. Yang ini bergantung pada built-in di Scipy:

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

Cobalah online!

Python 2 , 65 byte

Dan yang ini hanya menggunakan Numpy, dan diselesaikan oleh produk Kronecker, secara analog dengan jawaban R saya :

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

Cobalah online!

Stax , 20 byte

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

Jalankan dan debug di staxlang.xyz!

Kupikir aku akan mencoba tantanganku sendiri setelah beberapa waktu. Pendekatan non-rekursif. Tidak terlalu kompetitif melawan bahasa golf lainnya ...

Dibongkar (24 byte) dan penjelasan

|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