An Efficient Algorithm for Generating Linear Transformations in a Shuffle-Exchange Network
Tuvi Etzion, Abraham Lempel · SIAM Journal on Computing · 1986
This paper presents an algorithm for generating all the permutations defined by linear transformations on a shuffle-exchange network of $2^n $ processors in $2n - 1$ passes. The proposed algorithm generates any such permutation in $O(n\log ^2 n)$ elementary steps. The subclass of bit-permutations is generated in $O(n)$ steps.