On Thu, 7 May 2015 16:32:09 -0400, Warren D Smith <warren.wds@gmail.com> wrote:

LB, something like your "bitswap" primitive move, where, e.g. items x and y are swapped if the binary integers x and y differ in only a single bit, we specify the single bit we have in mind, and all such (x,y) pairs are independently decided about whether that pair is swapped or not... all in a single whack...

I don't see how you arrive from the above to the below.

that thing yields diameter of the whole set of N! permutations, of diam=O(logN).

The reason: this set of primitives can be used to build a "Benes network" which is a well known "non-blocking network" capable of "routing any permutation" of "telephone calls" in O(logN) stages.

Unlike bit swap, Benes stages are of a scatter-gather variety with O(log(N)) different distances each, therefore using bit swaps to implement a Benes network, one would expect O(log(N)^2) stages. Leo