**diff options**

author | Ori Bernstein <ori@eigenstate.org> | 2018-01-01 22:00:51 -0800 |
---|---|---|

committer | Ori Bernstein <ori@eigenstate.org> | 2018-01-02 10:01:47 -0800 |

commit | 7937358e3e356a62b5c52b67bc1f1daf32924a02 (patch) | |

tree | d8938f990f542641d1e8b43073dbbc3ddd92ba53 /lib/iter/perm.myr | |

parent | 6c561486a8359a7c6858be5b47170e9341633da5 (diff) | |

download | mc-7937358e3e356a62b5c52b67bc1f1daf32924a02.tar.gz |

Improve comments.

Diffstat (limited to 'lib/iter/perm.myr')

-rw-r--r-- | lib/iter/perm.myr | 36 |

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]) |