I want to permute a vector using comparison networks. This is the only method I have at my disposal.
My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector at the start of the network and instead of comparing the quantities I draw a random bit. this bit determines whether I perform the exchange or not.
My intuition tells me, that I would not need a full sorting network for that matter. So I was wondering if there is ANY COMPARISON network with complexity similar or smaller than nlog(n) that I could use instead or those sorting networks would allow me to obtain all the set of permutations of a vector.
thanks so much in advance
You could think of a telecommunications switch, wiring the simultaneous phone calls from $N$ people to $N$ people, with some folks calling themselves (or doing no call in this case).
In your problem the people are the components of the vector which should be connected to some other component of the vector.
The naive solution is to give each of the $N$ participants a switch with $N$ settings (to the $N-1$ other people and one setting for the self/no call) and to wire all of these connections. With large $N$ this is very resource consuming.
In practice there were methods devised to structure such a network more clever. This is subject to some theory in communications engineering. Have a look at Clos Network for example.
If only two-way switches are allowed you get a special case: the Beneš network.
BTW The answer to this question has a link to paper with a Beneš network used to implement a permutation.