The hallmark of the Cooley-Tukey algorithm for Fast Fourier Transform is the butterfly network, which helps reduce O(N^2) computations to O(N*log*N). Butterflies are very special graphs entangled in routing [Arora], switching [Chung], shuffling [Yang], and mixing [Czumaj].

The butterfly with 2 inputs and outputs (aka radix-2 butterfly, or the bipartite graph K(2, 2)) is a building block for larger networks [Chung]. It can implement two distinct operations: pass-through and swap.

**Problem 1**: Can an array of size N be permuted using only swapping 2-butterflies in a single stage? Single stage implies that every element is swapped exactly once.

Clearly, it can be iff N is even (otherwise the mapping is not bijective). Each permutation is also a maximal matching on the K(N/2, N/2) spanning N elements.

**Problem 2**: Can an array be deranged using only swapping 2-butterflies in a single stage?

There are always at least two derangements for any even-sized array when N > 2 (only one if N = 2). One can be obtained by swapping N/2 non-overlapping pairs. Another, by swapping the two halves of the array. Here’re two for N = 16:

**Problem 3**: How many such derangements are possible?

Let N = m * 2^k, where m >= 1 is some odd integer, and k > 0. There are at most log(k) – or, log(N), if m = 1 – distinct derangements.

**Problem 4**: Is there a permutation of the first N natural numbers, [1..N], such that if a number x is mapped to a number y in the permutation, then | x – y | == K for all x and y, and for a given 0 < K < N? |*| denotes the absolute value. In other words, is there a bijective function f mapping [1..N] to [1..N] such that |x – f(x)| == K?

Since K > 0, this permutation must be a derangement. The previous two examples for N = 16 illustrate K = 1 and K = 8. They represent a derangement that swaps N / K groups of K neighbors with each other. If K leaves an even factor to N, and K <= N/2, then such a derangement always exists. Here’s a short program to print them out:

public static String permute(int n, int k) { StringBuilder result = new StringBuilder(2 * n); if (n % 2 == 0 && k > 0 && k <= (n / 2)) { // any k that leaves an even factor is fine // e.g. k = 4 for n = 12 is not valid but k = 2 is if ((n % k == 0) && ((n / k) % 2 == 0)) { // groups of k are swapped with neighbors int k2 = k * 2; for (int g = 0; g < n / k2; ++g) { int f = k2 * g; for (int i = k + 1; i <= k2; ++i) { result.append(f + i).append(" "); } for (int i = 1; i <= k; ++i) { result.append(f + i).append(" "); } } return result.toString(); } } return "No permutation exists"; }

[Arora] S. Arora, F. T. Leighton, B. M. Maggs. *Online algorithms for path selection in a nonblocking network*.

[Chung] F. R. K. Chung. *An algebraic approach to switching networks*.

[Yang] Q. Yang, J. Ellis, K. Mamakani, F. Ruskey. *In-place permuting and perfect shuffling using involutions*.

[Czumaj] A. Czumaj. *Random permutations using **switching networks*.