Une matrice de Walsh est un type spécial de matrice carrée avec des applications en informatique quantique (et probablement ailleurs, mais je ne me soucie que de l'informatique quantique).

Propriétés des matrices de Walsh

Les dimensions sont la même puissance de 2. Par conséquent, on peut se référer à ces matrices par l'exposant de deux ici, les appeler W(0), W(1), W(2)...

W(0)est défini comme [[1]].

Car n>0, W(n)ressemble à:

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

Il en W(1)est de même:

[[1  1]
 [1 -1]]

Et W(2)c'est:

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

Le schéma continue ...

Ta tâche

Écrivez un programme ou une fonction qui prend en entrée un entier net imprime / retourne W(n)dans n'importe quel format pratique. Cela peut être un tableau de tableaux, un tableau aplati de booléens, une .svgimage, vous l' appelez, tant qu'elle est correcte.

Les failles standard sont interdites.

Quelques choses:

Car W(0), il 1n'est pas nécessaire d'envelopper une seule fois. Il peut s'agir d'un simple entier.

Vous êtes autorisé à 1 indexer les résultats - W(1)serait alors [[1]].

Cas de test

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

C'est le code-golf , donc la solution la plus courte dans chaque langue gagne! Bon golf!

Perl 6 , 63 44 40 octets

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

Essayez-le en ligne!

Approche non récursive, exploitant le fait que la valeur aux coordonnées x, y est (-1)**popcount(x&y). Renvoie un tableau aplati de booléens.

-4 octets grâce à l' astuce de parité des bits de xnor .

MATL , 4 octets

W4YL

Essayez-le en ligne!

Comment ça marche:

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

Sans le intégré: 11 octets

1i:"th1M_hv

Essayez-le en ligne!

Comment ça marche :

Pour chaque matrice Walsh W , la matrice suivante est calculée comme [ W W ; W - W ], comme décrit dans le défi. Le code fait cela nfois, à partir de la matrice 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 octets

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

Essayez-le en ligne! Ceci implémente la construction récursive donnée.

-1 octet grâce à Ørjan Johansen !

Octave avec intégré, 18 17 octets

@(x)hadamard(2^x)

Essayez-le en ligne!

Octave sans intégré, 56 51 47 octets

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

Essayez-le en ligne! Merci à @Luis Mendo pour -4.

Octave avec lambda récursif, 54 53 52 48 octets

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

Essayez-le en ligne! Merci à cette réponse et à cette question d'inspiration.

APL (Dyalog Unicode) , 12 octets

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

Essayez-le en ligne!

La sortie est un tableau à 2 dimensions.

Python 2 , 75 71 octets

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

Essayez-le en ligne!

La matrice de Walsh semble être liée aux mauvais nombres. Si x&y(au niveau du bit et coordonnées basées sur 0) est un nombre mauvais, la valeur dans la matrice est 1, -1pour les nombres odieux. Le calcul de la parité des bits int(bin(n),13)%2est tiré du commentaire de Noodle9 sur cette réponse .

R , 61 56 53 50 octets

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

Essayez-le en ligne!

Calcule récursivement la matrice par produit Kronecker, et renvoie 1 pour le n=0cas (merci à Giuseppe pour l'avoir signalé, et aussi à JAD pour avoir aidé à jouer au golf la version initiale).

Encore 3 octets supplémentaires grâce à Giuseppe.

Gelée , 14 octets

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

Essayez-le en ligne!

Modifiez le Gpour ŒṘen bas de page pour voir la sortie réelle.

JavaScript (ES6), 77 octets

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

Le calcul naïf commence par prendre 0 <= X, Y <= 2**Nen W[N]. Le cas simple est quand Xou Yest inférieur à 2**(N-1), auquel cas nous récursions sur X%2**(N-1)et Y%2**(N-1). Dans le cas des deux Xet Yétant au moins 2**(N-1)l'appel récursif doit être annulé.

Si plutôt que de comparer Xou Ymoins qu'un 2**(N-1)masque de bits X&Y&2**(N-1)est pris, il est différent de zéro lorsque l'appel récursif doit être annulé et nul dans le cas contraire. Cela évite également d'avoir à réduire le modulo 2**(N-1).

Les bits peuvent bien sûr être testés dans l'ordre inverse pour le même résultat. Ensuite, plutôt que de doubler le masque binaire à chaque fois que nous coordonnées, il peut être divisé par deux à la place, permettant aux résultats d'être XOR, ce qui 0signifie qu'un résultat final signifie aucune négation et 1signifie la négation.

Pari / GP , 41 octets

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

Essayez-le en ligne!

K (ngn / k) , 18 octets

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

Essayez-le en ligne!

05AB1E , 16 octets

oFoL<N&b0м€g®smˆ

Essayez-le en ligne!

Explication

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

Je souhaite que je connaissais un moyen plus court de calculer le poids de Hamming.
1δ¢˜est de la même longueur que 0м€g.

Husk , 13 octets

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

Essayez-le en ligne!

1 indexé.

Explication

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

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

Essayez-le en ligne!

Python 2 , 80 79 octets

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

Essayez-le en ligne!

Python 2 , 49 octets

Présentant quelques approches à l'aide de bibliothèques supplémentaires. Celui-ci s'appuie sur un Scipy intégré:

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

Essayez-le en ligne!

Python 2 , 65 octets

Et celui-ci utilise uniquement Numpy, et résout par produit Kronecker, de manière analogue à ma réponse R :

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

Essayez-le en ligne!

Stax , 20 octets

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

Exécutez-le et déboguez-le sur staxlang.xyz!

Je pensais essayer mon propre défi après un certain temps. Approche non récursive. Pas trop compétitif par rapport aux autres langues de golf ...

Déballé (24 octets) et explication

|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