Timeline for How can I make a 4x4 switch out of 2x2 switches?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 25, 2013 at 3:48 | comment | added | Kaz | @AlKepp Hmm. We know from sorting that a budget of \$n\log n\$ operations is enough to go to any permutation giving us a bound on how many exchange operations (thus switches) we need. But numerical experiments are indicating to me that \$2^{n\log n}\$ grows faster than \$n!\$. The ratio \$r(n)\$ between them seems to be exponential, judging from various \$r(2n)\$ values having about twice the number of decimal digits as \$r(n)\$. Permutations are formed by complete random access of choice w.r.t which element is appened to a sequence, but in-place exchanges must re-use positions. | |
| Mar 25, 2013 at 2:27 | comment | added | Al Kepp | I think this solution is correct. +1 We have got 6 switches, so there are 2^6=64 combinations. We expect to have only 24 combinations, so some combinations lead to the same output. But I can't see how this can be more optimized. (But you can prove me wrong. It's a nice mathematical problem. :-)) | |
| Feb 23, 2013 at 1:09 | history | edited | Kaz | CC BY-SA 3.0 |
deleted 322 characters in body
|
| Feb 23, 2013 at 1:09 | comment | added | Kaz | @supercat Are you sure bout the second claim: removing one of the switches? Suppose we remove one on the left, so that we cannot swap one of the two pairs. How can we achieve ABCD -> DABC? | |
| Feb 23, 2013 at 0:55 | comment | added | Kaz | That's what my intuition told me but I got stuck on that one case. It's suddenly obvious: ABCD -> BADC -> DABC. I will change the answer, thanks. | |
| Feb 23, 2013 at 0:18 | comment | added | supercat | Not only can the six-switch setup hit all permutations, but it would be able to do so even if one of the switches on the left or right were hard-wired to always pass straight through. | |
| Feb 22, 2013 at 22:44 | history | answered | Kaz | CC BY-SA 3.0 |