summaryrefslogtreecommitdiff
path: root/lib/iter/perm.myr
diff options
context:
space:
mode:
Diffstat (limited to 'lib/iter/perm.myr')
-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])