Walsh matrix
You are encouraged to solve this task according to the task description, using any language you may know.
| This page uses content from Wikipedia. The original article was at Walsh matrix. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
A Walsh matrix is a specific square matrix of dimensions 2n, where n is some particular natural number. The elements of the matrix are either +1 or −1 and its rows as well as columns are orthogonal, i.e. dot product is zero. Each row of a Walsh matrix corresponds to a Walsh function.
Walsh matrices are a special case of Hadamard matrices. The naturally ordered Hadamard (Walsh) matrix is defined by the recursive formula below, and the sequency-ordered Hadamard (Walsh) matrix is formed by rearranging the rows so that the number of sign changes in a row is in increasing order.
- To generate a naturally ordered Walsh matrix
Matrices of dimension 2k for k ∈ N are given by the recursive formula:
and in general
for 2 ≤ k ∈ N, where ⊗ denotes the Kronecker product.
- Task
- Write a routine that, given a natural number k, returns a naturally ordered Walsh matrix of order 2k.
- Display a few sample generated matrices.
-
- Traditionally, Walsh matrices use 1 & -1 to denote the different cell values in text mode, or green and red blocks in image mode. You may use whichever display mode is most convenient for your particular language.
- Stretch
- Also, optionally generate sequency ordered Walsh matrices.
-
- A sequency ordered Walsh matrix has the rows sorted by number of sign changes.
- See also
Ada
This solution demonstrates Ada enumerations for matrix values, for how to display the matrix (with numbers or as "red" (`#`) and green (`_`), and as array indices. It also illustrates usage of a default value of a procedure parameter.
pragma Ada_2022;
with Ada.Containers.Generic_Array_Sort;
with Ada.Text_IO;
procedure Walsh_Matrices is
package IO renames Ada.Text_IO;
-- SECTION
-- Definition of a Walsh Matrix
type Walsh_Value is (Red, Green);
Opposite : constant array (Walsh_Value) of Walsh_Value :=
[Red => Green, Green => Red];
type Walsh_Matrix is
array (Positive range <>, Positive range <>) of Walsh_Value;
-- SECTION
-- Sorting the matrix
-- In order to avail ourselves of Ada's standard library,
-- we define an auxiliary data
-- that records the number of sign changes in a given row.
-- We sort an array of **that** structure, then
-- use that to sort the matrix.
type Sort_Data_Record is record
Row : Positive;
Sign_Changes : Natural;
end record;
type Sort_Data_Array is array (Positive range <>) of Sort_Data_Record;
function "<" (Left, Right : Sort_Data_Record) return Boolean is
(Left.Sign_Changes < Right.Sign_Changes);
procedure Sort_By_Sequency is new Ada.Containers.Generic_Array_Sort
(Index_Type => Positive, Element_Type => Sort_Data_Record,
Array_Type => Sort_Data_Array);
function Number_Of_Sign_Changes
(Matrix : Walsh_Matrix; Row : Positive) return Natural
is
Result : Natural := 0;
begin
for Col in 2 .. Matrix'Last (2) loop
Result :=
@ + (if Matrix (Row, Col) = Matrix (Row, Col - 1) then 0 else 1);
end loop;
return Result;
end Number_Of_Sign_Changes;
procedure Sort_Matrix_By_Sequency (Matrix : in out Walsh_Matrix) is
Sort_Data : Sort_Data_Array (Matrix'Range (1)) :=
[for Ith in Matrix'Range (1) =>
(Row => Ith,
Sign_Changes => Number_Of_Sign_Changes (Matrix, Ith))];
Temp : Walsh_Matrix (Matrix'Range (1), Matrix'Range (2));
begin
Sort_By_Sequency (Sort_Data);
for Row in Matrix'Range (1) loop
for Col in Matrix'Range (2) loop
Temp (Row, Col) := Matrix (Sort_Data (Row).Row, Col);
end loop;
end loop;
Matrix := Temp;
end Sort_Matrix_By_Sequency;
-- SECTION
-- Displaying a Walsh Matrix
type Display is (Number, Color);
-- for the colors we imitate the Algol implementation
Output : constant array (Walsh_Value, Display) of String (1 .. 2) :=
[Red => [Number => "-1", Color => " #"],
Green => [Number => " 1", Color => " _"]];
procedure Put (W : Walsh_Matrix; Kind : Display := Number) is
begin
for Row in W'Range (1) loop
IO.Put ("( ");
for Col in W'Range (2) loop
IO.Put (Output (W (Row, Col), Kind) & " ");
end loop;
IO.Put_Line (" )");
end loop;
end Put;
-- SECTION
-- Creating a Walsh Matrix
procedure Fill (W : in out Walsh_Matrix; Row, Col, Dim : Positive) is
-- recursively fills a 2^Dim square submatrix of W,
-- starting from the given row and column
begin
if Dim = 1 then
W (Row, Col) := Green;
W (Row, Col + 1) := Green;
W (Row + 1, Col) := Green;
W (Row + 1, Col + 1) := Red;
else
Fill (W, Row, Col, Dim - 1);
Fill (W, Row, Col + 2**(Dim - 1), Dim - 1);
Fill (W, Row + 2**(Dim - 1), Col, Dim - 1);
Fill (W, Row + 2**(Dim - 1), Col + 2**(Dim - 1), Dim - 1);
for R in Row + 2**(Dim - 1) .. Row + 2**Dim - 1 loop
for C in Col + 2**(Dim - 1) .. Col + 2**Dim - 1 loop
W (R, C) := Opposite (@);
end loop;
end loop;
end if;
end Fill;
function New_Matrix (Dimension : Positive) return Walsh_Matrix is
Result : Walsh_Matrix (1 .. 2**Dimension, 1 .. 2**Dimension);
begin
Fill (Result, Result'First (1), Result'First (2), Dimension);
return Result;
end New_Matrix;
-- SECTION
-- a few values
W_1 : Walsh_Matrix := New_Matrix (1);
W_2 : Walsh_Matrix := New_Matrix (2);
W_5 : Walsh_Matrix := New_Matrix (5);
begin
Put (W_1, Color);
IO.New_Line;
Sort_Matrix_By_Sequency (W_1);
Put (W_1, Color);
IO.New_Line;
Put (W_2, Color);
IO.New_Line;
Sort_Matrix_By_Sequency (W_2);
Put (W_2, Color);
IO.New_Line;
Put (W_5, Color);
IO.New_Line;
Put (W_5);
IO.New_Line;
Sort_Matrix_By_Sequency (W_5);
Put (W_5, Color);
IO.New_Line;
end Walsh_Matrices;
- Output:
( _ _ ) ( _ # ) ( _ _ ) ( _ # ) ( _ _ _ _ ) ( _ # _ # ) ( _ _ # # ) ( _ # # _ ) ( _ _ _ _ ) ( _ _ # # ) ( _ # # _ ) ( _ # _ # ) ( _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ) ( _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # ) ( _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # ) ( _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ ) ( _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # ) ( _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ ) ( _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ ) ( _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # ) ( _ _ _ _ _ _ _ _ # # # # # # # # _ _ _ _ _ _ _ _ # # # # # # # # ) ( _ # _ # _ # _ # # _ # _ # _ # _ _ # _ # _ # _ # # _ # _ # _ # _ ) ( _ _ # # _ _ # # # # _ _ # # _ _ _ _ # # _ _ # # # # _ _ # # _ _ ) ( _ # # _ _ # # _ # _ _ # # _ _ # _ # # _ _ # # _ # _ _ # # _ _ # ) ( _ _ _ _ # # # # # # # # _ _ _ _ _ _ _ _ # # # # # # # # _ _ _ _ ) ( _ # _ # # _ # _ # _ # _ _ # _ # _ # _ # # _ # _ # _ # _ _ # _ # ) ( _ _ # # # # _ _ # # _ _ _ _ # # _ _ # # # # _ _ # # _ _ _ _ # # ) ( _ # # _ # _ _ # # _ _ # _ # # _ _ # # _ # _ _ # # _ _ # _ # # _ ) ( _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ # # # # # # # # # # # # # # # # ) ( _ # _ # _ # _ # _ # _ # _ # _ # # _ # _ # _ # _ # _ # _ # _ # _ ) ( _ _ # # _ _ # # _ _ # # _ _ # # # # _ _ # # _ _ # # _ _ # # _ _ ) ( _ # # _ _ # # _ _ # # _ _ # # _ # _ _ # # _ _ # # _ _ # # _ _ # ) ( _ _ _ _ # # # # _ _ _ _ # # # # # # # # _ _ _ _ # # # # _ _ _ _ ) ( _ # _ # # _ # _ _ # _ # # _ # _ # _ # _ _ # _ # # _ # _ _ # _ # ) ( _ _ # # # # _ _ _ _ # # # # _ _ # # _ _ _ _ # # # # _ _ _ _ # # ) ( _ # # _ # _ _ # _ # # _ # _ _ # # _ _ # _ # # _ # _ _ # _ # # _ ) ( _ _ _ _ _ _ _ _ # # # # # # # # # # # # # # # # _ _ _ _ _ _ _ _ ) ( _ # _ # _ # _ # # _ # _ # _ # _ # _ # _ # _ # _ _ # _ # _ # _ # ) ( _ _ # # _ _ # # # # _ _ # # _ _ # # _ _ # # _ _ _ _ # # _ _ # # ) ( _ # # _ _ # # _ # _ _ # # _ _ # # _ _ # # _ _ # _ # # _ _ # # _ ) ( _ _ _ _ # # # # # # # # _ _ _ _ # # # # _ _ _ _ _ _ _ _ # # # # ) ( _ # _ # # _ # _ # _ # _ _ # _ # # _ # _ _ # _ # _ # _ # # _ # _ ) ( _ _ # # # # _ _ # # _ _ _ _ # # # # _ _ _ _ # # _ _ # # # # _ _ ) ( _ # # _ # _ _ # # _ _ # _ # # _ # _ _ # _ # # _ _ # # _ # _ _ # ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( 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 ) ( _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ) ( _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ # # # # # # # # # # # # # # # # ) ( _ _ _ _ _ _ _ _ # # # # # # # # # # # # # # # # _ _ _ _ _ _ _ _ ) ( _ _ _ _ _ _ _ _ # # # # # # # # _ _ _ _ _ _ _ _ # # # # # # # # ) ( _ _ _ _ # # # # # # # # _ _ _ _ _ _ _ _ # # # # # # # # _ _ _ _ ) ( _ _ _ _ # # # # # # # # _ _ _ _ # # # # _ _ _ _ _ _ _ _ # # # # ) ( _ _ _ _ # # # # _ _ _ _ # # # # # # # # _ _ _ _ # # # # _ _ _ _ ) ( _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # ) ( _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ _ _ # # # # _ _ ) ( _ _ # # # # _ _ _ _ # # # # _ _ # # _ _ _ _ # # # # _ _ _ _ # # ) ( _ _ # # # # _ _ # # _ _ _ _ # # # # _ _ _ _ # # _ _ # # # # _ _ ) ( _ _ # # # # _ _ # # _ _ _ _ # # _ _ # # # # _ _ # # _ _ _ _ # # ) ( _ _ # # _ _ # # # # _ _ # # _ _ _ _ # # _ _ # # # # _ _ # # _ _ ) ( _ _ # # _ _ # # # # _ _ # # _ _ # # _ _ # # _ _ _ _ # # _ _ # # ) ( _ _ # # _ _ # # _ _ # # _ _ # # # # _ _ # # _ _ # # _ _ # # _ _ ) ( _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # ) ( _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ _ # # _ ) ( _ # # _ _ # # _ _ # # _ _ # # _ # _ _ # # _ _ # # _ _ # # _ _ # ) ( _ # # _ _ # # _ # _ _ # # _ _ # # _ _ # # _ _ # _ # # _ _ # # _ ) ( _ # # _ _ # # _ # _ _ # # _ _ # _ # # _ _ # # _ # _ _ # # _ _ # ) ( _ # # _ # _ _ # # _ _ # _ # # _ _ # # _ # _ _ # # _ _ # _ # # _ ) ( _ # # _ # _ _ # # _ _ # _ # # _ # _ _ # _ # # _ _ # # _ # _ _ # ) ( _ # # _ # _ _ # _ # # _ # _ _ # # _ _ # _ # # _ # _ _ # _ # # _ ) ( _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # ) ( _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ _ # _ # # _ # _ ) ( _ # _ # # _ # _ _ # _ # # _ # _ # _ # _ _ # _ # # _ # _ _ # _ # ) ( _ # _ # # _ # _ # _ # _ _ # _ # # _ # _ _ # _ # _ # _ # # _ # _ ) ( _ # _ # # _ # _ # _ # _ _ # _ # _ # _ # # _ # _ # _ # _ _ # _ # ) ( _ # _ # _ # _ # # _ # _ # _ # _ _ # _ # _ # _ # # _ # _ # _ # _ ) ( _ # _ # _ # _ # # _ # _ # _ # _ # _ # _ # _ # _ _ # _ # _ # _ # ) ( _ # _ # _ # _ # _ # _ # _ # _ # # _ # _ # _ # _ # _ # _ # _ # _ ) ( _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # _ # )
ALGOL 68
BEGIN # construct Walsh Matrices #
CO BEGIN code from the Kronecker product task CO
# multiplies in-place the elements of the matrix a by the scaler b #
OP *:= = ( REF[,]INT a, INT b )REF[,]INT:
BEGIN
FOR i FROM 1 LWB a TO 1 UPB a DO
FOR j FROM 2 LWB a TO 2 UPB a DO
a[ i, j ] *:= b
OD
OD;
a
END # *:= # ;
# returns the Kronecker Product of the two matrices a and b #
# the result will have lower bounds of 1 #
PRIO X = 6;
OP X = ( [,]INT a, b )[,]INT:
BEGIN
# normalise the matrices to have lower bounds of 1 #
[,]INT m = a[ AT 1, AT 1 ];
[,]INT n = b[ AT 1, AT 1 ];
# construct the result #
INT r 1 size = 1 UPB n;
INT r 2 size = 2 UPB n;
[ 1 : 1 UPB m * 1 UPB n, 1 : 2 UPB m * 2 UPB n ]INT k;
FOR i FROM 1 LWB m TO 1 UPB m DO
FOR j FROM 2 LWB m TO 2 UPB m DO
( k[ 1 + ( ( i - 1 ) * r 1 size ) : i * r 1 size
, 1 + ( ( j - 1 ) * r 2 size ) : j * r 2 size
] := n
) *:= m[ i, j ]
OD
OD;
k
END # X # ;
CO END code from the Kronecker product task CO
# returns a Walsh matrix of oreder n #
OP WALSH = ( INT n )[,]INT:
BEGIN
[,]INT w1 = ( ( 1, 1 )
, ( 1, -1 )
);
FLEX[ 1 : 0, 1 : 0 ]INT result := 1;
TO n DO
result := result X w1
OD;
result
END # WALSH # ;
# returns Walsh matrix a sorted into sequency order #
OP SEQUENCYSORT = ( [,]INT a )[,]INT:
BEGIN
# sort the rows of the matrix into order of the number of sign #
# changes in the row #
[,]INT w = a[ AT 1, AT 1 ]; # normalise the matrix to have #
# lower bounds of 1 #
[ 1 : 1 UPB w, 1 : 2 UPB w ]INT result;
# construct the resullt with the rows in order of the number of #
# the number of sign changes in the original #
# note the number of changes is unique and in 0 .. UPB a - 1 #
FOR row FROM 1 TO 1 UPB w DO
INT changes := 0;
INT curr := w[ row, 1 ];
FOR col FROM 2 TO 2 UPB w DO
IF curr /= w[ row, col ] THEN
changes +:= 1;
curr := w[ row, col ]
FI
OD;
result[ changes + 1, : ] := w[ row, : ]
OD;
result
END # SEQUENCYSORT # ;
CO returns r encoded with 1 = "_" and -1 = "#" CO
OP TOWSTRING = ( []INT r )STRING:
BEGIN
STRING result := "";
FOR j FROM LWB r TO UPB r DO
result +:= IF r[ j ] > 0 THEN "_" ELSE "#" FI
OD;
result
END # TOWSTRING # ;
# show the natural order and sequency order Walsh matrices of order 5 #
[,]INT w5 = WALSH 5;
[,]INT s5 = SEQUENCYSORT w5;
FOR row FROM 1 TO 1 UPB s5 DO
print( ( TOWSTRING w5[ row, : ], " ", TOWSTRING s5[ row, : ], newline ) )
OD
END- Output:
________________________________ ________________________________ _#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_# ________________################ __##__##__##__##__##__##__##__## ________################________ _##__##__##__##__##__##__##__##_ ________########________######## ____####____####____####____#### ____########________########____ _#_##_#__#_##_#__#_##_#__#_##_#_ ____########____####________#### __####____####____####____####__ ____####____########____####____ _##_#__#_##_#__#_##_#__#_##_#__# ____####____####____####____#### ________########________######## __####____####____####____####__ _#_#_#_##_#_#_#__#_#_#_##_#_#_#_ __####____####__##____####____## __##__####__##____##__####__##__ __####__##____####____##__####__ _##__##_#__##__#_##__##_#__##__# __####__##____##__####__##____## ____########________########____ __##__####__##____##__####__##__ _#_##_#_#_#__#_#_#_##_#_#_#__#_# __##__####__##__##__##____##__## __####__##____##__####__##____## __##__##__##__####__##__##__##__ _##_#__##__#_##__##_#__##__#_##_ __##__##__##__##__##__##__##__## ________________################ _##__##__##__##__##__##__##__##_ _#_#_#_#_#_#_#_##_#_#_#_#_#_#_#_ _##__##__##__##_#__##__##__##__# __##__##__##__####__##__##__##__ _##__##_#__##__##__##__#_##__##_ _##__##__##__##_#__##__##__##__# _##__##_#__##__#_##__##_#__##__# ____####____########____####____ _##_#__##__#_##__##_#__##__#_##_ _#_##_#__#_##_#_#_#__#_##_#__#_# _##_#__##__#_##_#__#_##__##_#__# __####____####__##____####____## _##_#__#_##_#__##__#_##_#__#_##_ _##_#__#_##_#__##__#_##_#__#_##_ _##_#__#_##_#__#_##_#__#_##_#__# ________################________ _#_##_#__#_##_#__#_##_#__#_##_#_ _#_#_#_##_#_#_#_#_#_#_#__#_#_#_# _#_##_#__#_##_#_#_#__#_##_#__#_# __##__####__##__##__##____##__## _#_##_#_#_#__#_##_#__#_#_#_##_#_ _##__##_#__##__##__##__#_##__##_ _#_##_#_#_#__#_#_#_##_#_#_#__#_# ____########____####________#### _#_#_#_##_#_#_#__#_#_#_##_#_#_#_ _#_##_#_#_#__#_##_#__#_#_#_##_#_ _#_#_#_##_#_#_#_#_#_#_#__#_#_#_# __####__##____####____##__####__ _#_#_#_#_#_#_#_##_#_#_#_#_#_#_#_ _##_#__##__#_##_#__#_##__##_#__# _#_#_#_#_#_#_#_#_#_#_#_#_#_#_#_#
C++
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
void display(const std::vector<std::vector<int32_t>>& matrix) {
for ( const std::vector<int32_t>& row : matrix ) {
for ( const int32_t& element : row ) {
std::cout << std::setw(3) << element;
}
std::cout << std::endl;;
}
std::cout << std::endl;;
}
uint32_t sign_change_count(const std::vector<int32_t>& row) {
uint32_t sign_changes = 0;
for ( uint64_t i = 1; i < row.size(); ++i ) {
if ( row[i - 1] == -row[i] ) {
sign_changes++;
}
}
return sign_changes;
}
std::vector<std::vector<int32_t>> walsh_matrix(const uint32_t& size) {
std::vector<std::vector<int32_t>> walsh = { size, std::vector<int32_t>(size, 0) };
walsh[0][0] = 1;
uint32_t k = 1;
while ( k < size ) {
for ( uint32_t i = 0; i < k; ++i ) {
for ( uint32_t j = 0; j < k; ++j ) {
walsh[i + k][j] = walsh[i][j];
walsh[i][j + k] = walsh[i][j];
walsh[i + k][j + k] = -walsh[i][j];
}
}
k += k;
}
return walsh;
}
int main() {
for ( const std::string type : { "Natural", "Sequency" } ) {
for ( const uint32_t order : { 2, 4, 5 } ) {
uint32_t size = 1 << order;
std::cout << "Walsh matrix of order " << order << ", " << type << " order:" << std::endl;
std::vector<std::vector<int32_t>> walsh = walsh_matrix(size);
if ( type == "Sequency" ) {
std::sort(walsh.begin(), walsh.end(),
[](const std::vector<int32_t> &row1, const std::vector<int32_t> &row2) {
return sign_change_count(row1) < sign_change_count(row2);
});
}
display(walsh);
}
}
}
- Output:
Walsh matrix of order 2, Natural order: 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix of order 4, Natural order: 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 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 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 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 Walsh matrix of order 5, Natural order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Walsh matrix of order 2, Sequency order: 1 1 1 1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 Walsh matrix of order 4, Sequency order: 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 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 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 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 Walsh matrix of order 5, Sequency order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
EasyLang
proc out w[][] . .
numfmt 0 3
for i to len w[][]
for j to len w[i][]
write w[i][j]
.
print ""
.
print ""
numfmt 0 0
.
proc walshmatr ord . .
n = pow 2 ord
len walsh[][] n
for i to n
len walsh[i][] n
.
walsh[1][1] = 1
k = 1
while k < n
for i = 1 to k
for j = 1 to k
walsh[i + k][j] = walsh[i][j]
walsh[i][j + k] = walsh[i][j]
walsh[i + k][j + k] = -walsh[i][j]
.
.
k *= 2
.
print "Walsh matrix of order " & ord
out walsh[][]
.
walshmatr 2
walshmatr 4
- Output:
Walsh matrix of order 2 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix of order 4 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 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 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 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
F#
// Walsh matrix. Nigel Galloway: August 31st., 2023
open MathNet.Numerics
open MathNet.Numerics.LinearAlgebra
let walsh()=let w2=matrix [[1.0;1.0];[1.0;-1.0]] in Seq.unfold(fun n->Some(n,w2.KroneckerProduct n)) w2
walsh() |> Seq.take 5 |> Seq.iter(fun n->printfn "%s" (n.ToMatrixString()))
- Output:
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 -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 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 -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 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 -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 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 -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
Factor
USING: accessors formatting images.processing images.testing
images.viewer kernel math math.matrices math.matrices.extras
sequences sequences.extras sorting.extras ui ui.gadgets
ui.gadgets.borders ui.gadgets.labeled ui.gadgets.packs ;
IN: walsh
CONSTANT: walsh1 { { 1 1 } { 1 -1 } }
CONSTANT: red B{ 0 255 0 }
CONSTANT: green B{ 255 0 0 }
: walsh ( n -- seq )
1 - walsh1 tuck '[ _ kronecker-product ] times ;
: sequency ( n -- seq )
walsh [ dup rest-slice [ = not ] 2count ] map-sort ;
: seq>bmp ( seq -- newseq )
concat [ 1 = red green ? ] B{ } map-concat-as ;
: seq>img ( seq -- image )
dup dimension <rgb-image> swap >>dim swap seq>bmp >>bitmap ;
: <img> ( seq -- gadget )
dup length 256 swap / matrix-zoom seq>img <image-gadget> ;
: info ( seq -- str )
length dup log2 swap dup "Order %d (%d x %d)" sprintf ;
: <info-img> ( seq -- gadget )
[ <img> ] [ info ] bi <labeled-gadget> ;
: <pile-by> ( seq quot -- gadget )
<pile> -rot [ <info-img> add-gadget ] compose each ; inline
: <natural> ( -- gadget )
{ 2 4 5 } [ walsh ] <pile-by> "Natural ordering"
<labeled-gadget> ;
: <sequency> ( -- gadget )
{ 2 4 5 } [ sequency ] <pile-by> "Sequency ordering"
<labeled-gadget> ;
: <walsh> ( -- gadget )
<shelf> <natural> { 3 0 } <border> add-gadget
<sequency> { 3 0 } <border> add-gadget ;
MAIN: [ <walsh> "Walsh matrices" open-window ]
- Output:
FreeBASIC
REM Text mode version.
Sub Imprime(w() As Integer)
Dim As Integer i, j, ub = Ubound(w)
Print "Walsh matrix - order " & Fix(Sqr(ub)) & " (" & ub & "x" & ub & "), Natural order:"
For i = 0 To ub-1
For j = 0 To ub-1
Print Using "###"; w(i, j);
Next j
Print
Next i
Print
End Sub
Sub WalshMatrix(n As Integer)
Dim walsh(0 To n, 0 To n) As Integer
walsh(0,0) = 1
Dim As Integer i, j, k
k = 1
While k < n
For i = 0 To k-1
For j = 0 To k-1
walsh(i+k, j) = walsh(i, j)
walsh(i, j+k) = walsh(i, j)
walsh(i+k, j+k) = -walsh(i, j)
Next j
Next i
k *= 2
Wend
Imprime(walsh())
End Sub
Dim As Integer n = 4
n = 4: WalshMatrix(n)
n = 16: WalshMatrix(n)
n = 32: WalshMatrix(n)
Sleep
- Output:
Walsh matrix - order 2 (4x4), Natural order: 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix - order 4 (16x16), Natural order: 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 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 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 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 Walsh matrix - order 5 (32x32), Natural order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
J
kp1=: [: ,./^:2 */ NB. Victor Cerovski, 2010-02-26
walsh=: {{(_1^3=i.2 2)&kp1^:y 1}}
sequencyorder=: /: 2 ~:/\"1 ]
Small examples (time is not an issue here, but page estate is an issue):
walsh 0
1
walsh 1
1 1
1 _1
walsh 2
1 1 1 1
1 _1 1 _1
1 1 _1 _1
1 _1 _1 1
walsh 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
sequencyorder walsh 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
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public final class WalshMatrix {
public static void main(String[] args) {
for ( String type : List.of( "Natural", "Sequency" ) ) {
for ( int order : List.of( 2, 4, 5 ) ) {
int size = 1 << order;
System.out.println("Walsh matrix of order " + order + ", " + type + " order:");
List<List<Integer>> walsh = walshMatrix(size);
if ( type.equals("Sequency") ) {
Collections.sort(walsh, rowComparator);
}
display(walsh);
}
}
}
private static List<List<Integer>> walshMatrix(int size) {
List<List<Integer>> walsh = IntStream.range(0, size).boxed()
.map( i -> new ArrayList<Integer>(Collections.nCopies(size, 0)) ).collect(Collectors.toList());
walsh.get(0).set(0, 1);
int k = 1;
while ( k < size ) {
for ( int i = 0; i < k; i++ ) {
for ( int j = 0; j < k; j++ ) {
walsh.get(i + k).set(j, walsh.get(i).get(j));
walsh.get(i).set(j + k, walsh.get(i).get(j));
walsh.get(i + k).set(j + k, -walsh.get(i).get(j));
}
}
k += k;
}
return walsh;
}
private static int signChangeCount(List<Integer> row) {
int signChanges = 0;
for ( int i = 1; i < row.size(); i++ ) {
if ( row.get(i - 1) == -row.get(i) ) {
signChanges += 1;
}
}
return signChanges;
}
private static Comparator<List<Integer>> rowComparator =
(one, two) -> Integer.compare(signChangeCount(one), signChangeCount(two));
private static void display(List<List<Integer>> matrix) {
for ( List<Integer> row : matrix ) {
for ( int element : row ) {
System.out.print(String.format("%3d", element));
}
System.out.println();
}
System.out.println();
}
}
- Output:
Walsh matrix of order 2, Natural order: 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix of order 4, Natural order: 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 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 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 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 Walsh matrix of order 5, Natural order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Walsh matrix of order 2, Sequency order: 1 1 1 1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 Walsh matrix of order 4, Sequency order: 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 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 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 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 Walsh matrix of order 5, Sequency order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
Works with jaq, the Rust implementation of jq
This entry uses a non-recursive method for creating Walsh matrices, but the `kprod` definition at Kronecker_product#jq could also be used as follows:
## Generate a Walsh matrix of size 2^$n for $n >= 1
def walsh:
. as $n
| [[1, 1], [1, -1]] as $w2
| if $n < 2 then $w2 else kprod($w2; $n - 1 | walsh) end;## Generic matrix functions
# Create an m x n matrix
def matrix(m; n; init):
if m == 0 then []
elif m == 1 then [range(0;n) | init]
elif m > 0 then
matrix(1;n;init) as $row
| [range(0;m) | $row ]
else error("matrix\(m);_;_) invalid")
end;
# Input: a numeric array
def signChanges:
def s: if . > 0 then 1 elif . < 0 then -1 else 0 end;
. as $row
| reduce range(1;length) as $i (0;
if ($row[$i-1]|s) == -($row[$i]|s) then . + 1 else . end );
# Print a matrix of integers
# $width is the minimum width to use per cell
def mprint($width):
def max(s): reduce s as $x (null; if . == null or $x > . then $x else . end);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
(max($width, (.[][] | tostring | length) + 1)) as $w
| . as $in
| range(0; length) as $i
| reduce range(0; .[$i]|length) as $j ("|"; . + ($in[$i][$j]|lpad($w)))
| . + " |" ;
def cprint:
. as $in
| range(0; length) as $i
| reduce range(0; .[$i]|length) as $j (""; . + ($in[$i][$j]));
def color: if . == 1 then "🟥" else "🟩" end;Walsh matrices
def walshMatrix:
. as $n
| { walsh: matrix($n; $n; 0) }
| .walsh[0][0] = 1
| .k = 1
| until (.k >= $n;
.k as $k
| reduce range (0; $k) as $i (.;
reduce range (0; $k) as $j (.;
.walsh[$i][$j] as $wij
| .walsh[$i+$k][$j] = $wij
| .walsh[$i][$j+$k] = $wij
| .walsh[$i+$k][$j+$k] = -$wij ))
| .k += .k )
| .walsh ;
## The tasks
def task1:
(2, 4, 5) as $order
| pow(2; $order)
| "Walsh matrix - order \($order) (\(.) x \(.)), natural order:",
(walshMatrix | mprint(2)),
"";
def task2:
(2, 4, 5) as $order
| pow(2; $order)
| "Walsh matrix - order \($order) (\(.) x \(.)), sequency order:",
(walshMatrix | sort_by( signChanges ) | mprint(2)),
"";
def task3:
5 as $order
| pow(2; $order)
| "Walsh matrix - order \($order) (\(.) x \(.)), natural order:",
(walshMatrix | map(map(color)) | cprint),
"";
def task4:
5 as $order
| pow(2; $order)
| "Walsh matrix - order \($order) (\(.) x \(.)), sequency order:",
(walshMatrix | sort_by( signChanges ) | map(map(color)) | cprint),
"";
task1, task2, task3, task4- Output:
The output for the first two tasks is essentially as for Wren. The output for the last two tasks is as follows:
Walsh matrix - order 5 (32 x 32), natural order: 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥 🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩 🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩 🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥 🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩 🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥 🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥 🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩 🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩 🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥 🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥 🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩 🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥 🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩 🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩 🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩 🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥 🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥 🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩 🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥 🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩 🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩 🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥 🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥 🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩 🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩 🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥 🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩 🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥 🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥 🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩 Walsh matrix - order 5 (32 x 32), sequency order: 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥 🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩 🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥 🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩 🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥 🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟥🟥🟥🟥🟩🟩🟩🟩 🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥 🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩 🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥 🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩 🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥 🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩 🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥 🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟥🟥🟩🟩🟥🟥🟩🟩 🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥 🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩 🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥 🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩 🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥 🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩 🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥 🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟥🟩🟩🟥🟩🟥🟥🟩 🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥 🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩 🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥 🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩 🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥 🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩 🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥 🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟥🟩🟥🟩🟥🟩🟥🟩 🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥 🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩🟥🟩
Julia
kron is a builtin function in Julia.
julia>using Plots
const w2 = [1 1; 1 -1]
walsh(k) = k < 2 ? w2 : kron(w2, walsh(k - 1))
countsignchanges(r) = count(i -> sign(r[i-1]) != sign(r[i[]]), 2:lastindex(r))
sequency(m) = sortslices(m, dims = 1, by = countsignchanges)
display(walsh(2))
display(walsh(3))
display(walsh(4))
display(sequency(walsh(3)))
display(sequency(walsh(4)))
subplots = [
heatmap(
(i ? sequency : identity)(walsh(n)),
ylims = [0, 2^n + 1],
xlims = [0, 2^n + 1],
aspect_ratio = :equal,
legend = false,
axis = false,
colormap = [:red, :forestgreen],
yflip = true,
) for i = false:true, n = 3:5
]
plot(
subplots...,
plot_title = "Walsh, Natural Order" * "\u2007"^20 * "Walsh, Sequency Order",
plot_titlefont = (9, "times"),
layout = @layout [a b; c d; e f]
)
- Output:
4×4 Matrix{Int64}:
1 1 1 1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 1
8×8 Matrix{Int64}:
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
16×16 Matrix{Int64}:
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
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
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
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×8 Matrix{Int64}:
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
16×16 Matrix{Int64}:
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
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
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
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
Mathematica /Wolfram Language
WalshMatrix = Nest[ArrayFlatten@{{#, #}, {#, -#}} &, 1, #] &;
WalshMatrix[4] // MatrixPlot
- Output:
MATLAB
walsh=@(x)hadamard(2^x);
imagesc(walsh(4));
Maxima
Using altern_kronecker as defined in Kronecker product task
/* Function that attempts to implement recursion but only works for n when already called for every antecessor */
auxwalsh(n):=if n=1 then w[1]:matrix([1,1],[1,-1]) else
block(w[2]:matrix([1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]),w[n]:altern_kronecker(w[1],w[n-1]),w[n])$
/* Function that guarantees an output for integer n */
walsh(n):=block(makelist(auxwalsh(i),i,1,n),last(%%))$
/* Examples */
walsh(4)$
wxdraw2d(palette = [red,gray,green], image(%,0,0,30,30))$
walsh(6)$
wxdraw2d(palette = [red,gray,green], image(%,0,0,30,30))$
Perl
#!/usr/bin/perl
use strict; # https://www.rosettacode.org/wiki/Walsh_matrix
use warnings;
use List::AllUtils qw( bundle_by pairwise nsort_by );
sub Kronecker
{
my ($ac, $bc) = map scalar($_->[0]->@*), my ($A, $B) = @_;
return [ bundle_by { [ @_ ] } $ac * $bc, pairwise { $a * $b }
@{[ map { map { ($_) x $bc } (@$_) x @$B } @$A ]}, # left side
@{[ ( map { (@$_) x $ac } @$B ) x @$A ]} ]; # right side
}
sub Walsh # Task - write a routine that, given k, returns Walsh of 2**k
{
my $k = shift;
$k > 0 ? Kronecker [ [1,1],[1,-1] ], Walsh( $k - 1 ) : [[1]];
}
for my $k ( 1, 3, 2, 4 ) # test code out of order just for fun
{
printf '%3d'x@$_ . "\n", @$_ for [], (my $w = Walsh($k))->@*, [];
print nsort_by { scalar(() = /(.)\1*/g) }
map { join '', (0, '_', '#')[@$_], "\n" } $w->@*;
}
- Output:
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 -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 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 -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 -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 1 1 -1 -1 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 1 -1 -1 1 ________________ ________######## ____########____ ____####____#### __####____####__ __####__##____## __##__####__##__ __##__##__##__## _##__##__##__##_ _##__##_#__##__# _##_#__##__#_##_ _##_#__#_##_#__# _#_##_#__#_##_#_ _#_##_#_#_#__#_# _#_#_#_##_#_#_#_ _#_#_#_#_#_#_#_#
Phix
You can run this online here. Use the keys '1'..'7' to change the order, limited to min 4 pixels per square, but you can resize/maximise the window, and the 's' key to toggle between natural and sequency order.
with javascript_semantics
requires("1.0.5")
function walsh_matrix(integer n)
sequence walsh = repeat(repeat(0,n),n)
walsh[1, 1] = 1
integer k = 1
while k < n do
for i=1 to k do
for j=1 to k do
integer wij = walsh[i, j]
walsh[i+k, j ] = wij
walsh[i , j+k] = wij
walsh[i+k, j+k] = -wij
end for
end for
k *= 2
end while
return walsh
end function
function sign_changes(sequence row)
integer n = length(row)
return sum(sq_eq(row[1..n-1],sq_mul(row[2..n],-1)))
end function
--/* -- console version:
for natural in {true,false} do
for order in {2, 4, 5} do
integer n = power(2,order)
printf(1,"Walsh matrix - order %d (%d x %d), %s order:\n", {order, n, n, iff(natural?"natural":"sequency")})
sequence w = walsh_matrix(n)
if not natural then
w = extract(w,custom_sort(apply(w,sign_changes),tagset(n)))
end if
pp(w,{pp_Nest,1,pp_IntFmt,"%2d",pp_Maxlen,132})
end for
end for
--*/
include xpGUI.e
integer order = 2, natural = true
procedure redraw(gdx canvas)
integer {w,h} = gGetAttribute(canvas,"SIZE"),
mwh = min(w,h), n
gCanvasRect(canvas,0,w,0,h,true,colour:=XPG_PARCHMENT)
while true do
n = power(2,order)
if n<=(floor(mwh/4)) then exit end if
order -= 1
end while
string o = iff(natural?"natural":"sequency")
gSetAttribute(gGetDialog(canvas),"TITLE","Walsh matrix order %d, %s order",{order,o})
sequence m = walsh_matrix(n)
if not natural then
m = extract(m,custom_sort(apply(m,sign_changes),tagset(n)))
end if
integer s = floor(mwh/n), xm = floor((w-s*n)/2), ym = floor((h-s*n)/2)
for i=1 to n do
for j=1 to n do
integer mij = m[i,j],
c = iff(mij=1?XPG_LIGHT_GREEN:XPG_RED),
x = (i-1)*s+xm,
y = (j-1)*s+ym
gCanvasRect(canvas,x,x+s,y,y+s,true,colour:=c)
gCanvasRect(canvas,x,x+s,y,y+s,false,colour:=XPG_BLACK)
end for
end for
end procedure
function key_handler(gdx dlg, integer c)
if c>='1' and c<='7' then
order = c-'0' -- (may be limited within redraw())
gRedraw(dlg)
return XPG_IGNORE
elsif lower(c)='s' then
natural = not natural
gRedraw(dlg)
end if
return XPG_CONTINUE
end function
gdx canvas = gCanvas(redraw),
dialog = gDialog(canvas,`gCanvas`,`SIZE=370x400`)
gSetAttribute(canvas,"BGCLR",XPG_PARCHMENT)
gSetHandler(dialog,`KEY`,key_handler)
gShow(dialog)
gMainLoop()
Python
#!/usr/bin/env python3
def display(matrix):
for row in matrix:
print(' '.join(f" {element}" if element > 0 else f"{element}" for element in row))
print()
def sign_change_count(row):
sign_changes = 0
for i in range(1, len(row)):
if row[i - 1] == -row[i]:
sign_changes += 1
return sign_changes
def walsh_matrix(size):
walsh = [[0 for _ in range(size)] for _ in range(size)]
walsh[0][0] = 1
k = 1
while k < size:
for i in range(k):
for j in range(k):
walsh[i + k][j] = walsh[i][j]
walsh[i][j + k] = walsh[i][j]
walsh[i + k][j + k] = -walsh[i][j]
k += k
return walsh
def main():
for order in [2, 4, 5]:
size = 1 << order
for order_type in ["Natural", "Sequency"]:
print(f"Walsh matrix of order {order}, {order_type} order:")
walsh = walsh_matrix(size)
if order_type == "Sequency":
walsh.sort(key=sign_change_count)
display(walsh)
if __name__ == "__main__":
main()
- Output:
Walsh matrix of order 2, Natural order: 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix of order 2, Sequency order: 1 1 1 1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 Walsh matrix of order 4, Natural order: 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 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 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 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 Walsh matrix of order 4, Sequency order: 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 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 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 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 Walsh matrix of order 5, Natural order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Walsh matrix of order 5, Sequency order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
Raku
sub walsh (\m) { (map {$_?? -1 !! ' 1'}, map { :3(.base: 2) % 2 }, [X+&] ^2**m xx 2 ).batch: 2**m }
sub natural (@row) { Same }
sub sign-changes (@row) { sum (1..^@row).map: { 1 if @row[$_] !== @row[$_ - 1] } }
use SVG;
for &natural, 'natural', &sign-changes, 'sequency' -> &sort, $sort {
for 2,4,5 -> $order {
# ASCII text
.put for "\nWalsh matrix - order $order ({exp($order,2)} x {exp($order,2)}), $sort order:", |walsh($order).sort: &sort;
# SVG image
my $side = 600;
my $scale = $side / 2**$order;
my $row = 0;
my @blocks;
my %C = ' 1' => '#0F0', '-1' => '#F00';
for walsh($order).sort: &sort -> @row {
my \x = $row++ * $scale;
for @row.kv {
my \y = $^k * $scale;
@blocks.push: (:rect[:x(x),:y(y),:width($scale),:height($scale),:fill(%C{$^v})]);
}
}
"walsh-matrix--order-{$order}--{$sort}-sort-order--raku.svg".IO.spurt:
SVG.serialize(:svg[:width($side),:height($side),:stroke<black>,:stroke-width<1>,|@blocks])
}
}
- Output:
Walsh matrix - order 2 (4 x 4), natural order: 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 Walsh matrix - order 4 (16 x 16), natural order: 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 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 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 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 Walsh matrix - order 5 (32 x 32), natural order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Walsh matrix - order 2 (4 x 4), sequency order: 1 1 1 1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 Walsh matrix - order 4 (16 x 16), sequency order: 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 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 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 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 Walsh matrix - order 5 (32 x 32), sequency order: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
RPL
« DUP SIZE DUP 1 GET
SWAP 2 * 0 CON ROT ROT → w k
« 0 3 FOR t
IF t 3 == THEN -1 'w' STO* END
1 k SQ FOR z
z DUP 1 - k / IP k * +
t 2 MOD LASTARG / IP @ can be replaced by IDIV2 on HP-49s
k * SWAP k SQ * 2 * + +
w z GET
PUT
NEXT NEXT
» » 'NEXTW' STO
« [[1 1][1 -1]]
WHILE SWAP 1 - DUP REPEAT
SWAP NEXTW
END DROP
» 'WALSH' STO
4 WALSH
- Output:
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 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 -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 -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 1 ]]
Wren
Wren-cli
Text mode version.
import "./matrix" for Matrix
import "./fmt" for Fmt
var walshMatrix = Fn.new { |n|
var walsh = Matrix.new(n, n, 0)
walsh[0, 0] = 1
var k = 1
while (k < n) {
for (i in 0...k) {
for (j in 0...k) {
walsh[i+k, j] = walsh[i, j]
walsh[i, j+k] = walsh[i, j]
walsh[i+k, j+k] = -walsh[i, j]
}
}
k = k + k
}
return walsh
}
var signChanges = Fn.new { |row|
var n = row.count
var sc = 0
for (i in 1...n) {
if (row[i-1] == -row[i]) sc = sc + 1
}
return sc
}
var walshCache = {} // to avoid calculating the Walsh matrix twice
for (order in [2, 4, 5]) {
var n = 1 << order
Fmt.print("Walsh matrix - order $d ($d x $d), natural order:", order, n, n)
var w = walshMatrix.call(n)
walshCache[order] = w
Fmt.mprint(w, 2, 0, "|", true)
System.print()
}
for (order in [2, 4, 5]) {
var n = 1 << order
Fmt.print("Walsh matrix - order $d ($d x $d), sequency order:", order, n, n)
var rows = walshCache[order].toList
rows.sort { |r1, r2| signChanges.call(r1) < signChanges.call(r2) }
Fmt.mprint(rows, 2, 0, "|", true)
System.print()
}
- Output:
Walsh matrix - order 2 (4 x 4), natural order: | 1 1 1 1| | 1 -1 1 -1| | 1 1 -1 -1| | 1 -1 -1 1| Walsh matrix - order 4 (16 x 16), natural order: | 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| | 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| | 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| | 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| Walsh matrix - order 5 (32 x 32), natural order: | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| Walsh matrix - order 2 (4 x 4), sequency order: | 1 1 1 1| | 1 1 -1 -1| | 1 -1 -1 1| | 1 -1 1 -1| Walsh matrix - order 4 (16 x 16), sequency order: | 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| | 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| | 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| | 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| Walsh matrix - order 5 (32 x 32), sequency order: | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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| | 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|
DOME
Image mode version.
import "dome" for Window
import "input" for Keyboard
import "graphics" for Canvas, Color
import "./matrix" for Matrix
import "./polygon" for Square
var walshMatrix = Fn.new { |n|
var walsh = Matrix.new(n, n, 0)
walsh[0, 0] = 1
var k = 1
while (k < n) {
for (i in 0...k) {
for (j in 0...k) {
walsh[i+k, j] = walsh[i, j]
walsh[i, j+k] = walsh[i, j]
walsh[i+k, j+k] = -walsh[i, j]
}
}
k = k + k
}
return walsh
}
var signChanges = Fn.new { |row|
var n = row.count
var sc = 0
for (i in 1...n) {
if (row[i-1] == -row[i]) sc = sc + 1
}
return sc
}
var WalshNaturalCache = {}
var WalshSequencyCache = {}
for (order in [2, 4, 5]) {
var n = 1 << order
var w = walshMatrix.call(n).toList
WalshNaturalCache[order] = w
}
for (order in [2, 4, 5]) {
var rows = WalshNaturalCache[order].toList
rows.sort { |r1, r2| signChanges.call(r1) < signChanges.call(r2) }
WalshSequencyCache[order] = rows
}
class WalshMatrix {
construct new() {
Window.title = "Walsh Matrix"
Window.resize(1020, 750)
Canvas.resize(1020, 750)
var bc = Color.black
for (natural in [true, false]) {
if (natural) {
Canvas.print("NATURAL ORDERING", 450, 10, Color.blue)
} else {
Canvas.print("SEQUENCY ORDERING", 450, 400, Color.blue)
}
var z = 10
for (order in [2, 4, 5]) {
var y = natural ? 30 : 420
var mat = natural ? WalshNaturalCache[order] : WalshSequencyCache[order]
var n = 1 << order
var size = 320 / n
for (row in mat) {
var x = z
for (i in row) {
var fc = (i == 1) ? Color.green : Color.red
var sq = Square.new(x, y, size)
sq.drawfill(fc, bc)
x = x + size
}
y = y + size
}
z = z + 340
}
}
}
init() {}
update() {}
draw(alpha) {}
}
var Game = WalshMatrix.new()
