Una matriz de Walsh es un tipo especial de matriz cuadrada con aplicaciones en computación cuántica (y probablemente en otros lugares, pero solo me importa la computación cuántica).

Propiedades de las matrices de Walsh

Las dimensiones son de la misma potencia de 2. Por lo tanto, podemos referirnos a estas matrices por exponente de dos aquí, llamándolos W(0), W(1), W(2)...

W(0)se define como [[1]].

Para n>0, se W(n)ve así:

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

Entonces W(1)es:

[[1  1]
 [1 -1]]

Y W(2)es:

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

El patrón continúa ...

Tu tarea

Escriba un programa o función que tome como entrada un número entero ne imprima / devuelva W(n)en cualquier formato conveniente. Puede ser una matriz de matrices, una matriz aplanada de booleanos, una .svgimagen, lo que sea, siempre que sea correcto.

Las lagunas estándar están prohibidas.

Un par de cosas:

Para W(0), la 1necesidad no se envuelve ni una sola vez Puede ser un mero entero.

Se le permite obtener 1 índice de resultados W(1), entonces sería [[1]].

Casos de prueba

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

Este es el código de golf , por lo que gana la solución más corta en cada idioma. ¡Feliz golf!

Perl 6 , 63 44 40 bytes

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

Pruébalo en línea!

Enfoque no recursivo, explotando el hecho de que el valor en las coordenadas x, y es (-1)**popcount(x&y). Devuelve una matriz aplanada de booleanos.

-4 bytes gracias a XNOR 's truco bit de paridad .

MATL , 4 bytes

W4YL

Pruébalo en línea!

Cómo funciona:

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

Sin el incorporado: 11 bytes

1i:"th1M_hv

Pruébalo en línea!

Cómo funciona :

Para cada matriz Walsh W , la siguiente matriz se calcula como [ W W ; W - W ], como se describe en el desafío. El código hace ese ntiempo, comenzando desde la matriz 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 bytes

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

Pruébalo en línea! Esto implementa la construcción recursiva dada.

-1 byte gracias a Ørjan Johansen !

Octava con incorporado, 18 17 bytes

@(x)hadamard(2^x)

Pruébalo en línea!

Octava sin construir, 56 51 47 bytes

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

Pruébalo en línea! Gracias a @Luis Mendo por -4.

Octava con lambda recursiva, 54 53 52 48 bytes

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

Pruébalo en línea! Gracias a esta respuesta y esta pregunta por inspiración.

APL (Dyalog Unicode) , 12 bytes

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

Pruébalo en línea!

La salida es una matriz bidimensional.

Python 2 , 75 71 bytes

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

Pruébalo en línea!

La matriz de Walsh parece estar relacionada con los números malvados. Si x&y(coordenadas bit a bit y basadas en 0) es un número malo, el valor en la matriz es 1, -1para números odiosos. El cálculo de la paridad de bits int(bin(n),13)%2se toma del comentario de Noodle9 sobre esta respuesta .

R , 61 56 53 50 bytes

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

Pruébalo en línea!

Calcula recursivamente la matriz por el producto Kronecker, y devuelve 1 por n=0caso (gracias a Giuseppe por señalar esto, y también a JAD por ayudar a jugar golf la versión inicial).

-3 bytes adicionales nuevamente gracias a Giuseppe.

Jalea , 14 bytes

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

Pruébalo en línea!

Cambie Ga ŒṘen el pie de página para ver la salida real.

JavaScript (ES6), 77 bytes

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

El cálculo ingenuo comienza tomando 0 <= X, Y <= 2**Nen W[N]. El caso simple es cuando Xo Yes menor que 2**(N-1), en cuyo caso recurrimos en X%2**(N-1)y Y%2**(N-1). En el caso de ambos Xy de Yser al menos 2**(N-1)la llamada recursiva debe ser negada.

Si en lugar de comparar Xo se toma Ymenos de 2**(N-1)una máscara de bits X&Y&2**(N-1), esto no es cero cuando la llamada recursiva necesita ser negada y cero cuando no lo hace. Esto también evita tener que reducir el módulo 2**(N-1).

Por supuesto, los bits se pueden probar en orden inverso para obtener el mismo resultado. Luego, en lugar de duplicar la máscara de bits cada vez que coordinamos, se puede reducir a la mitad, permitiendo que los resultados sean XORed, por lo que un resultado final 0significa no negación y 1significa negación.

Pari / GP , 41 bytes

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

Pruébalo en línea!

K (ngn / k) , 18 bytes

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

Pruébalo en línea!

05AB1E , 16 bytes

oFoL<N&b0м€g®smˆ

Pruébalo en línea!

Explicación

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

Ojalá supiera una forma más corta de calcular el peso de Hamming.
1δ¢˜tiene la misma longitud que 0м€g.

Casco , 13 bytes

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

Pruébalo en línea!

1 indexado.

Explicación

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

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

Pruébalo en línea!

Python 2 , 80 79 bytes

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

Pruébalo en línea!

Python 2 , 49 bytes

Mostrando un par de enfoques utilizando bibliotecas adicionales. Este se basa en un Scipy incorporado:

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

Pruébalo en línea!

Python 2 , 65 bytes

Y este solo usa Numpy, y resuelve por el producto Kronecker, de manera análoga a mi respuesta R :

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

Pruébalo en línea!

Stax , 20 bytes

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

¡Ejecútelo y depúrelo en staxlang.xyz!

Pensé en probar mi propio desafío después de algún tiempo. Enfoque no recursivo. No es demasiado competitivo contra otros idiomas de golf ...

Desempaquetado (24 bytes) y explicación

|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