1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @mvw Thanks so much for the attention! uhm the thing is as far as I know they can and they should! A comparison network is the term to define a network with comparator gates e.g. all sorting networks are comparison networks but not all comparison networks are sorting networks $\endgroup$
    – DaWNFoRCe
    Commented Jan 28, 2015 at 13:31
  • $\begingroup$ The values of the vector play no role for the routing. So comparison make no sense to me. Isn't this more about implementing a permutation with a network of configurable switches? Not unlike a railroad switch? $\endgroup$
    – mvw
    Commented Jan 28, 2015 at 13:37
  • $\begingroup$ That is my goal, hope you can give me a hand $\endgroup$
    – DaWNFoRCe
    Commented Jan 28, 2015 at 14:49
  • $\begingroup$ Is this a theoretical problem or do you need to come up with some hardeware? $\endgroup$
    – mvw
    Commented Jan 29, 2015 at 10:03

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks, I see how the problem can be related to mine, but I don't see how to apply it.. what should be the dept of the network and what properties it needs to have... $\endgroup$
    – DaWNFoRCe
    Commented Jan 28, 2015 at 16:22
  • $\begingroup$ any comments on that would be highly appreciated :D @mvw $\endgroup$
    – DaWNFoRCe
    Commented Jan 29, 2015 at 9:36
  • $\begingroup$ "The number of inputs and outputs is $N= r\times n = 2r$. Such networks have $2\log_2 N - 1$ stages, each containing $N/2$ $2\times 2$ crossbar switches, and use a total of $N\log_2 N- N/2$ $2\times 2$ crossbar switches." I would go into a library and dig deeper into the references. $\endgroup$
    – mvw
    Commented Jan 29, 2015 at 10:01
  • $\begingroup$ Thax!! @mvw I will try it $\endgroup$
    – DaWNFoRCe
    Commented Jan 29, 2015 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .