shithub: mc

Info  •  Files  •  Log  •  Branches

Fix iter.byperm when there are duplicates.

Eh, I'm trying to get back in business.

Cheers.

--- a/lib/iter/perm.myr

+++ b/lib/iter/perm.myr

@@ -47,12 +47,12 @@

 			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 @@

 		 */

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

--- a/lib/iter/test/perm.myr

+++ b/lib/iter/test/perm.myr

@@ -8,6 +8,7 @@

 		[.name = "byperm-01", .fn = byperm01],

 		[.name = "byperm-02", .fn = byperm02],

 		[.name = "byperm-03", .fn = byperm03],

+		[.name = "byperm-04", .fn = byperm04],

 	][:])

 }

@@ -51,4 +52,20 @@

 	var expected : byte[:] = " [1, 1, 3] [1, 3, 1] [3, 1, 1] "

 	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)

 }