[Question]
  [
Below on the left is a picture of a sorting network that can sort 4 inputs. On the right you can see it sorting the input `3,2,4,1`.
![](https://upload.wikimedia.org/wikipedia/commons/9/9b/SimpleSortingNetworkFullOperation.svg)
A sorting network of size `n` consists of a set of `n` horizontal wires where two wires can be connected by a vertical wire. The inputs to a sorting network move from the left to the right on the horizontal wires and whenever a vertical wire connects two elements they swap places if the lower element comes before the higher element.
The example sorting network above has the property that it correctly sorts all inputs. You could add even more wires but the behavior would not change. But if you removed a wire then there would be some inputs that it would not sort anymore.
Two networks behave the same if for every input permutation they produce the same output permutation. Your task is to find out how many possible behaviors there are for a given size. That is, output a sequence of the number of behaviors (equivalence classes) for n=1,2,3,... etc.
Your code will be scored based on its speed on an AMD Ryzen 1800X Linux system. The code should output the sequence described above. I'll run each submission for 5 minutes and with a 16GiB ram limit. Whichever code has outputted most of the sequence wins. Ties are broken by whichever program outputted the final number first.
You can use a probabilistic algorithm, however it must be in the 5 sigma threshold, meaning that the chance that your program outputs the incorrect result must be less than one in 3.5 million. If it's good enough for particle physics, it's good enough for this challenge.
Sequence output
```
1
2
11
261
43337
72462128
```
A lower bound on the seventh value is 4.6 billion, but personally I'd guess it's around a trillion.
# Leaderboard
| Score | Language | Author |
| --- | --- | --- |
| 6 in 10.75s | Rust | [gsitcia](https://codegolf.stackexchange.com/a/261442/84290) |
| 6 in 23.97s | Rust | [isaacg](https://codegolf.stackexchange.com/a/261300/84290) |
| 6 in 70.93s | Rust | [Anders Kaseorg](https://codegolf.stackexchange.com/a/261259/84290) |
| 5 in 0.188s | Haskell | [Roman Czyborra](https://codegolf.stackexchange.com/a/261333/84290) |
| 5 in 1.437s | JS (Node.js) | [Arnauld](https://codegolf.stackexchange.com/a/261252/84290) |
| 4 in 0.038s | Haskell | [Roman Czyborra](https://codegolf.stackexchange.com/a/261258/84290) |
 
  
[Answer]
# Rust, \$n = 6\$ in ≈ 59 seconds
The main simplifying observation here is that we don’t need to run the network on all \$n!\$ permutations; it suffices to run it on all \$2^n\$ binary strings. We can do this efficiently on all strings simultaneously using bitwise operations.
**`Cargo.toml`**
```
[package]
name = "sorting"
version = "0.1.0"
edition = "2021"
[dependencies]
hashbrown = "0.13.2"
typed-arena = "2.0.2"
```
**`src/main.rs`**
```
use hashbrown::HashSet;
use typed_arena::Arena;
type Item = u64;
const LOG_BITS: usize = Item::BITS.trailing_zeros() as usize;
fn search<'a>(arena: &'a Arena<Item>, found: &mut HashSet<&'a [Item]>, state: &mut [Item]) {
    let n = state.len();
    for i in 0..n - 1 {
        let p = state[i];
        for j in i + 1..n {
            let q = state[j];
            if p & !q != 0 {
                state[i] = p & q;
                state[j] = p | q;
                let mut inserted = false;
                found.get_or_insert_with(state, |state| {
                    inserted = true;
                    arena.alloc_extend(state.iter().copied())
                });
                if inserted {
                    search(arena, found, state);
                }
                state[i] = p;
                state[j] = q;
            }
        }
    }
}
fn count_networks(n: usize) -> usize {
    assert!(n <= LOG_BITS);
    let mut state = Vec::from_iter((0..n).map(|i| !0 / (1 << (1 << i) | 1)));
    let arena = Arena::new();
    let mut found = HashSet::new();
    found.insert(&*arena.alloc_extend(state.iter().copied()));
    search(&arena, &mut found, &mut state);
    found.len()
}
fn main() {
    for n in 1..=LOG_BITS {
        println!("{}", count_networks(n));
    }
}
```
[Answer]
# Rust, \$n=6\$ in roughly ~~50~~ ~~48~~ ~~43~~ ~~41~~ 23 seconds.
*Thanks to @AnttiP for a 44% speedup!*
My solution is based off of @AndersKaseorg's solution. I originally posted my changes as comments there, but with the number of changes I've made, I thought it'd be better to post as a separate answer.
**`Cargo.toml`**
```
cargo-features = ["profile-rustflags"]
[package]
name = "sorting"
version = "0.1.0"
edition = "2021"
[dependencies]
hashbrown = "0.13.2"
rustc-hash = "1.1.0"
[profile.release]
rustflags = ["-C", "target-cpu=native"]
```
**`src/main.rs`**
```
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
type HashSet<V> = hashbrown::HashSet<V, BuildHasherDefault<FxHasher>>;
type Item = u64;
const LOG_BITS: usize = Item::BITS.trailing_zeros() as usize;
/*
    Extract just the nontrivial bits that can actually change:
    0..57 from state[0]
    0..57 from state[1]
    0..57 from state[2]
   11..57 from state[3]
   26..57 from state[4]
     none from state[5]
    A bit position is either trivial or can't change
    if in the input, all wires after that position were 1s.
    That position is either forced to be a 1,
    or reconstructible from the other earlier wires.
    It turns out to be safe to just treat trivial bits as if
    they're already zeroed out, rather than zeroing them manually.
    Empirically, this causes no collisions.
    I wasn't sure that this would work, but it does,
    and that's good enough for me.
*/
type CompactState = [Item; 4];
const fn compact(state: &[Item; LOG_BITS]) -> CompactState {
    let out_0 = state[0] ^ (state[1] << 57);
    let out_1 = (state[1] >> 7) ^ (state[2] << 50);
    let out_2 = (state[2] >> 14) ^ (state[3] << (43 - 11));
    let out_3 = (state[3] >> (21 + 11)) ^ state[4];
    [out_0, out_1, out_2, out_3]
}
fn search<'a>(
    found: &mut HashSet<CompactState>,
    state: &mut [Item; LOG_BITS],
    last_i: usize,
    last_j: usize,
) {
    for i in 0..LOG_BITS - 1 {
        let p = state[i];
        for j in i + 1..LOG_BITS {
            if i < last_i && j != last_i && j != last_j {
                continue;
            }
            let q = state[j];
            if p & !q != 0 {
                state[i] = p & q;
                state[j] = p | q;
                let compact_state = compact(state);
                let inserted = found.insert(compact_state);
                if inserted {
                    search(found, state, i, j);
                }
                state[i] = p;
                state[j] = q;
            }
        }
    }
}
// Inputs that are already sorted are removed.
fn initial_state(n: usize) -> [Item; LOG_BITS] {
    // Remove inputs that are already sorted
    let inputs: Vec<u64> = (0..1 << n)
        .rev()
        .filter(|i| (0..n - 1).any(|b| i & (1 << b) > 0 && i & (1 << (b + 1)) == 0))
        .collect();
    let mut state = [0; LOG_BITS];
    for (wire_index, wire_mut) in state.iter_mut().enumerate() {
        if wire_index < n {
            for (bit_index, input) in inputs.iter().enumerate() {
                if input & 1 << wire_index > 0 {
                    *wire_mut |= 1 << bit_index;
                }
            }
        } else {
            // If n < LOG_BITS, pad with all-ones wires.
            *wire_mut = !0;
        }
    }
    // Debugging printout
    if false {
        for wire in state {
            println!("{wire:#066b}");
        }
    }
    state
}
fn count_networks(n: usize) -> usize {
    assert!(n <= LOG_BITS);
    let mut state = initial_state(n);
    let mut found: HashSet<CompactState> = HashSet::default();
    let compact_state = compact(&state);
    found.insert(compact_state);
    search(&mut found, &mut state, 0, 0);
    found.len()
}
fn main() {
    for n in 1..=LOG_BITS {
        println!("{}", count_networks(n));
    }
}
```
The basic idea of this program, and of @AndersKaesorg's solution, is to maintain a state consisting of the effect of a sorting network on all possible inputs of \$n\$ bits, from `000000` to `111111`. The state is internally represented as a vector of \$n\$ 64-bit integers, where each of the first \$2^n\$ bit indexes represents one possible input. All possible comparisons are performed, and a hash table is used to check if any comparisons give a new result. If so, it's added to the hash table and the comparison function is called recursively.
The changes I've made, starting from @AndersKaesorg's solution, are:
* Track the last pair of wires that were compared in order to reach the current state. If that pair doesn't overlap with the current comparison being considered, and the current comparison is earlier lexicographically that the last comparison, skip the current comparison. In other words, we shouldn't consider both comparing `[1, 2]` then `[3, 4]` and also comparing `[3, 4]` then `[1, 2]` - both orderings give the same result.
* When inserting a state into the HashSet to check if it's a new state, leave out the final wire of the state. Because a comparison doesn't change the total number of 0s and 1s, the contents of the last wire are implicit in the other wires.
* Change the hash function from ahash, Rust's default hashing function, to FxHash, which is what the rust compiler uses. It's less collision-resistant, but much faster, and the tradeoff is worth it.
* Store the hash table values as fixed-width arrays, rather than variable-width slices. This communicates more information about the hash values to the compiler, allowing it to produce more optimized code.
* Enable optimizations for my specific machine: `rustflags = ["-C", "target-cpu=native"]`.
* When generating the initial state with all possible inputs, remove the \$n+1\$ inputs that are already in sorted order, as these inputs don't distinguish anything. Move the remaining inputs to the low-order bits of the 64-bit integers in the state. This helps because FxHash is asymmetrical: It makes more use of entropy in the low-order bits than the high-order bits, because it performs a multiplication by a large constant and discards the overflow.
* Extract just the nontrivial bits from the state, and use those as the HashSet value. This amounts to only 4 u64s, rather than 5 previously. This isn't a huge time saving, only 1-2 seconds, because of the extra work that needs to be done to generate the smaller value. However, this change dramatically shrinks the peak memory usage, from about 70% of my machine's RAM to about 40% of it.
* Simplify the hash value extraction with some arcane magic.
* Store the HashSet values directly in the HashSet, rather than in a separate allocation. This is slightly less memory efficient, but much faster. It only became possible because of the previous memory efficiency improvements.
In my timing on my machine, these changes brought the runtime down from ~75 seconds to ~23 seconds.
[Answer]
# Rust, n=6 in ~~~12~~ 1 second
This answer is based on @Anders Kaseorg's solution and uses some of @isaacg's improvements.
I got the answer 1,530,608,978,810 for n=7 in about 12 hours using more than 100 gigabytes of ram. (I'm not completely sure it's correct, since I don't know how to prove the conjectures this relies on).
The basic strategy is to count the total number of networks using the principle of inclusion-exclusion (splitting into groups based on the first swap).
**`Cargo.toml`**
```
cargo-features = ["profile-rustflags"]
[package]
name = "sorting_networks"
version = "0.1.0"
edition = "2021"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
hashbrown = "0.13.2"
rustc-hash = "1.1.0"
nohash-hasher = "0.2.0"
[profile.release]
rustflags = ["-C", "target-feature=+crt-static"]
```
**`main.rs`**
```
use std::{
    cmp::min,
    iter::repeat,
    mem::{replace, swap},
    time::{Duration, Instant},
};
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
type HashSet<V> = hashbrown::HashSet<V, BuildHasherDefault<FxHasher>>;
type HashMap<K, V> = hashbrown::HashMap<K, V, BuildHasherDefault<FxHasher>>;
macro_rules! networks {
    ($n:expr) => {
        networks::<{ $n }, { ($n * $n - $n) / 2 }>()
    };
}
type Item = u64;
fn main() {
    let then = Instant::now();
    networks!(1);
    networks!(2);
    networks!(3);
    networks!(4);
    networks!(5);
    networks!(6);
    // networks!(7);
    println!("Total time: {:?}", Instant::now().duration_since(then));
}
/**
 * Calculates number of networks
 */
fn networks<const N: usize, const N2: usize>() -> i64 {
    let then = Instant::now();
    let v: Vec<(i64, i64, Duration, Vec<u64>)> = counter(N)
        .into_iter()
        .map(|(sizes, multiplier)| {
            let then = Instant::now();
            let a = count_specific::<N, N2>(&sizes);
            (a, multiplier, Instant::now().duration_since(then), sizes)
        })
        .collect();
    let o = v.iter().map(|(a, m, _, _)| a * m).sum::<i64>() + 1;
    println!(
        "n={}: {} (took {:?})",
        N,
        o,
        Instant::now().duration_since(then)
    );
    v.iter().for_each(|(a, m, duration, sizes)| {
        println!(
            "  {:?}: {} = {} * {} (took {:?})",
            sizes,
            a * m,
            a,
            m,
            duration
        );
    });
    o
}
/**
 * Calculate multipliers for PIE
 */
fn counter(n: usize) -> HashMap<Vec<Item>, i64> {
    let mut counts = HashMap::default();
    if n == 1 {
        return counts;
    }
    let mut uf = UnionFind::new(n);
    counter_(&mut uf, n, 0, 1, 1, &mut counts);
    counts
}
fn counter_(
    uf: &mut UnionFind,
    n: usize,
    i: usize,
    j: usize,
    m: i64,
    counts: &mut HashMap<Vec<Item>, i64>,
) {
    let mut j1 = j + 1;
    let i1 = if j1 == n {
        j1 = i + 2;
        i + 1
    } else {
        i
    };
    uf.save();
    uf.join(i, j);
    *counts.entry(uf.get_sizes()).or_insert(0) += m;
    if j1 < n {
        counter_(uf, n, i1, j1, -m, counts);
    }
    uf.rollback();
    if j1 < n {
        counter_(uf, n, i1, j1, m, counts);
    }
}
/**
 * Counts number of networks that start with sorts that have given sizes
 */
fn count_specific<const N: usize, const N2: usize>(sizes: &Vec<Item>) -> i64 {
    let mut base_state = [0; N];
    let mut num_bits = 0;
    if sizes.iter().filter(|&v| v & 1 == 1).count() > (N & 1) {
        // no symmetric starting states
        let filter: Vec<_> = sizes
            .iter()
            .copied()
            .scan(0, |state, i| {
                let offset = *state;
                *state += i;
                Some(((1 << i) - 1, offset))
            })
            .collect();
        (1..1 << N)
            .filter(|&v| {
                // filter out states that aren't sorted in given ranges
                filter.iter().all(|&(mask, offset)| {
                    let n = (v >> offset) & mask;
                    n & (n + 1) == 0
                })
            })
            .filter(|&v: &Item| v & (v + 1) != 0) // filter out states that are completely sorted
            .for_each(|v| {
                // convert to state
                (0..N).rev().fold(v, |acc, i| {
                    base_state[i] = (base_state[i] << 1) | (acc & 1);
                    acc >> 1
                });
                num_bits += 1;
            });
        if num_bits > Item::BITS {
            panic!("Too big? {} > {} {:?}", num_bits, Item::BITS, sizes);
        }
        let mut states: HashSet<[Item; N]> = HashSet::default();
        visit_notree::<N, N2>(&mut base_state, &mut states); // populate states
        states.len() as i64
    } else {
        let mut state_to_idx: HashMap<[Item; N], usize> = HashMap::default();
        let mut tree: Vec<[usize; N2]> = Vec::new();
        let filter: Vec<_> = sizes
            .iter()
            .copied()
            .scan(0, |state, i| {
                // filter divides range so [3,2] => 0b1001001, 0b0100010
                let w = i / 2;
                let mask = (1 << w) - 1;
                let offset0 = *state;
                let mask0 = mask << offset0;
                let offset1 = N as Item / 2;
                let mask1 = (i & 1) << offset1;
                let offset2 = N as Item - (w + offset0);
                let mask2 = mask << offset2;
                *state += w;
                Some((
                    mask0,
                    offset0,
                    mask1,
                    offset1 - w,
                    mask2,
                    offset2 - w - (i & 1),
                ))
            })
            .collect();
        (1..1 << N)
            .filter(|v: &Item| {
                // filter out states that aren't sorted in given ranges
                filter.iter().all(|&(m0, o0, m1, o1, m2, o2)| {
                    let n = (v & m0) >> o0 | (v & m1) >> o1 | (v & m2) >> o2;
                    n & (n + 1) == 0
                })
            })
            .filter(|&v: &Item| {
                // filter out states that are completely sorted or states that have a smaller dual state
                (0..=N / 2).contains(&(v.count_ones() as usize)) && (v & (v + 1) != 0)
            })
            .map(|v| {
                // convert states to smaller states (this one is for situations like 010011 vs 001101)
                min(
                    v,
                    (((1 << N) - 1) - v).reverse_bits() >> (Item::BITS as usize - N),
                )
            })
            .collect::<HashSet<Item>>() //remove duplicates
            .into_iter()
            .for_each(|v| {
                // convert to state
                (0..N).rev().fold(v, |acc, i| {
                    base_state[i] = (base_state[i] << 1) | (acc & 1);
                    acc >> 1
                });
                num_bits += 1;
            });
        if num_bits > Item::BITS {
            panic!("Too big? {} > {} {:?}", num_bits, Item::BITS, sizes);
        } // currently, the largest this gets (for sizes=[2] and N=7) is 44
        let r = visit(&mut base_state, &mut tree, &mut state_to_idx); // build tree ("tree")
        double::<N, N2>(tree, r) as i64 // doubles (more like squares) tree
    }
}
/**
 * Finds all states that are descendants of the input state and maps them to numbers in topological order.
 * "tree" is an adjacency list on the numbers
 */
fn visit<const N: usize, const N2: usize>(
    state: &mut [Item; N],
    tree: &mut Vec<[usize; N2]>,
    state_to_idx: &mut HashMap<[Item; N], usize>,
) -> usize {
    if let Some(&idx) = state_to_idx.get(state) {
        idx
    } else {
        let mut l: Vec<Option<usize>> = vec![];
        for a in 0..N - 1 {
            let p = state[a];
            for b in a + 1..N {
                let q = state[b];
                if p & !q == 0 {
                    // self loop
                    l.push(None);
                } else {
                    state[a] = p & q;
                    state[b] = p | q;
                    l.push(Some(visit::<N, N2>(state, tree, state_to_idx)));
                    state[a] = p;
                    state[b] = q;
                }
            }
        }
        let v = state_to_idx.len();
        state_to_idx.insert(*state, v);
        tree.push(
            l.iter()
                .copied()
                .map(|x| x.unwrap_or(v))
                .collect::<Vec<usize>>()
                .try_into()
                .unwrap(),
        );
        v
    }
}
/**
 * Finds all descendant states from input_state
 */
fn visit_notree<const N: usize, const N2: usize>(
    state: &mut [Item; N],
    states: &mut HashSet<[Item; N]>,
) {
    if !states.contains(state) {
        for a in 0..N - 1 {
            let p = state[a];
            for b in a + 1..N {
                let q = state[b];
                if p & !q != 0 {
                    state[a] = p & q;
                    state[b] = p | q;
                    visit_notree::<N, N2>(state, states);
                    state[a] = p;
                    state[b] = q;
                }
            }
        }
        states.insert(*state);
    }
}
/**
 * Combines a graph with the reverse of the graph
 */
fn double<const N: usize, const N2: usize>(tree: Vec<[usize; N2]>, r: usize) -> usize {
    // does bfs on the graph, because visit returns in topological order, we can discard states with smaller rank, which saves memory
    let choices: Vec<(usize, usize)> = (0..N - 1).flat_map(|a| repeat(a).zip(a + 1..N)).collect();
    let choices_idx: HashMap<(usize, usize), usize> = choices
        .iter()
        .copied()
        .enumerate()
        .map(|(a, b)| (b, a))
        .collect();
    let rev: Vec<usize> = choices
        .iter()
        .copied()
        .map(|(a, b)| *choices_idx.get(&(N - 1 - b, N - 1 - a)).unwrap())
        .collect();
    let tree_rev: Vec<[usize; N2]> = tree
        .iter()
        .map(|t| {
            rev.iter()
                .map(|&v| t[v])
                .collect::<Vec<usize>>()
                .try_into()
                .unwrap()
        })
        .collect();
    let tl = tree.len();
    let mut queues: Vec<HashSet<usize>> = (0..2 * tl - 1).map(|_| HashSet::default()).collect();
    queues[2 * r].insert(r);
    let mut center = 0;
    let mut num_seen = 0;
    let mut rank = 2 * tl - 1;
    while !queues.is_empty() {
        rank -= 1;
        queues.pop().unwrap().drain().for_each(|a| {
            let b = rank - a;
            if a == b {
                center += 1;
            }
            num_seen += 1;
            for (&a1, &b1) in tree[a].iter().zip(tree_rev[b].iter()) {
                if a1 > b1 {
                    if a != b && (a != b1 || b != a1) {
                        queues[b1 + a1].insert(b1);
                    }
                } else if a != a1 || b != b1 {
                    queues[a1 + b1].insert(a1);
                }
            }
        });
    }
    2 * num_seen - center
}
// union-find with backtracking whatever
struct BacktrackArray<T> {
    data: Vec<T>,
    history: Vec<(usize, T)>,
    checkpoints: Vec<usize>,
}
impl<T: Copy> BacktrackArray<T> {
    pub fn new(data: Vec<T>) -> BacktrackArray<T> {
        BacktrackArray {
            data,
            history: vec![],
            checkpoints: vec![],
        }
    }
    pub fn rollback(&mut self) {
        self.history
            .drain(self.checkpoints.pop().unwrap_or(0)..)
            .rev()
            .for_each(|(idx, v)| self.data[idx] = v);
    }
    pub fn save(&mut self) {
        self.checkpoints.push(self.history.len());
    }
    pub fn set(&mut self, idx: usize, value: T) {
        self.history
            .push((idx, replace(&mut self.data[idx], value)));
    }
    pub fn get(&self, idx: usize) -> T {
        self.data[idx]
    }
}
impl<V: Copy> FromIterator<V> for BacktrackArray<V> {
    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
        BacktrackArray::new(Vec::from_iter(iter))
    }
}
impl<V: Copy> From<Vec<V>> for BacktrackArray<V> {
    fn from(val: Vec<V>) -> Self {
        BacktrackArray::new(val)
    }
}
struct UnionFind {
    num_unions: BacktrackArray<usize>,
    parent: BacktrackArray<usize>,
    size: BacktrackArray<Item>,
    representatives: BacktrackArray<usize>,
    rep_ptrs: BacktrackArray<usize>,
}
impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        UnionFind {
            num_unions: vec![n].into(),
            parent: (0..n).collect(),
            size: repeat(1).take(n).collect(),
            representatives: (0..n).collect(),
            rep_ptrs: (0..n).collect(),
        }
    }
    pub fn save(&mut self) {
        self.num_unions.save();
        self.parent.save();
        self.size.save();
        self.representatives.save();
        self.rep_ptrs.save();
    }
    pub fn rollback(&mut self) {
        self.num_unions.rollback();
        self.parent.rollback();
        self.size.rollback();
        self.representatives.rollback();
        self.rep_ptrs.rollback();
    }
    pub fn get_sizes(&self) -> Vec<Item> {
        let n = self.num_unions.get(0);
        let mut v: Vec<Item> = self
            .representatives
            .data
            .iter()
            .take(n)
            .map(|&i| self.size.get(i))
            .filter(|&v| v > 1)
            .collect();
        v.sort_unstable();
        v
    }
    pub fn join(&mut self, i: usize, j: usize) {
        let mut i = self.find(i);
        let mut j = self.find(j);
        if i != j {
            let mut s_i = self.size.get(i);
            let mut s_j = self.size.get(j);
            if s_i < s_j {
                swap(&mut s_i, &mut s_j);
                swap(&mut i, &mut j);
            }
            self.parent.set(j, i);
            self.size.set(i, s_i + s_j);
            let n = self.num_unions.get(0) - 1;
            self.num_unions.set(0, n);
            let r = self.representatives.get(n);
            let r_idx = self.rep_ptrs.get(j);
            self.representatives.set(r_idx, r);
            self.rep_ptrs.set(r, r_idx);
        }
    }
    pub fn find(&mut self, i: usize) -> usize {
        let i1 = self.parent.get(i);
        if i1 == i {
            i
        } else {
            let i2 = self.find(i1);
            self.parent.set(i, i2);
            i2
        }
    }
}
```
**`Output:`**
```
n=1: 1
n=2: 2
  [2]: 1 = 1 * 1 (took 7.73µs)
n=3: 11
  [2]: 12 = 4 * 3 (took 9.617µs)
  [3]: -2 = 1 * -2 (took 783ns)
n=4: 261
  [2]: 366 = 61 * 6 (took 17.105µs)
  [2, 2]: -48 = 16 * -3 (took 3.853µs)
  [3]: -64 = 8 * -8 (took 2.727µs)
  [4]: 6 = 1 * 6 (took 1.088µs)
n=5: 43337
  [2]: 62480 = 6248 * 10 (took 440.742µs)
  [2, 2]: -14100 = 940 * -15 (took 76.582µs)
  [5]: -24 = 1 * -24 (took 1.818µs)
  [2, 3]: 1280 = 64 * 20 (took 9.063µs)
  [3]: -6780 = 339 * -20 (took 35.228µs)
  [4]: 480 = 16 * 30 (took 3.91µs)
n=6: 72462128
  [2, 3]: 1741440 = 14512 * 120 (took 3.553571ms)
  [4]: 169650 = 1885 * 90 (took 164.134µs)
  [2, 2, 2]: 831870 = 55458 * 15 (took 3.841656ms)
  [2]: 103912905 = 6927527 * 15 (took 553.271018ms)
  [2, 2]: -28154610 = 625658 * -45 (took 43.410737ms)
  [3, 3]: -20480 = 512 * -40 (took 67.739µs)
  [5]: -4608 = 32 * -144 (took 4.743µs)
  [6]: 120 = 1 * 120 (took 2.899µs)
  [3]: -5991120 = 149778 * -40 (took 33.794472ms)
  [2, 4]: -23040 = 256 * -90 (took 49.235µs)
n=7: 1530608978810
  [2, 2]: -701933448825 = 6685080465 * -105 (took 1777.016031993s)
  [7]: -720 = 1 * -720 (took 22.07µs)
  [2, 2, 3]: -684133800 = 3257780 * -210 (took 424.2515ms)
  [2, 3]: 26000250360 = 61905358 * 420 (took 7.892396883s)
  [4]: 754063170 = 3590777 * 210 (took 282.065867ms)
  [2, 2, 2]: 39011470995 = 371537819 * 105 (took 67.801355981s)
  [2]: 2244447515625 = 106878453125 * 21 (took 40712.141796623s)
  [3, 4]: 1720320 = 4096 * 420 (took 431.995µs)
  [2, 5]: 516096 = 1024 * 504 (took 93.822µs)
  [5]: -5283432 = 10483 * -504 (took 809.017µs)
  [6]: 53760 = 64 * 840 (took 13.258µs)
  [3]: -76668548810 = 1095264983 * -70 (took 215.344123884s)
  [3, 3]: -174011040 = 621468 * -280 (took 176.875932ms)
  [2, 4]: -141184890 = 224103 * -630 (took 93.090671ms)
Total time: 42782.049221178s
```
The correctness of this solution relies on two conjectures.
Before that, notation.
There are \$N\$ wires, \$1\$ through \$N\$ (the set of them is denoted by \$[N]\$).
\$U\$ is the set of all possible networks over the \$N\$ wires. \$2^U\$ is the powerset of \$U\$ (that is, the set of all subsets of \$U\$).
We'll let \$G=\ (U, E)\$ be a directed graph with vertices \$U\$ and an edge from \$a\$ to \$b\$ iff \$b\$ can be expressed by appending a single vertical wire to the right of \$a\$. We also denote by \$G\_x\$ (for network \$x\$) the set of networks reachable from \$x\$.
Define \$S(A):\ 2^{[N]}\rightarrow U\$ to mean the network that sorts the wires in \$A\$.
This is sort of an abuse of notation, but for \$A\subseteq[N]\$, we will write \$G\_{S(A)}\$ as \$G\_A\$
Define \$F(\{A\_1, ..., A\_k\}): 2^{\left(2^{[N]}\right)}\rightarrow 2^U\$ (where \$A\_i \subseteq [N]\$ and the \$A\_i\$ are pairwise disjoint) to mean \$G\_{A\_1}\cap G\_{A\_2}\cap\ ...\cap\ G\_{A\_k}\$.
  
  
The first conjecture is that \$\|F(\{A\_1,...,A\_k\})\|=\|F(\{B\_1,...,B\_k\})\|\$ if \$\|A\_i\|=\|B\_i\|\$ for \$1\le i\le k\$.
The second conjecture is that given \$X\_1, X\_2, ..., X\_m \subseteq [N]\$ (possibly overlapping), \$G\_{X\_1}\cap G\_{X\_2}\cap ...\cap\ G\_{X\_m}=F({A\_1,A\_2,...,A\_k})\$ for some pairwise disjoint \$A\_i\$ with \$k\le m\$.
To be more specific, if we make a graph with vertices in \$[N]\$ and an edge between vertices \$a\$ and \$b\$ if there is some \$i\$ for which \$a,b \in X\_i\$, then the \$A\_j\$ are the connected components of that graph.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), \$n=5\$
Naive brute force.
```
for(let n = 1; n <= 5; n++) {
  console.log(n, solve(n));
}
function getPermutations(a) {
  let list = [];
  (function P(a, ...p) {
    if(a.length) {
      a.forEach((v, i) => P(a.filter(_ => i--), ...p, v));
    }
    else {
      list.push(p);
    }
  })(a);
  return list;
}
function solve(n) {
  let connector = [];
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      connector.push([i, j]);
    }
  }
  let perm = getPermutations([...Array(n)].map((_, n) => n)),
      lookup = {};
  perm.forEach((p, i) => lookup[p] = i);
  let transform = connector.map(([ i, j ]) =>
    perm.map(([...p]) => {
      if(p[i] > p[j]) {
        [ p[i], p[j] ] = [ p[j], p[i] ];
      }
      return lookup[p];
    })
  );
  let set = new Set();
  (function search(list) {
    let key = JSON.stringify(list);
    if(!set.has(key)) {
      set.add(key);
      transform.forEach(t => {
        let update = 0;
        let newList = list.map(permNdx => {
          let newNdx = t[permNdx];
          update |= newNdx != permNdx;
          return newNdx;
        });
        if(update) {
          search(newList);
        }
      });
    }
  })(perm.map((_, n) => n));
  return set.size;
}
```
[Try it online!](https://tio.run/##XVPBbtswDL37K9ibhDjGdtgpTYEedhmGrkCPhlEIiZwodWVBkrNlnb89IyXZcppDJJOP5OMjdRJn4XZWGb/W/V5er21vWSc9aNjC1w0e91v4hudqxeGjANj12vWdrLr@wHQJeD9LpjnfFGNRtIPeedVrOEj/LO374AV9OiZiMCXulPOYu242BVrYHPLMRAlVVZkIBVAtE1Un9cEfJxOAqJDgd7E7MnYuQXHYPlBk1arOS8te6Vut1zymKuFMzChwDP@yc3LORUwqM7gjMwvQyJFt4GalH6wOsNvupqbnnlAULXe@t7mxSUeFpi8bPO5B4zHJmAEnBChYkdinCDplEOTUkWmtSjg1S7pF4mBQb0z1WfkadXi0VlyQb1O9C8PYawk6CIdjKyct@v5tMBj/MQb6lC1LbSapI6w2DZGOKlFtb4V2iCYCmXAoVgMxhobCQ62QObpoRMExd4szN7Vq4AFMjW3OdoAayFEGO1D5OlzLYIZmk4BjOqfZTXyTYByPTNtJ2kQtf8OL9Ix/WkgnhcXmafwTEQp6kxcM@vHy66ly3ip9UO0lgkJ86OEOM1dH4RiCee6CrGK/D9YEhqzdLLdfKhKLDmYvvAyrVNw4kPzP@KDCNpOuJPDT/s9tkhkdPODrhJqFo1@q8m87Ae@2kHBLWNI2YrJj5PmOGsRk/IZDkjSRXuCnsY23DzHvynJnl4@TJHXqr8QHer3@Bw "JavaScript (Node.js) – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), n≤4
```
import Data.List
import Data.List.Ordered
pairs[]=[]
pairs(i:k)=[[i,j]|j<-k]++pairs k
end(a:b:c)=last$end(b:c):[a|a==b]
b n=length$end$iterate behave[permutations[1..n]]where
 gate[i,j]z=last$z:[[z!!last(l:[i+j-l|l==i||l==j])|l<-[0..n-1]]|z!!i>z!!j]
 behave bs=nubSort$bs++[map(gate[i,j])b|b<-bs,[i,j]<-pairs[0..n-1]]
```
[Try it online!](https://tio.run/##XVCxboQwDN3zFTmJAcQF9aROiNzUsVKHjlYGp0RHIORQkmsllH@nCbQdulh@fvZ7tgf0kzJm2/S83F2gLxiwedU@kP@F5s31yqmeLKidB8FBHGmp26niAPo8ijh2bBJ1vRN0Isr2Jbay/ai4QR@KjDNqASNyLgWR1HKj7C0MmSx0UA6DolIN@KlgUW5@BAz6bj1cmsYK8TWkLQi9pa7dcj2U1xZgPZ1yXpoWdD0yEw3nOuY4iiqajsFTkmAXIWJq1dcURkF@vKj03D7kezq6kL6uYcal/HOpZJQdk/68o44dT/iV22bUli9O2zTbFddMPIvtGw "Haskell – Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), n≤5
```
import Data.Array
import Data.Bits
import Data.List
import qualified Data.Set as S
b n = S.size$visit 1 2 ini (S.singleton$hash ini)
 where
  ini = listArray(1,n)$map((sum::[Integer]->Integer).zipWith(*)(iterate(2*)1))$transpose$sequence$replicate n[0,1]
  hash = id
  visit i j s visited
   |i>n =visited
   |j>n =visit(i+1)(i+2)s visited
   |s!i.&.complement(s!j)>0&&S.notMember (hash newState) visited
        =visit i(j+1)s$visit 1 2 newState(S.insert (hash newState) visited)
   |0<1 =visit i(j+1)s visited
         where newState=s//[(i,s!i.&.s!j),(j,s!i.|.s!j)]
main=mapM_(print.b)[1..5]
```
[Try it online!](https://tio.run/##dVHBTsMwDL33K4xUTck2wjrEZaKTQFyQQBx64FBNKNu81aVNS5yBmPbtlKxlaIDIyX6x33u2M83PWBRNQ2VdWQc32ml1Za1@D46Ra3L8A7gjdgfgZaMLWhEuu68EHWiGJAjmYCCGRDFtMXwlJgcRjIEMgdijZl2gq0yYac72qAzgLUOLAbQ1MRRepTUjoqGRYalrIXhTTibprXG4Rjs7nX5FUm2pfiSXib4U5NBqh2Lcl5GUobPacF0xhowvGzQLDC3WBS18DZh0NIxmgddsbcRAy33S2SXIgbsYlx6FHU39TMdA/g0IGkReezCWP1v4hFRPLaqyLrBE4wSf5HI66vUSZSp3j@UcLYhW3eBb4rwreUzQvvjLkMi9CB9t89DiN0qG0d/jHyrZmhldRr@4/kh1R/gmiPnsLBU07MbYex@KvM12beZ3V2oysb/O/ZOoLRmn5jKNlLqYNc3HYlXoNTenD@ef "Haskell – Try It Online")
[Answer]
# [Scala](http://www.scala-lang.org/), \$n \leq 5\$
Port of [@Arnauld's Javascript answer](https://codegolf.stackexchange.com/a/261252/110802) in Scala.
Naive brute force.
[Try it online!](https://tio.run/##dVQ9b9swEN35Ky5GBrJxhWboYtRBm6kBmqJAUHQIMjAyldCmSEGk0nxUv929kyiGatzBsnT37t27D9KX0sj9XteNawN4@ipKZ4wqg3a2qLsgb40qvmkfzruqUi2bQaW1LsgBGqQ2rSoZc7dbjIZLqS2ox6DsxsOXpoEXBlC5FriFT@/hFIKDj2KwAjSttsFY7hfHFo5fvDMPilvRLwS6e/xtVAWVLINrtTTcruBc313YIKYXWEemz5MO@phFfVWmUe1r7BJkWXZ1ZyT6/08IoKtB8xpORR4Svcp49TYJYIVLsPAujxBDSM@GvzchS@Rn0U3CYxNWMMrKNT3IFkpnrSIKtHLqa5JL7f0AnQ3agI3GLRk1nGDfc0cPT1qZDXC9hK0QRXA0aRaTGEBhNfFznggnkCjI2Y3T9yl0ijTO7boGYwlVPOvmlw73F3ajHhF5KZvXHKGV1mMBlCgVVdQSNwZKic0dxcH6LNYyMI7@5tU6ksWF/UGJMVHc2QlBk5wQXAs4S3iO1acOJmWqpgqyiAyQ86xznkMYkj/QJWef3sZOJV1Te1mO61mau1e0B1cqXF8FPDV3N1ywtOxeyba85wYJVkA017g2N7g9P63OV5qq26kntBC0qHcjF18sF5FtbNYRZsP7wOKhsp5jxKxLJOVkTUQs2dI0C3woWd7jlEI@pbGKrtnIoDB/JfH8sH8ab9VvEp/kjbPGsX/fPM65En7wQOARJWaYmO0PbnKEHq3hIHJ0Z6Y@e6eOjFTzXYGp71G3OBjfH5poDEzHK7vj6EjR0Z8tBM3D62c1XBQ92@//Ag)
```
import scala.collection.mutable.ListBuffer
import scala.annotation.tailrec
object Main extends App {
  for (n <- 1 to 5) {
    println(s"$n ${solve(n)}")
  }
  def factorial(n: BigInt): BigInt = {
    @tailrec
    def factorialHelper(n: BigInt, accumulator: BigInt): BigInt = {
      if (n <= 1) accumulator
      else factorialHelper(n - 1, n * accumulator)
    }
    factorialHelper(n, 1)
  }
  def solve(n: Int): Int = {
    var connector = (for {
      i <- 0 until n
      j <- i + 1 until n
    } yield (i, j)).toList
    val perm = (((0 until n).toList).permutations).toList
    val lookup = perm.zipWithIndex.toMap
    val transform = connector.map { case (i, j) =>
      perm.map { p =>
        val mutableP = p.toBuffer
        if (mutableP(i) > mutableP(j)) {
          val temp = mutableP(i)
          mutableP(i) = mutableP(j)
          mutableP(j) = temp
        }
        lookup(mutableP.toList)
      }
    }
    var set = Set[String]()
    def search(list: List[Int]): Unit = {
      val key = list.mkString(",")
      if (!set.contains(key)) {
        set += key
        transform.foreach { t =>
          var update = false
          val newList = list.map { permNdx =>
            val newNdx = t(permNdx)
            update |= (newNdx != permNdx)
            newNdx
          }
          if (update) {
            search(newList)
          }
        }
      }
    }
    search((0 until factorial(n).toInt).toList)
    set.size
  }
}
```
]