Re: [PATCH 2/2] add permutation iterator

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

Sorry for taking a while to review this. Overall, it looks pretty good,
just a few minor nits. I've already made them on my local branch, so
as long as they look good to you, I can push.

On Sun, 31 Dec 2017 02:49:07 -0500, "S. Gilles" <sgilles@xxxxxxxxxxxx> wrote:

> A good exposition of this algorithm is at
> https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

<snip>

> +generic byperm = {a, cmp
> +	/* start off by backwards-sorting a */
> +	std.sort(a, cmp)

Hm. Since we need random access, it looks like this might need to have a
slice, even after the new syntax lands. That's unfortunate, I suppose,
but unavoidable.

> +impl iterable permiter(@a) -> @a[:] =
> +	__iternext__ = {itp, valp
> +		var j : std.size = seq.len - 1
> +		var i : std.size = seq.len - 1
> +		var seq : @a[:] = itp.seq
> +
> +		/* We're permuting seq in place */

Moved this comment up.

> +		valp# = itp.seq
> +
> +		if itp.first
> +			itp.first = false
> +			-> true
> +		;;
> +
> +		/* Find the longest decreasing sequence at end */

Yes, but why? Proposing this replacement:

		/*
		  To generate the next permutation, we need
		  to increase the sequence by as little as
		  possible. That means that we start by finding
		  the longest monotonically decreasing trailing
		  sequence.
		 */

> +		j = seq.len - 1
> +		while true
> +			if j == 0
> +				-> false
> +			;;
> +			match itp.cmp(seq[j - 1], seq[j])
> +			| `std.After: j--
> +			| _: break
> +			;;
> +		;;
> +		j--
> +
> +			/* Now seq[j+1:] is all decreasing */

This comment also doesn't add much; if the previous code worked,
we already know this. I'd like to propose another comment that
explains why we're doing it:

		/* 
		  Find highest i s.t. seq[j] < seq[i]. This
		  is the index that will maintain the order of
		  the suffix, while increasing the value of the
		  element in the 'pivot'.
		 */

> +
> +			/* Find highest i s.t. seq[j] < seq[i] */
> +			i = seq.len - 1
> +			while true

Indentation seemed a bit screwed up. Fixed it.

> +			if i <= j
> +				-> false
> +			;;
> +			match itp.cmp(seq[j], seq[i])
> +			| `std.Before: break
> +			| _: i--
> +			;;
> +		;;
> +
> +		/* First, swap seq[i] and seq[j] */

And, another comment change:

		/*
		  Then, swap seq[i] and seq[j] and reverse the
		  sequence. Because the suffix was in decreasing
		  order, reversing it means that our sequence is
		  now in increasing order: ie, our most significant
		  place has the smallest value.
		 */

> +		std.swap(&seq[i], &seq[j])
> +
> +		/* Now reverse seq[j+1:] */
> +		i = 1
> +		while j + i < seq.len - i
> +			std.swap(&seq[j + i], &seq[seq.len - i])
> +			i++
> +		;;
> +
> +		-> true
> +	}
> +
> +	__iterfin__ = {itp, valp
> +	}
> +;;
> diff --git a/lib/iter/test/perm.myr b/lib/iter/test/perm.myr
> new file mode 100644
> index 00000000..cfebb036
> --- /dev/null
> +++ b/lib/iter/test/perm.myr
> @@ -0,0 +1,54 @@
> +use std
> +use testr
> +
> +use iter
> +
> +const main = {
> +	testr.run([
> +		[.name = "byperm-01", .fn = byperm01],
> +		[.name = "byperm-02", .fn = byperm02],
> +		[.name = "byperm-03", .fn = byperm03],
> +	][:])
> +}
> +
> +const byperm01 = {c
> +	var v : int[:] = [ 0, 2, 1 ][:]
> +	var sb : std.strbuf# = std.mksb()
> +	std.sbfmt(sb, " ")
> +
> +	for w : iter.byperm(v, std.numcmp)
> +		std.sbfmt(sb, "{} ", w)
> +	;;
> +
> +	var expected : byte[:] = " [0, 1, 2] [0, 2, 1] [1, 0, 2] [1, 2, 0] [2, 0, 1] [2, 1, 0] "
> +	var actual : byte[:] = std.sbfin(sb)
> +	testr.check(c, std.eq(expected, actual), "expected “{}”, got “{}”", expected, actual)
> +}
> +
> +const byperm02 = {c
> +	var v : int[:] = [ 1, 1 ][:]
> +	var sb : std.strbuf# = std.mksb()
> +	std.sbfmt(sb, " ")
> +
> +	for w : iter.byperm(v, std.numcmp)
> +		std.sbfmt(sb, "{} ", w)
> +	;;
> +
> +	var expected : byte[:] = " [1, 1] "
> +	var actual : byte[:] = std.sbfin(sb)
> +	testr.check(c, std.eq(expected, actual), "expected “{}”, got “{}”", expected, actual)
> +}
> +
> +const byperm03 = {c
> +	var v : int[:] = [ 3, 1, 1 ][:]
> +	var sb : std.strbuf# = std.mksb()
> +	std.sbfmt(sb, " ")
> +
> +	for w : iter.byperm(v, std.numcmp)
> +		std.sbfmt(sb, "{} ", w)
> +	;;
> +
> +	var expected : byte[:] = " [1, 1, 3] [1, 3, 1] [3, 1, 1] "
> +	var actual : byte[:] = std.sbfin(sb)
> +	testr.check(c, std.eq(expected, actual), "expected “{}”, got “{}”", expected, actual)
> +}
> -- 
> 2.15.1
> 
> 


-- 
    Ori Bernstein