Eigenstate: myrddin-dev mailing list

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] Fix iter.byperm when there are duplicates.


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


Follow-Ups:
Re: [PATCH] Fix iter.byperm when there are duplicates.Ori Bernstein <ori@xxxxxxxxxxxxxx>