Eine Walsh-Matrix ist eine spezielle Art von Quadratmatrix mit Anwendungen im Quanten-Computing (und wahrscheinlich auch anderswo, aber ich kümmere mich nur um das Quanten-Computing).

Eigenschaften von Walsh-Matrizen

Die Abmessungen sind die gleiche Potenz von 2 Deshalb haben wir auf diese Matrizen durch Zweier-Exponenten hier beziehen können, rufen sie W(0), W(1), W(2)...

W(0)ist definiert als [[1]].

Für n>0, W(n)wie folgt aussieht:

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

So W(1)ist es auch:

[[1  1]
 [1 -1]]

Und W(2)ist:

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

Das Muster geht weiter ...

Deine Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die als Eingabe eine Ganzzahl verwendet nund W(n)in einem beliebigen Format ausgibt bzw. zurückgibt . Dies kann ein Array von Arrays sein, ein abgeflachtes Array von Booleschen Werten, ein .svgBild, wie Sie es nennen, solange es korrekt ist.

Standardlücken sind verboten.

Ein paar Dinge:

Denn W(0)das 1muss nicht einmal gewickelt werden. Es kann eine ganze Zahl sein.

Es ist Ihnen gestattet, die Ergebnisse mit einem Index W(1)zu versehen [[1]].

Testfälle

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

Das ist Code-Golf , also gewinnt die kürzeste Lösung in jeder Sprache! Viel Spaß beim Golfen!

Perl 6 , 63 44 40 Bytes

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

Probieren Sie es online!

Nicht-rekursiver Ansatz, der die Tatsache ausnutzt, dass der Wert bei den Koordinaten x, y ist (-1)**popcount(x&y). Gibt ein abgeflachtes Array von Booleschen Werten zurück.

-4 Bytes dank xnor ‚s - Bit - Parität Trick .

MATL , 4 Bytes

W4YL

Probieren Sie es online!

Wie es funktioniert:

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

Ohne den eingebauten: 11 Bytes

1i:"th1M_hv

Probieren Sie es online!

Wie es funktioniert :

Für jede Walsh-Matrix W wird die nächste Matrix berechnet als [ W W ; W - W ], wie in der Challenge beschrieben. Der Code macht das nmal, ausgehend von der 1 × 1-Matrix [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]]!!)

Probieren Sie es online! Dies implementiert die angegebene rekursive Konstruktion.

-1 Byte danke an Ørjan Johansen !

Oktave mit eingebauten, 18 17 Bytes

@(x)hadamard(2^x)

Probieren Sie es online!

Oktave ohne eingebauten, 56 51 47 Bytes

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

Probieren Sie es online! Danke an @Luis Mendo für -4.

Oktave mit rekursivem Lambda, 54 53 52 48 Bytes

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

Probieren Sie es online! Dank dieser Antwort und dieser Frage zur Inspiration.

APL (Dyalog Unicode) , 12 Byte

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

Probieren Sie es online!

Die Ausgabe ist ein zweidimensionales Array.

Python 2 , 75 71 Bytes

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

Probieren Sie es online!

Die Walsh-Matrix scheint mit den bösen Zahlen verwandt zu sein. Wenn x&y(bitweise und 0 basierte Koordinaten) ein Übel Zahl ist, ist der Wert in der Matrix 1, -1für odious Zahlen. Die Bitparitätsberechnungint(bin(n),13)%2 stammt aus Noodle9s Kommentar zu dieser Antwort .

R , 61 56 53 50 Bytes

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

Probieren Sie es online!

Berechnet rekursiv die Matrix nach Kronecker-Produkt und gibt 1 für den n=0Fall zurück (danke an Giuseppe für den Hinweis und auch an JAD für die Unterstützung beim Golfen der ursprünglichen Version).

Nochmals zusätzliche -3 Bytes dank Giuseppe.

Jelly , 14 Bytes

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

Probieren Sie es online!

Ändern Sie das Gin ŒṘin der Fußzeile, um die tatsächliche Ausgabe anzuzeigen.

JavaScript (ES6), 77 Byte

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

Die naive Berechnung beginnt , indem sie 0 <= X, Y <= 2**Nin W[N]. Der einfache Fall ist, wenn entweder Xoder Ykleiner ist als 2**(N-1), in welchem ​​Fall wir auf X%2**(N-1)und zurückgreifen Y%2**(N-1). Im Fall der beiden Xund Ywobei zumindest 2**(N-1)der rekursive Aufruf muss negiert werden.

Wenn anstatt zu vergleichen Xoder Yweniger als 2**(N-1)eine Bitmaske verwendet X&Y&2**(N-1)wird, ist diese ungleich Null, wenn der rekursive Aufruf negiert werden muss, und Null, wenn dies nicht der Fall ist. Dies vermeidet auch, dass Modulo reduziert werden muss 2**(N-1).

Die Bits können natürlich in umgekehrter Reihenfolge für das gleiche Ergebnis getestet werden. Anstatt die Bitmaske jedes Mal zu verdoppeln, wenn wir sie koordinieren, kann sie stattdessen halbiert werden, wodurch die Ergebnisse XOR-verknüpft werden können, wobei ein Endergebnis von 0keine Negation und 1Negation bedeutet.

Pari / GP , 41 Bytes

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

Probieren Sie es online!

K (ngn / k) , 18 Bytes

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

Probieren Sie es online!

05AB1E , 16 Bytes

oFoL<N&b0м€g®smˆ

Probieren Sie es online!

Erläuterung

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

Ich wünschte, ich wüsste einen kürzeren Weg, um das Hamming-Gewicht zu berechnen.
1δ¢˜ist die gleiche Länge wie 0м€g.

Schale , 13 Bytes

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

Probieren Sie es online!

1-indiziert.

Erläuterung

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

Probieren Sie es 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)]

Probieren Sie es online!

Python 2 , 49 Bytes

Darstellung einiger Ansätze unter Verwendung zusätzlicher Bibliotheken. Dieser stützt sich auf einen in Scipy eingebauten:

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

Probieren Sie es online!

Python 2 , 65 Bytes

Und dieser verwendet nur Numpy und löst nach Kronecker-Produkt, analog zu meiner R-Antwort :

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

Probieren Sie es online!

Stax , 20 Bytes

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

Führen Sie es aus und debuggen Sie es unter staxlang.xyz!

Ich dachte, ich würde meine eigene Herausforderung nach einiger Zeit versuchen. Nicht rekursiver Ansatz. Nicht zu konkurrenzfähig gegen andere Golfsprachen ...

Entpackt (24 Bytes) und Erklärung

|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