Optimizing a Rust permutation chooser for the most subsequences

Question

I had semi-recently asked a question (well a couple closely related questions) on math.stackexchange. The simplest question is phrased as follows: You are allowed to make 3 permutations of length n. You then collect the total number of distinct subsequences one finds between all 3 permutations. What is the highest number of distinct subsequences you can find between all 3 of them?

As an example, consider n = 3. Then one may choose 123, 321, and 213 as the 3 permutations. The number of distinct subsequences found between the three of them is the empty subsequence, 1, 2, 3, 12, 13, 23, 123, 32, 31, 21, 321, and 213 giving a score of 13. It turns out, no what other choice for the three permutations are made, you can't beat this score. So the function should output 13.

I have written a Rust program that searches for these optimal permutations and prints out the resulting score. @mihaild points out in the math.stackexchange post that it seems likely the to be the sequence A116702 but I would like to get further than 7 terms in. So, if you have any optimizations, please do not assume the two sequences are equivalent (that is what we are trying to confirm or deny after all!) Here is the Rust program:

src/main.rs

use std::collections::HashSet;
use itertools::Itertools;
/// Count the number of subsequences in a permutation.
fn subsequences(s: &mut Vec<usize>) -> HashSet<Vec<usize>> {
 if let Some((head, tail)) = s.split_first() {
 // Get all the subsequences of the tail via recursion.
 let h = subsequences(&mut Vec::from(tail));
 let mut h_new = HashSet::new();
 // Because it is a permutation, map the head to each sequence in h to 
 // add on to the other sequences.
 for seq in h.iter() {
 let mut v = Vec::new();
 v.push(*head);
 for e in seq.into_iter() {
 v.push(*e);
 }
 h_new.insert(v);
 }
 h_new.extend(h);
 h_new
 } else {
 let mut h = HashSet::new();
 h.insert(Vec::new());
 h
 } 
}
/// Compute f(n, 3) where:
/// f(n, 3) = max_{s1,s2,s3} |subseq(s1) U subseq(s2) U subseq(s3)|
/// See https://math.stackexchange.com/q/5083318/15140
fn max3_subseq<const N: usize>() -> usize {
 let mut best_len = 0;
 // One permutation may be fixed to be 12345...N
 let mut s1 = (0..N).collect();
 // As for the others, it is not so clear.
 let seqs1 = subsequences(&mut s1);
 for mut s2 in (0..N).permutations(N) {
 let seqs2 = subsequences(&mut s2);
 for mut s3 in (0..N).permutations(N) {
 let seqs3 = subsequences(&mut s3);
 let mut seqs = HashSet::new();
 seqs.extend(&seqs1);
 seqs.extend(&seqs2);
 seqs.extend(&seqs3);
 if seqs.len() > best_len {
 best_len = seqs.len();
 }
 }
 }
 best_len
}
fn main() {
 // I wish there was a way to propegate constants in simple loops.
 println!("{}", max3_subseq::<0>());
 println!("{}", max3_subseq::<1>());
 println!("{}", max3_subseq::<2>());
 println!("{}", max3_subseq::<3>());
 println!("{}", max3_subseq::<4>());
 println!("{}", max3_subseq::<5>());
 println!("{}", max3_subseq::<6>());
 println!("{}", max3_subseq::<7>());
 println!("{}", max3_subseq::<8>());
 println!("{}", max3_subseq::<9>());
 println!("{}", max3_subseq::<10>());
}

Cargo.toml

[package]
name = "permutation_counts"
version = "0.1.0"
edition = "2024"
[dependencies]
itertools = "0.14.0"

Answer 1

So, if you have any optimizations

With your current algorithm, you will not get much faster, as the number of permutations for a sequence of length \$n\$ is \$n!\$. With Stirling's approximation, your current max3_subseq with its \$\mathcal O (n \times n! \times n!)\$ has \$\mathcal O \left(2\pi n^2 \left(\frac{n}{e}\right)^{2n}\right)\$.

That's all a bit abstract, so let's have a look at the number of candidates and number of subsequences calls you will have:

\$n\$	\$n!\$	\$n! \times n!\$ (combinations)	\$n \times n! \times n!\$ (subsequences calls)
7	5,040	25,401,600	177,811,200
8	40,320	1,625,702,400	13,005,619,200
9	362,880	131,681,894,400	1,185,137,049,600
10	3,628,800	13,168,189,440,000	131,681,894,400,000

Roughly, for every increment of n, we see an approximate 100 times increment of the subsequences calls. No optimization of Rust code can help there.

Still, we can make your Rust code a bit faster:

$ hyperfine ./q297783.orig ./q297783.mod
Benchmark 1: ./q297783.orig
 Time (mean ± σ): 11.803 s ± 0.134 s [User: 11.797 s, System: 0.000 s]
 Range (min ... max): 11.430 s ... 11.891 s 10 runs
Benchmark 2: ./q297783.mod
 Time (mean ± σ): 11.388 s ± 0.026 s [User: 11.384 s, System: 0.000 s]
 Range (min ... max): 11.354 s ... 11.428 s 10 runs
Summary
 ./q297783.mod ran
 1.04 ± 0.01 times faster than ./q297783.orig

Remove unnecessary mut

Your subsequences doesn't require mut in its arguments, only for h_new and v.

Prefer borrowing slices to Vec

Similarly, subsequences doesn't require a Vec, it only requires an &[usize]. that removes the requirement to create a Vec from tail.

Use Vec::with_capacity if you know the resultings Vec size

In

 let mut v = Vec::new();
 v.push(*head);
 for e in seq.into_iter() {
 v.push(*e);
 }

you already know that v will have a final size of 1 + seq.len(), so use Vec::with_capacity(1 + seq.len()) to reduce the number of allocations.

All at once

fn subsequences(s: &[usize]) -> HashSet<Vec<usize>> {
 if let Some((head, tail)) = s.split_first() {
 // Get all the subsequences of the tail via recursion.
 let h = subsequences(tail);
 let mut h_new = HashSet::new();
 // Because it is a permutation, map the head to each sequence in h to
 // add on to the other sequences.
 for seq in h.iter() {
 let mut v = Vec::with_capacity(1 + seq.len());
 v.push(*head);
 v.extend(seq);
 h_new.insert(v);
 }
 h_new.extend(h);
 h_new
 } else {
 HashSet::from([vec![]])
 }
}

Other remarks

There is no reason to not use N as a regular function argument to max3_subseq, as the permuations won't get inlined with small N. I've benchmarked

fn max3_subseq(n: usize) -> usize {
 ...
}

and found no difference to your variant.

• Dair: Ah I was being too hopeful. I might be able to come up with some math tricks in addition to this to get something to work tho! Thanks!
• Zeta: There might be a math trick, @Dair, but that would probably a constructive one, instead of a search throughout the whole domain of "take two arbitrary permutations of the original sequence".