Walsh matryca jest specjalny rodzaj macierzy kwadratowej z aplikacji Quantum computing (i zapewne gdzie indziej, ale zależy mi tylko o quantum computing).

Właściwości macierzy Walsha

Wymiary są takie same moc 2. Dlatego, możemy odnieść się do tych matryc o dwa za wykładnik tutaj, nazywając je W(0), W(1), W(2)...

W(0)jest zdefiniowany jako [[1]].

Dla n>0, W(n)wygląda następująco:

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

Tak W(1)jest:

[[1  1]
 [1 -1]]

I W(2)jest:

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

Wzór trwa ...

Twoje zadanie

Napisz program lub funkcję, która przyjmuje jako liczbę całkowitą ni drukuje / zwraca W(n)w dowolnym dogodnym formacie. Może to być tablica tablic, spłaszczona tablica booleanów, .svgobraz, nazywasz go, o ile jest poprawny.

Standardowe luki są zabronione.

Kilka rzeczy:

Dla W(0)The 1nie muszą być owinięte jeszcze raz. Może to być zwykła liczba całkowita.

Masz prawo do 1-indeksu wyników - W(1)byłoby [[1]].

Przypadki testowe

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

To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie w każdym języku! Miłej gry w golfa!

Perl 6 , 63 44 40 bajtów

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

Wypróbuj online!

Podejście nierekurencyjne, wykorzystujące fakt, że wartość przy współrzędnych x, y wynosi (-1)**popcount(x&y). Zwraca spłaszczoną tablicę wartości logicznych.

-4 bajty dzięki XNOR jest bit parzystości podstęp .

MATL , 4 bajty

W4YL

Wypróbuj online!

Jak to działa:

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

Bez wbudowanego: 11 bajtów

1i:"th1M_hv

Wypróbuj online!

Jak to działa :

Dla każdej macierzy Walsha W następną macierz oblicza się jako [ W W ; W - W ], jak opisano w wyzwaniu. Kod robi to tyle nrazy, zaczynając od macierzy 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 bajtów

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

Wypróbuj online! To implementuje daną konstrukcję rekurencyjną.

-1 bajt dzięki Ørjan Johansen !

Oktawa z wbudowanym 18 17 bajtami

@(x)hadamard(2^x)

Wypróbuj online!

Oktawa bez wbudowanego, 56 51 47 bajtów

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

Wypróbuj online! Dzięki @Luis Mendo za -4.

Oktawa z rekurencyjną lambda, 54 53 52 48 bajtów

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

Wypróbuj online! Dzięki tej odpowiedzi i temu pytaniu o inspirację.

APL (Dyalog Unicode) , 12 bajtów

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

Wypróbuj online!

Dane wyjściowe to tablica dwuwymiarowa.

Python 2 , 75 71 bajtów

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

Wypróbuj online!

Matryca Walsha wydaje się być związana ze złymi liczbami. Jeśli x&y(bitowe oraz współrzędne w oparciu o 0) jest liczbą zła wartość w matrycy 1, -1dla liczb odrażających. Obliczenie parzystości bitowej int(bin(n),13)%2pochodzi z komentarza Noodle9 do tej odpowiedzi .

R , 61 56 53 50 bajtów

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

Wypróbuj online!

Rekurencyjnie oblicza macierz według produktu Kronecker i zwraca 1 dla n=0przypadku (podziękowania dla Giuseppe za wskazanie tego, a także dla JAD za pomoc w golfa w początkowej wersji).

Dodatkowe -3 bajty ponownie dzięki Giuseppe.

Galaretka , 14 bajtów

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

Wypróbuj online!

Zmienić Gsię ŒṘw stopce, aby zobaczyć rzeczywistą wydajność.

JavaScript (ES6), 77 bajtów

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

Naiwny obliczanie rozpoczyna się od podejmowania 0 <= X, Y <= 2**Nw W[N]. Prostym przypadkiem jest, gdy albo jest Xalbo Ymniej niż 2**(N-1), w którym to przypadku powracamy do X%2**(N-1)i Y%2**(N-1). W przypadku obu Xi Ybycia przynajmniej 2**(N-1)rekursywne połączenie musi być zanegowane.

Jeśli zamiast porównywania Xlub Ymniej niż 2**(N-1)maska ​​bitowa X&Y&2**(N-1)jest brana, jest to niezerowe, gdy wywołanie rekurencyjne musi być zanegowane i zero, gdy nie jest. Pozwala to również uniknąć konieczności zmniejszania modulo 2**(N-1).

Bity można oczywiście testować w odwrotnej kolejności, aby uzyskać ten sam wynik. Następnie zamiast podwajać maskę bitową za każdym razem, gdy współrzędne są współrzędne, można zamiast tego zmniejszyć o połowę, co pozwala na XOR, a końcowy wynik 0oznacza brak negacji i 1oznacza negację.

Pari / GP , 41 bajtów

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

Wypróbuj online!

K (ngn / k) , 18 bajtów

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

Wypróbuj online!

05AB1E , 16 bajtów

oFoL<N&b0м€g®smˆ

Wypróbuj online!

Wyjaśnienie

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

Chciałbym znać krótszy sposób obliczania wagi Hamminga.
1δ¢˜ma taką samą długość jak 0м€g.

Łuska , 13 bajtów

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

Wypróbuj online!

1-indeksowany.

Wyjaśnienie

!¡§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 bajtów

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

Wypróbuj online!

Python 2 , 80 79 bajtów

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

Wypróbuj online!

Python 2 , 49 bajtów

Prezentacja kilku podejść przy użyciu dodatkowych bibliotek. Ten opiera się na wbudowanym w Scipy:

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

Wypróbuj online!

Python 2 , 65 bajtów

A ten używa tylko Numpy i rozwiązuje produkt Kronecker, analogicznie do mojej odpowiedzi R :

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

Wypróbuj online!

Stax , 20 bajtów

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

Uruchom i debuguj na staxlang.xyz!

Pomyślałem, że po pewnym czasie spróbuję własnego wyzwania. Podejście nierekurencyjne. Niezbyt konkurencyjny w stosunku do innych języków golfowych ...

Rozpakowano (24 bajty) i wyjaśnienie

|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