21
\$\begingroup\$

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.

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
6 in 23.97s Rust isaacg
6 in 70.93s Rust Anders Kaseorg
5 in 0.188s Haskell Roman Czyborra
5 in 1.437s JS (Node.js) Arnauld
4 in 0.038s Haskell Roman Czyborra
\$\endgroup\$
5
  • \$\begingroup\$ Assuming you want to prohibit solutions that just hardcode known values (treating prior computations as computer-assisted proofs), I wonder how to formulate that requirement precisely. Maybe an execution log of the program should correspond in some quantitative way to a proof that the generated values are correct. In any case, how far you get in the sequence is more interesting than how fast you get there. \$\endgroup\$
    – Karl
    Commented May 26, 2023 at 20:14
  • 1
    \$\begingroup\$ @Karl That's actually an interesting idea, didn't think that the no-hardcoding requirement could be formulated. I think you only need to require each submission to prove that the code produces (only) correct outputs (without resorting to external computation). \$\endgroup\$
    – AnttiP
    Commented May 26, 2023 at 21:02
  • 1
    \$\begingroup\$ @Karl Hard-coding known values to save time in fastest-code is already prohibited by default. But your proposed formalization doesn’t capture this objectively, since one could assert that the fixed execution log of the output statements corresponds to the fixed known proof of the hard-coded values. \$\endgroup\$ Commented May 26, 2023 at 21:16
  • \$\begingroup\$ @AndersKaseorg yeah, I was imagining a quantitative constraint to prevent that, e.g. an execution log of \$n\$ steps must translate to a proof of no more than, say, \$10^6+10^3n\$ steps. But then we have to say how we're measuring those lengths, which seems very impractical. It'd be cool if it were more practical/common to require programs to actually output machine-checkable proofs (or to include their own correctness proofs) and then we could just include the verification time in the runtime. \$\endgroup\$
    – Karl
    Commented May 26, 2023 at 21:41
  • 5
    \$\begingroup\$ Sequence not in OEIS. Potential new sequence to be submitted? \$\endgroup\$
    – qwr
    Commented May 28, 2023 at 3:09

7 Answers 7

12
\$\begingroup\$

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));
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ What wires in the sorting networks do your booleans correspond to? \$\endgroup\$ Commented May 27, 2023 at 11:12
  • \$\begingroup\$ @RomanCzyborra There are still \$n\$ booleans, one per wire—we can sort an array of booleans just as easily as an array of integers. The trick is that any two networks that can be distinguished by inputting an array of integers can also be distinguished by inputting some array of booleans. (This is essentially the zero-one principle.) \$\endgroup\$ Commented May 27, 2023 at 18:49
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Tip: remove the arenas and just store the arrays in the hashset directly \$\endgroup\$
    – AnttiP
    Commented May 29, 2023 at 7:06
  • \$\begingroup\$ @AnttiP Thanks! Previously without the arena the program ran out of memory, but with the CompactState improvements, it can afford to be less memory-efficient. \$\endgroup\$
    – isaacg
    Commented May 29, 2023 at 19:35
6
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Very clever! Cutting the work in half is very impressive. \$\endgroup\$
    – isaacg
    Commented May 31, 2023 at 22:08
  • \$\begingroup\$ I’m not sure how to interpret either of your conjectures. The number of sorting networks beginning with (1,2), (1,3) is different from the number of sorting networks beginning with (1,2), (1,3), (2,3). \$\endgroup\$ Commented Jun 6, 2023 at 18:22
  • \$\begingroup\$ @AndersKaseorg What I mean to say is that the intersection of (the set of networks beginning with (1,2)) and (the set of networks beginning with (1,3)) is (the set of networks beginning with (1,2), (1,3), (2,3)) \$\endgroup\$
    – gsitcia
    Commented Jun 7, 2023 at 0:46
  • \$\begingroup\$ What's ||.|| defined as? \$\endgroup\$
    – l4m2
    Commented Jul 3, 2023 at 10:58
  • \$\begingroup\$ @l4m2 I mean the cardinality of a set. (I accidentally used \| instead of \vert) \$\endgroup\$
    – gsitcia
    Commented Jul 4, 2023 at 5:28
3
\$\begingroup\$

JavaScript (Node.js), \$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!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 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!

\$\endgroup\$
0
\$\begingroup\$

Haskell, 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!

\$\endgroup\$
0
\$\begingroup\$

Scala, \$n \leq 5\$

Port of @Arnauld's Javascript answer in Scala.

Naive brute force.

Try it online!

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
  }
}
\$\endgroup\$
1
  • \$\begingroup\$ What bruteforce? Add sorter at end? \$\endgroup\$
    – l4m2
    Commented Jul 3, 2023 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.