To learn I'm solving some Euler Problems in Rust (and I'm having good headaches. Rust is more fun than a Rubik cube).
This is a simple D language solution of the problem #24 (What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?):
import std.algorithm, std.array, std.string;
size_t fac(in size_t n) @nogc { return n ? n * fac(n - 1) : 1; }
void n_lexi_perm(ubyte[] xs, size_t n) @nogc {
while (!xs.empty) {
immutable m = fac(xs.length - 1);
immutable y = n / m;
bringToFront(xs[0 .. y], xs[y .. y + 1]);
xs.popFront;
n %= m;
}
}
void main() {
char[10] s = "0123456789";
n_lexi_perm(s.representation, 999999);
assert(s == "2783915460");
}
And this is the solution I've managed to write in Rust so far:
#![feature(iter_arith)]
fn main() {
fn n_lexi_perm(xs: &mut [u8], n: usize) {
if xs.is_empty() { return; }
let m: usize = (1 .. xs.len()).product();
let y = n / m;
xs[0 .. y + 1].reverse();
xs[1 .. y + 1].reverse();
n_lexi_perm(&mut xs[1 ..], n % m);
}
let mut s = *b"0123456789";
n_lexi_perm(&mut s, 999_999);
assert_eq!(&s, b"2783915460");
}
Is such Rust code good? Do you have suggestions?
Some of the problems I've found:
I was unable to make the Rust version iterative. Can you show me how to do it?
I was unable to find a bringToFront algorithm in the Rust std lib, it's called "rotate" in C++: std.algorithm.mutation - D Programming Language rotate - C++ Reference
If this algorithm is not present in the Rust std lib then I suggest to add it, because it's quite fundamental and famous.
Rust borrow checker: Making obvious code non-obvious since 2013. Fortunately, though, that's because the most obvious thing one can do with mutable references in a systems language is shoot yourself in the foot. Your example is just collateral damage.
The obvious loopification of the tail-recursive solution results in the line xs = &mut xs[1..] and rust doesn't seem to handle recursive mutable borrow checking very well, giving a frustrating compiler error for which the workaround is not obvious. The key trick is to separate lifetimes of each loop iteration by
moving the mutable reference into a temporary (using mem::replace which disconnects the lifetimes),
doing logic on the temporary, and then
moving the mutable reference back.
Since & mut[u8] is not nullable, the common way to swap out the mutable reference is to wrap it in an Option.
#![feature(iter_arith)]
use std::mem;
fn main() {
fn n_lexi_perm(xs_: &mut [u8], n: usize) {
let mut n = n;
let mut xs_wrapped = Some(xs_);
loop {
// Replace xs_wrapped with a None, detaching the lifetime and
// moving the borrowed mutable into a temporary.
let xs = mem::replace(&mut xs_wrapped, None).unwrap();
if xs.is_empty() { break; }
let m: usize = (1 .. xs.len()).product();
let y = n / m;
xs[0 .. y + 1].reverse();
xs[1 .. y + 1].reverse();
n = n % m;
// Move the temporary back into the wrapped loop variable for
// the next iteration.
xs_wrapped = Some(&mut xs[1..]);
}
}
let mut s = *b"0123456789";
n_lexi_perm(&mut s, 999_999);
assert_eq!(&s, b"2783915460");
}
The main tricks I have learned regarding handling borrow errors have been from Gankro's excellent Learning Rust With Entirely Too Many Linked Lists writeup which exposes the reader to many common compiler errors encountered when coding rust.
The trick actually works without Option, because variables can be temporarily left uninitialised, as long as they're not used:
fn n_lexi_perm(mut xs: &mut [u8], n: usize) {
let mut n = n;
while !xs.is_empty() {
let m: usize = (1 .. xs.len()).product();
let y = n / m;
xs[0 .. y + 1].reverse();
xs[1 .. y + 1].reverse();
let tmp = xs;
xs = &mut tmp[1..];
n %= m;
}
}
Specifically, the let tmp line ensures the compiler understands what is going on.
Rust used to have next_permutation for slices to produce the next lexicographical permutation. Seeing how it's now been deprecated & removed, and I couldn't find it on crates.io, I added those functions to crate permutohedron.
