summaryrefslogtreecommitdiff
path: root/lib/iter
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2018-01-01 22:00:51 -0800
committerOri Bernstein <ori@eigenstate.org>2018-01-02 10:01:47 -0800
commit7937358e3e356a62b5c52b67bc1f1daf32924a02 (patch)
treed8938f990f542641d1e8b43073dbbc3ddd92ba53 /lib/iter
parent6c561486a8359a7c6858be5b47170e9341633da5 (diff)
downloadmc-7937358e3e356a62b5c52b67bc1f1daf32924a02.tar.gz
Improve comments.
Diffstat (limited to 'lib/iter')
-rw-r--r--lib/iter/perm.myr36
1 files changed, 26 insertions, 10 deletions
diff --git a/lib/iter/perm.myr b/lib/iter/perm.myr
index c520919..2105463 100644
--- a/lib/iter/perm.myr
+++ b/lib/iter/perm.myr
@@ -18,13 +18,16 @@ generic byperm = {a, cmp
-> [.cmp = cmp, .seq = std.sort(a, cmp), .first = true]
}
+/*
+ Generates all permutations of a sequence in place,
+ mutating the sequence passed in the iterator.
+ */
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
@@ -32,7 +35,13 @@ impl iterable permiter(@a) -> @a[:] =
-> true
;;
- /* Find the longest decreasing sequence at end */
+ /*
+ 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
@@ -45,11 +54,14 @@ impl iterable permiter(@a) -> @a[:] =
;;
j--
- /* Now seq[j+1:] is all decreasing */
-
- /* Find highest i s.t. seq[j] < seq[i] */
- i = seq.len - 1
- while true
+ /*
+ 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'.
+ */
+ i = seq.len - 1
+ while true
if i <= j
-> false
;;
@@ -59,10 +71,14 @@ impl iterable permiter(@a) -> @a[:] =
;;
;;
- /* First, swap seq[i] and seq[j] */
+ /*
+ 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])