I want to build a network of switches that with $N$ inputs that allows any pairing of the inputs to be created ($N$ is an even number). For each number of inputs, I'm looking for a network with the minimal number of switches.
Each switch has 4 terminals, each connected to a terminal of another switch or one of the inputs. In the following examples, I'll use this symbol to represent such a switch:
The two inputs on the left a and b are either connected to the same outputs a and b on the right or with the outputs flipped, depending on the state of the switch, i.e. in one of these ways:
The following is an example of a network that uses two switches to connect 4 inputs to each other. By setting each of the switches to the "flipped" or "non-flipped" state, it is possible to create any pairing of the inputs:
Here are the paths that need to be connected for each possible pairing of the inputs (the states of the switches are not shown but can be deduced from the color-coded paths):
Here is a network with 6 inputs and 5 switches plus the paths of 2 possible pairings:
The network above allows all 15 pairings of the inputs to be made. This is the network with the lowest number of switches I was able to find for 6 inputs.
There are $(N - 1)!!$ pairings of N inputs. A network of $k$ switches has $2^k$ different states. Thus a network with $N$ inputs will need at least $k = \lceil log_2((N - 1)!!) \rceil$ switches to allow for a different state for each pairing.
Is the minimal number of switches of such networks known for larger $N$?