Schoute permutation

Schoute matrix
rows: Schoute permutations
columns: Schoute partitions

A Schoute permutation is a Walsh permutation corresponding to a permutation matrix.
It can be seen as a permutation of hypercube vertices derived from a permutation of coordinate axes.
In the signed case (see below) the axes can also change their directions.

A Schoute permutation or degree d has length 2^d.
Like with all Walsh permutations, it makes sense to see them as periodic.
The n-th Schoute permutation is row n of the number triangle A195665.

The most well known Schoute permutations are the bit-reversal permutations.
They are always the last row in a finite Schoute matrix, because the reversal is always the last among the finite permutations.

Also well known (but very forgettable) are those that simply sort the even before the odd numbers. (The corresponding finite permutations are the left shifts.)

Schoute permutations

signed Schoute permutations

examples with degree 4 (Python code)

This code uses the Python library discrete helpers.

import numpy as np

from discretehelpers.a import int_to_perm


perm_matrix = np.zeros([24, 4], dtype=int)
schoute_matrix = np.zeros([24, 16], dtype=int)

for i in range(24):
    perm_object = int_to_perm(i)

    perm_matrix[i, :] = perm_object.sequence(4)
    schoute_matrix[i, :] = perm_object.schoute_perm.sequence(16)

n

n-th finite permutation

n-th Schoute permutation

[[0, 1, 2, 3],
 [1, 0, 2, 3],
 [0, 2, 1, 3],
 [2, 0, 1, 3],
 [1, 2, 0, 3],
 [2, 1, 0, 3],

 [0, 1, 3, 2],
 [1, 0, 3, 2],
 [0, 3, 1, 2],
 [3, 0, 1, 2],
 [1, 3, 0, 2],
 [3, 1, 0, 2],

 [0, 2, 3, 1],
 [2, 0, 3, 1],
 [0, 3, 2, 1],
 [3, 0, 2, 1],
 [2, 3, 0, 1],
 [3, 2, 0, 1],

 [1, 2, 3, 0],
 [2, 1, 3, 0],
 [1, 3, 2, 0],
 [3, 1, 2, 0],
 [2, 3, 1, 0],
 [3, 2, 1, 0]]

[[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
 [ 0,  2,  1,  3,  4,  6,  5,  7,  8, 10,  9, 11, 12, 14, 13, 15],
 [ 0,  1,  4,  5,  2,  3,  6,  7,  8,  9, 12, 13, 10, 11, 14, 15],
 [ 0,  4,  1,  5,  2,  6,  3,  7,  8, 12,  9, 13, 10, 14, 11, 15],
 [ 0,  2,  4,  6,  1,  3,  5,  7,  8, 10, 12, 14,  9, 11, 13, 15],
 [ 0,  4,  2,  6,  1,  5,  3,  7,  8, 12, 10, 14,  9, 13, 11, 15],

 [ 0,  1,  2,  3,  8,  9, 10, 11,  4,  5,  6,  7, 12, 13, 14, 15],
 [ 0,  2,  1,  3,  8, 10,  9, 11,  4,  6,  5,  7, 12, 14, 13, 15],
 [ 0,  1,  8,  9,  2,  3, 10, 11,  4,  5, 12, 13,  6,  7, 14, 15],
 [ 0,  8,  1,  9,  2, 10,  3, 11,  4, 12,  5, 13,  6, 14,  7, 15],
 [ 0,  2,  8, 10,  1,  3,  9, 11,  4,  6, 12, 14,  5,  7, 13, 15],
 [ 0,  8,  2, 10,  1,  9,  3, 11,  4, 12,  6, 14,  5, 13,  7, 15],

 [ 0,  1,  4,  5,  8,  9, 12, 13,  2,  3,  6,  7, 10, 11, 14, 15],
 [ 0,  4,  1,  5,  8, 12,  9, 13,  2,  6,  3,  7, 10, 14, 11, 15],
 [ 0,  1,  8,  9,  4,  5, 12, 13,  2,  3, 10, 11,  6,  7, 14, 15],
 [ 0,  8,  1,  9,  4, 12,  5, 13,  2, 10,  3, 11,  6, 14,  7, 15],
 [ 0,  4,  8, 12,  1,  5,  9, 13,  2,  6, 10, 14,  3,  7, 11, 15],
 [ 0,  8,  4, 12,  1,  9,  5, 13,  2, 10,  6, 14,  3, 11,  7, 15],

 [ 0,  2,  4,  6,  8, 10, 12, 14,  1,  3,  5,  7,  9, 11, 13, 15],
 [ 0,  4,  2,  6,  8, 12, 10, 14,  1,  5,  3,  7,  9, 13, 11, 15],
 [ 0,  2,  8, 10,  4,  6, 12, 14,  1,  3,  9, 11,  5,  7, 13, 15],
 [ 0,  8,  2, 10,  4, 12,  6, 14,  1,  9,  3, 11,  5, 13,  7, 15],
 [ 0,  4,  8, 12,  2,  6, 10, 14,  1,  5,  9, 13,  3,  7, 11, 15],
 [ 0,  8,  4, 12,  2, 10,  6, 14,  1,  9,  5, 13,  3, 11,  7, 15]]

usage

These number patterns appear in many sources related to computer science.

SIMD related question (Stackoverflow)

Is there a SIMD intrinsics like scatter but between registers?

x = _mm256_shuffle_epi8(x, _mm256_setr_epi8(
    0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15,
    0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15));

N-dimensional representation classes (Galactic Dynamics)

N-dimensional representation classes

<NDCartesianRepresentation (x1, x2) in kpc
    [(0.,  8.), (1.,  9.), (2., 10.), (3., 11.), (4., 12.), (5., 13.), (6., 14.), (7., 15.)]>

<NDCartesianRepresentation (x1, x2, x3, x4) in kpc
    [(0., 4.,  8., 12.), (1., 5.,  9., 13.), (2., 6., 10., 14.), (3., 7., 11., 15.)]>

16 sectors on a ProDOS disk track (Google groups)

ProDOS vs DOS 3.3 sector order, sector headers, and interleaving

Then the 16 sectors on a ProDOS disk track are ordered
0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 15
which is what I would call a normal 2:1 interleave.

leaf nodes of collapsed trees (PDF)

Dynamic processor allocation in hypercube computers by Chuang and Tzeng (1990)

Fig. 1. A binary tree representation (T₄) with a parameter <t₀, t₁, t₂, t₃> = <0, 2, 3, 1>.
Fig. 6. (b) The leaf nodes of collapsed trees.
Fig. 7. Performing σ₂ on an sequence of 2⁴ numbers corresponding to the leaf node addresses shown in Fig. 1.

Primer Preserving Permutations in music theory (PDF)

MODELING THE MULTISCALE STRUCTURE OF CHORD SEQUENCES USING POLYTOPIC GRAPHS by Louboutin and Bimbot

P0	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
P0	A	A	A	A	B	B	B	B	C	C	C	C	D	D	D	D
P1	0	1	4	5	2	3	6	7	8	9	12	13	10	11	14	15
P1	A	A	B	B	A	A	B	B	C	C	D	D	C	C	D	D
P2	0	2	4	6	1	3	5	7	8	10	12	14	9	11	13	15
P2	A	B	A	B	A	B	A	B	C	D	C	D	C	D	C	D
P3	0	1	8	9	2	3	10	11	4	5	12	13	6	7	14	15
P3	A	A	B	B	C	C	D	D	A	A	B	B	C	C	D	D
P4	0	2	8	10	1	3	9	11	4	6	12	14	5	7	13	15
P4	A	B	A	B	C	D	C	D	A	B	A	B	C	D	C	D
P5	0	4	8	12	1	5	9	13	2	6	10	14	3	7	11	15
P5	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D

Table 1. List of the 6 PPPs, together with their corresponding Prototypical Carrier Sequences (PCS).

signed

reflection of cube vertices

A signed Schoute permutation is a Schoute permutation permuted by the row of a XOR table.
It corresponds to a signed permutation (but is not itself signed).
This file shows all 16·24 = 384 signed Schoute permutations of degree 4. Each 16×16 matrix shows a Schoute permutation in the top row and its XOR permutations below.