Uma matriz de Walsh é um tipo especial de matriz quadrada com aplicações na computação quântica (e provavelmente em outros lugares, mas eu me preocupo apenas com a computação quântica).

Propriedades das matrizes de Walsh

As dimensões são a mesma potência de 2. Portanto, podemos nos referir a essas matrizes por expoente dois está aqui, chamando-os W(0), W(1),W(2) ...

W(0) é definido como [[1]] .

Pois n>0, W(n)parece com:

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

Então W(1)é:

[[1  1]
 [1 -1]]

E W(2)é:

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

O padrão continua ...

Sua tarefa

Escreva um programa ou função que tome como entrada um número inteiro ne imprima / retorne W(n)em qualquer formato conveniente. Pode ser uma matriz de matrizes, uma matriz plana de booleanos, uma .svgimagem, o nome dela, desde que esteja correta.

As brechas padrão são proibidas.

Algumas coisas:

Pois W(0), 1não é necessário embrulhar nem uma vez. Pode ser um mero inteiro.

Você tem permissão para resultados de 1 índice - W(1)seria[[1]] .

Casos de teste

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

Isso é código-golfe , então a solução mais curta em cada idioma vence! Feliz golfe!

Perl 6 , 63 44 40 bytes

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

Experimente online!

Abordagem não recursiva, explorando o fato de que o valor nas coordenadas x, y é (-1)**popcount(x&y) . Retorna uma matriz nivelada de booleanos.

-4 bytes graças a xnor 's truque bit de paridade .

MATL , 4 bytes

W4YL

Experimente online!

Como funciona:

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

Sem o built-in: 11 bytes

1i:"th1M_hv

Experimente online!

Como funciona :

Para cada matriz Walsh W , a próxima matriz é calculada como [ W W ; W - W ], conforme descrito no desafio. O código faz isso nvezes, começando na 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]]!!)

Experimente online! Isso implementa a construção recursiva fornecida.

-1 byte graças a Ørjan Johansen !

Oitava com built-in, 18 17 bytes

@(x)hadamard(2^x)

Experimente online!

Oitava sem built-in, 56 51 47 bytes

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

Experimente online! Obrigado a @Luis Mendo por -4.

Oitava com lambda recursiva, 54 53 52 48 bytes

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

Experimente online! Graças a esta resposta e a esta pergunta por inspiração.

APL (Dyalog Unicode) , 12 bytes

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

Experimente online!

A saída é uma 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]

Experimente online!

A matriz de Walsh parece estar relacionada aos números malignos. Se x&y(bit a bit e, com base coordenadas-0) é um número mal, o valor na matriz é 1, -1em números odious. O cálculo da paridade de bits int(bin(n),13)%2é retirado do comentário do Noodle9 sobre esta resposta .

R , 61 56 53 50 bytes

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

Experimente online!

Calcula recursivamente a matriz pelo produto Kronecker e retorna 1 para o n=0caso (graças a Giuseppe por apontar isso e também ao JAD por ajudar a jogar golfe na versão inicial).

-3 bytes adicionais novamente graças a Giuseppe.

Gelatina , 14 bytes

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

Experimente online!

Altere Gpara ŒṘno rodapé para ver a saída 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))

O cálculo ingênuo começa tomando 0 <= X, Y <= 2**Nem W[N]. O caso simples é quando um Xou Yé menor que 2**(N-1), caso em que recorremos em X%2**(N-1)e Y%2**(N-1). No caso de ambos Xe Ysendo pelo menos2**(N-1) a chamada recursiva precisa ser negada.

Se em vez de comparar Xou Ymenos de 2**(N-1)uma máscara de bits X&Y&2**(N-1)for usada, isso será diferente de zero quando a chamada recursiva precisar ser negada e zero quando não for necessária. Isso também evita ter que reduzir o módulo 2**(N-1).

Obviamente, os bits podem ser testados na ordem inversa para o mesmo resultado. Então, em vez de dobrar a máscara de bit cada vez que ele coordena, pode ser dividido pela metade, permitindo que os resultados sejam XOR, pelo que um resultado final 0significa que não há negação e 1significa negação.

Pari / GP , 41 bytes

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

Experimente online!

K (ngn / k) , 18 bytes

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

Experimente online!

05AB1E , 16 bytes

oFoL<N&b0м€g®smˆ

Experimente online!

Explicação

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

Eu gostaria de conhecer uma maneira mais curta de calcular o peso de Hamming.
1δ¢˜tem o mesmo comprimento que 0м€g.

Casca , 13 bytes

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

Experimente online!

1 indexado.

Explicação

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

Experimente online!

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

Experimente online!

Python 2 , 49 bytes

Apresentando algumas abordagens usando bibliotecas adicionais. Este conta com um recurso interno do Scipy:

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

Experimente online!

Python 2 , 65 bytes

E este usa apenas o Numpy e resolve pelo produto Kronecker, analogamente à minha resposta R :

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

Experimente online!

Stax , 20 bytes

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

Execute e depure-o em staxlang.xyz!

Pensei em tentar meu próprio desafio depois de algum tempo. Abordagem não recursiva. Não é muito competitivo contra outras línguas do golfe ...

Descompactado (24 bytes) e explicação

|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