| Bytes | Lang | Time | Link |
|---|---|---|---|
| 005 | C++ GCC | 241206T130831Z | 138 Aspe |
| 005 | Scala | 230608T115156Z | 138 Aspe |
| 061 | Rust | 230531T172525Z | gsitcia |
| 623 | Rust | 230528T185939Z | isaacg |
| 005 | Haskell | 230529T163627Z | Roman Cz |
| 659 | Rust | 230526T205734Z | Anders K |
| 004 | Haskell | 230526T203459Z | Roman Cz |
| 005 | JavaScript Node.js | 230526T170241Z | Arnauld |
C++ (GCC), \$n\leq 5\$
C++ port of @Arnauld's Javascript answer.
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <functional>
// Generate all permutations of the vector [0, 1, 2, ..., n-1]
static std::vector<std::vector<int>> getPermutations(int n) {
std::vector<int> base(n);
for (int i = 0; i < n; ++i) {
base[i] = i;
}
std::vector<std::vector<int>> perms;
do {
perms.push_back(base);
} while (std::next_permutation(base.begin(), base.end()));
return perms;
}
int solve(int n) {
// Build connector pairs: all pairs (i,j) with i<j
std::vector<std::pair<int,int>> connector;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
connector.push_back(std::make_pair(i,j));
}
}
// Get all permutations of length n
auto perm = getPermutations(n);
// Build a lookup from permutation to index
// We'll use a map<vector<int>, int> for lookup
std::map<std::vector<int>, int> lookup;
for (int i = 0; i < (int)perm.size(); ++i) {
lookup[perm[i]] = i;
}
// transform is essentially a list of transformations for each connector pair
// For each pair (i, j), we build a vector<int> that maps each perm index to a new perm index
std::vector<std::vector<int>> transform;
for (auto &c : connector) {
int ci = c.first;
int cj = c.second;
std::vector<int> t;
t.reserve(perm.size());
for (auto p : perm) {
// If p[ci] > p[cj], swap them
if (p[ci] > p[cj]) {
int temp = p[ci];
p[ci] = p[cj];
p[cj] = temp;
}
t.push_back(lookup[p]);
}
transform.push_back(t);
}
// We'll do a DFS over states (list of permutation indices)
// Initial state is [0,1,2,...] same length as perm
std::vector<int> initialState(perm.size());
for (int i = 0; i < (int)perm.size(); i++) {
initialState[i] = i;
}
// We'll keep a set of visited states
std::set<std::vector<int>> visited;
std::function<void(const std::vector<int>&)> search = [&](const std::vector<int> &list) {
if (visited.find(list) != visited.end()) return;
visited.insert(list);
for (auto &t : transform) {
bool update = false;
std::vector<int> newList(list.size());
for (size_t idx = 0; idx < list.size(); idx++) {
int permNdx = list[idx];
int newNdx = t[permNdx];
if (newNdx != permNdx) update = true;
newList[idx] = newNdx;
}
if (update) {
search(newList);
}
}
};
search(initialState);
return (int)visited.size();
}
int main() {
for (int n = 1; n <= 5; n++) {
std::cout << n << " " << solve(n) << std::endl;
}
return 0;
}
Scala, \$n \leq 5\$
Port of @Arnauld's Javascript answer in Scala.
Naive brute force.
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
}
}
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.
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.
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]
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));
}
}
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]]
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;
}