From ffc8e8c2695d61e97fd7b69fb658f6cb1d8e13a2 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Tue, 26 Dec 2023 21:14:33 -0800 Subject: comb: bug: missing combinations. The comb function is broken; some combinations of items are missing in the output. This is because the iteration reset step in comb_gen_fun_common handles only one column of the state, neglecting to reset the other columns: what is now done by the for (j = i ... loop. I'm changing the representation of the state from a list of lists to a vector of lists. Moreover, it is not reversed. This allows the loop in comb_gen_fun_common to perform random access. * combi.c (k_conses): Return a vector, that is not reversed. (comb_init): New helper function to slightly abstract the use of k_conses. (comb_while_fun): Termination now occurs if the state vector is nil (degenerate case, like k items chosen from n, when k > n), or if the vector has nil in element zero (special flag situation). (comb_gen_fun_common): Rewritten, with correction. The logic is similar. Since we have random access, we don't need the "prev" variable. When we reset a column iterator, we now also populate all the columns to the right of it. For instance, if a given column resets to (a b c), the one to the right must reset to (b c), and so on. In the broken function, this is what was not done, resulting in missing items due to, say, a column resetting to (a b c) but the one next to it remaining at (c). (comb_list_gen_fun): Drop nreverse. (comb_vec_gen_fun, comb_str_gen_fun, comb_hash_gen_fun): Use the same i iterator for the state and the output object, accessing the vector directly. (comb_list, comb_vec, comb_str, comb_hash): Use comb_init. * tests/015/comb.tl: New file. --- tests/015/comb.tl | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 116 insertions(+) create mode 100644 tests/015/comb.tl (limited to 'tests/015') diff --git a/tests/015/comb.tl b/tests/015/comb.tl new file mode 100644 index 00000000..c60b8f2a --- /dev/null +++ b/tests/015/comb.tl @@ -0,0 +1,116 @@ +(load "../common") + +(defun normtype (obj) + (etypecase obj + (null 'list) + (cons 'list) + (lit 'string) + (str 'string) + (vec 'vec))) + +(defun test-comb (s k) + (let ((out (comb s k)) + (nCk (n-choose-k (len s) k))) + (if (> k (len s)) + (test out nil) + (mvtest + (len out) nCk + (len (uniq out)) nCk)) + (vtest + (sort out) out) + (unless (empty out) + (let ((stype (normtype s)) + (otype (normtype (first out)))) + (vtest stype otype))))) + +(test-comb #() 0) +(test-comb #() 1) +(test-comb #(1) 0) +(test-comb #(1) 1) +(test-comb #(1) 2) +(test-comb #(1 2) 0) +(test-comb #(1 2) 1) +(test-comb #(1 2) 2) +(test-comb #(1 2) 3) +(test-comb #(1 2 3) 0) +(test-comb #(1 2 3) 1) +(test-comb #(1 2 3) 2) +(test-comb #(1 2 3) 3) +(test-comb #(1 2 3) 4) +(test-comb #(1 2 3 4) 0) +(test-comb #(1 2 3 4) 1) +(test-comb #(1 2 3 4) 2) +(test-comb #(1 2 3 4) 3) +(test-comb #(1 2 3 4) 4) +(test-comb #(1 2 3 4) 5) +(test-comb #(1 2 3 4 5) 0) +(test-comb #(1 2 3 4 5) 1) +(test-comb #(1 2 3 4 5) 2) +(test-comb #(1 2 3 4 5) 3) +(test-comb #(1 2 3 4 5) 4) +(test-comb #(1 2 3 4 5) 5) +(test-comb #(1 2 3 4 5) 5) + +(test-comb '() 0) +(test-comb '() 1) +(test-comb '(1) 0) +(test-comb '(1) 1) +(test-comb '(1) 2) +(test-comb '(1 2) 0) +(test-comb '(1 2) 1) +(test-comb '(1 2) 2) +(test-comb '(1 2) 3) +(test-comb '(1 2 3) 0) +(test-comb '(1 2 3) 1) +(test-comb '(1 2 3) 2) +(test-comb '(1 2 3) 3) +(test-comb '(1 2 3) 4) +(test-comb '(1 2 3 4) 0) +(test-comb '(1 2 3 4) 1) +(test-comb '(1 2 3 4) 2) +(test-comb '(1 2 3 4) 3) +(test-comb '(1 2 3 4) 4) +(test-comb '(1 2 3 4) 5) +(test-comb '(1 2 3 4 5) 0) +(test-comb '(1 2 3 4 5) 1) +(test-comb '(1 2 3 4 5) 2) +(test-comb '(1 2 3 4 5) 3) +(test-comb '(1 2 3 4 5) 4) +(test-comb '(1 2 3 4 5) 5) +(test-comb '(1 2 3 4 5) 5) + +(test-comb "" 0) +(test-comb "" 1) +(test-comb "1" 0) +(test-comb "1" 1) +(test-comb "1" 2) +(test-comb "12" 0) +(test-comb "12" 1) +(test-comb "12" 2) +(test-comb "12" 3) +(test-comb "123" 0) +(test-comb "123" 1) +(test-comb "123" 2) +(test-comb "123" 3) +(test-comb "123" 4) +(test-comb "1234" 0) +(test-comb "1234" 1) +(test-comb "1234" 2) +(test-comb "1234" 3) +(test-comb "1234" 4) +(test-comb "1234" 5) +(test-comb "12345" 0) +(test-comb "12345" 1) +(test-comb "12345" 2) +(test-comb "12345" 3) +(test-comb "12345" 4) +(test-comb "12345" 5) +(test-comb "12345" 5) + +(mtest + (comb #() -1) :error + (comb #(1) -1) :error + (comb () -1) :error + (comb '(1) -1) :error + (comb "" -1) :error + (comb "a" -1) :error) -- cgit v1.2.3