summaryrefslogtreecommitdiff log msg author committer range
path: root/lib/iter/perm.myr
blob: 21054635a8fb5d29c7f8bd1042eba03fa948c869 (plain)
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 ``` ``````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] } /* 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 valp# = itp.seq if itp.first itp.first = false -> true ;; /* 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 -> false ;; match itp.cmp(seq[j - 1], seq[j]) | `std.After: j-- | _: break ;; ;; j-- /* 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 ;; match itp.cmp(seq[j], seq[i]) | `std.Before: break | _: i-- ;; ;; /* 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]) i = 1 while j + i < seq.len - i std.swap(&seq[j + i], &seq[seq.len - i]) i++ ;; -> true } __iterfin__ = {itp, valp } ;; ``````