summaryrefslogtreecommitdiff
path: root/lib/iter
diff options
context:
space:
mode:
authorS. Gilles <sgilles@math.umd.edu>2017-12-31 02:49:07 -0500
committerOri Bernstein <ori@eigenstate.org>2018-01-02 10:01:45 -0800
commit6c561486a8359a7c6858be5b47170e9341633da5 (patch)
treee4fb21e3b0dd204aaa739a2bd2adb9583be9bcae /lib/iter
parent5106fe5edb4664688fe87b6340b32c0c1dbd6157 (diff)
downloadmc-6c561486a8359a7c6858be5b47170e9341633da5.tar.gz
add permutation iterator
A good exposition of this algorithm is at https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
Diffstat (limited to 'lib/iter')
-rw-r--r--lib/iter/bld.sub1
-rw-r--r--lib/iter/perm.myr77
-rw-r--r--lib/iter/test/perm.myr54
3 files changed, 132 insertions, 0 deletions
diff --git a/lib/iter/bld.sub b/lib/iter/bld.sub
index 805676a..2b8f5e3 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 0000000..c520919
--- /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 0000000..cfebb03
--- /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)
+}