7 May
2015
7 May
'15
2:32 p.m.
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... 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.