Wygeneruj matrycę Walsha

22

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!

code-golf  math  matrix 
— Khuldraeseth na'Barya
źródło
— Khuldraeseth na'Barya
Czy wyniki można indeksować 1? (np. W(1)zwraca [[1]], W(2)zwraca [[1,1],[1,-1]...)
— Lew
@Leo Tak, mogą. Zredagowano w.
— Khuldraeseth na'Barya

Odpowiedzi:

10

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)
— Luis Mendo
źródło
2
Ugh ... a tutaj próbuję użyć kron. ;)
— zlewka
5

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ę.

— sufitowy
źródło
Jeśli funkcja jest zdefiniowana w pliku, drugi endnie jest potrzebny. Możesz więc przenieść go do nagłówka TIO, a tym samym usunąć go z liczby bajtów
— Luis Mendo
4

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 .

— ovs
źródło
2
Intuicyjnie znak w (x, y) jest odwracany tyle razy, ile jest poziomów rekurencji, na których (x, y) znajduje się w prawym dolnym kwadrancie macierzy (2 ^ k × 2 ^ k), który występuje gdy oba x i y mają 1 w k-tym bicie. Korzystając z tego faktu, możemy po prostu policzyć 1 bit, x&yaby określić, ile razy należy odwrócić znak.
— Lynn
4

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.

— Kirill L.
źródło
Nie wiem, czy powrocie 1aniżeli matrix(1)jest ważny, ale jeśli jest to możliwe golf to w dół, a tam 61 bajtów Reducepodejście, a także: spróbuj!
— Giuseppe,
Nie jestem również pewien formatu n=0przypadku, większość innych odpowiedzi otacza go [[1]], ale nie wszystkie ...
— Kirill L.
1
Można wymienić matrix(1)z t(1).
— JAD
1
Pytanie zostało edytowane. Możesz zwrócić liczbę całkowitą zamiast macierzy.
— Khuldraeseth na'Barya
1
1-2*!3:0jest krótszy niż c(1,1,1,-1)o trzy bajty.
— Giuseppe,
2

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ę.

— Neil
źródło
1

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.

— Emigna
źródło
1

Ł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)
— Lew
źródło
0

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!

— Kirill L.
źródło
0

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
— Khuldraeseth na'Barya
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.