[PATCH 2/2] add permutation iterator

["S. Gilles" <sgilles@xxxxxxxxxxxx>]

A good exposition of this algorithm is at
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
---
 lib/iter/bld.sub       |  1 +
 lib/iter/perm.myr      | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/iter/test/perm.myr | 54 +++++++++++++++++++++++++++++++++++
 3 files changed, 132 insertions(+)
 create mode 100644 lib/iter/perm.myr
 create mode 100644 lib/iter/test/perm.myr

diff --git a/lib/iter/bld.sub b/lib/iter/bld.sub
index f3ba696b..96d5e0c7 100644
--- a/lib/iter/bld.sub
+++ b/lib/iter/bld.sub
@@ -1,6 +1,7 @@
 lib iter =
 	chunk.myr
 	enum.myr
+	perm.myr
 	ref.myr
 	reverse.myr
 	zip.myr
diff --git a/lib/iter/perm.myr b/lib/iter/perm.myr
new file mode 100644
index 00000000..c5209195
--- /dev/null
+++ b/lib/iter/perm.myr
@@ -0,0 +1,77 @@
+use std
+
+pkg iter =
+	type permiter(@a) = struct
+		cmp	: (a : @a, b : @a -> std.order)
+		seq	: @a[:]
+		first	: bool
+	;;
+
+	impl iterable permiter(@a) -> @a[:]
+	generic byperm	: (a : @a[:], cmp : (a : @a, b : @a -> std.order) -> permiter(@a))
+;;
+
+generic byperm = {a, cmp
+	/* start off by backwards-sorting a */
+	std.sort(a, cmp)
+
+	-> [.cmp = cmp, .seq = std.sort(a, cmp), .first = true]
+}
+
+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 */
+		valp# = itp.seq
+
+		if itp.first
+			itp.first = false
+			-> true
+		;;
+
+		/* Find the longest decreasing sequence at end */
+		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 */
+
+			/* Find highest i s.t. seq[j] < seq[i] */
+			i = seq.len - 1
+			while true
+			if i <= j
+				-> false
+			;;
+			match itp.cmp(seq[j], seq[i])
+			| `std.Before: break
+			| _: i--
+			;;
+		;;
+
+		/* First, swap seq[i] and seq[j] */
+		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