[PATCH] Fix iter.byperm when there are duplicates.
[Thread Prev] | [Thread Next]
- Subject: [PATCH] Fix iter.byperm when there are duplicates.
- From: Quentin Carbonneaux <quentin@xxxxxx>
- Reply-to: myrddin-dev@xxxxxxxxxxxxxx
- Date: Mon, 15 Jan 2018 21:11:02 +0000
- To: myrddin-dev@xxxxxxxxxxxxxx
Eh, I'm trying to get back in business. Cheers. --- lib/iter/perm.myr | 17 ++++++++++------- lib/iter/test/perm.myr | 17 +++++++++++++++++ 2 files changed, 27 insertions(+), 7 deletions(-) diff --git a/lib/iter/perm.myr b/lib/iter/perm.myr index 21054635..0ac8cb6c 100644 --- a/lib/iter/perm.myr +++ b/lib/iter/perm.myr @@ -47,12 +47,12 @@ impl iterable permiter(@a) -> @a[:] = if j == 0 -> false ;; - match itp.cmp(seq[j - 1], seq[j]) - | `std.After: j-- - | _: break + j-- + match itp.cmp(seq[j], seq[j + 1]) + | `std.Before: break + | _: ;; ;; - j-- /* Find highest i s.t. seq[j] < seq[i]. This @@ -62,9 +62,12 @@ impl iterable permiter(@a) -> @a[:] = */ i = seq.len - 1 while true - if i <= j - -> false - ;; + /* + By the previous loop, we know that + seq[j] < seg[j + 1], thus, in this loop, + we always have j + 1 <= i, and the array + accesses are always in bounds. + */ match itp.cmp(seq[j], seq[i]) | `std.Before: break | _: i-- diff --git a/lib/iter/test/perm.myr b/lib/iter/test/perm.myr index cfebb036..5e80a876 100644 --- a/lib/iter/test/perm.myr +++ b/lib/iter/test/perm.myr @@ -8,6 +8,7 @@ const main = { [.name = "byperm-01", .fn = byperm01], [.name = "byperm-02", .fn = byperm02], [.name = "byperm-03", .fn = byperm03], + [.name = "byperm-04", .fn = byperm04], ][:]) } @@ -52,3 +53,19 @@ const byperm03 = {c var actual : byte[:] = std.sbfin(sb) testr.check(c, std.eq(expected, actual), "expected “{}”, got “{}”", expected, actual) } + +const byperm04 = {c + var v : int[:] = [ 0, 3, 1, 1 ][:] + var nperm = 0 + + for w : iter.byperm(v, std.numcmp) + nperm++ + ;; + + /* + There are 24 permutations for 4 elements, but we get only + half because two elements are equal. + */ + const expected = 12 + testr.check(c, std.eq(expected, nperm), "expected “{}”, got “{}”", expected, nperm) +} -- 2.16.0.rc1.238.g530d649a79-goog
Re: [PATCH] Fix iter.byperm when there are duplicates. | Ori Bernstein <ori@xxxxxxxxxxxxxx> |
- Prev by Date: Re: New Trait Syntax Coming.
- Next by Date: Re: [PATCH] Fix iter.byperm when there are duplicates.
- Previous by thread: [PATCH] let bychunk() read the last element; guard for negative sz
- Next by thread: Re: [PATCH] Fix iter.byperm when there are duplicates.
- Index(es):