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.

2 files changed, 174 insertions, 39 deletions

diff --git a/combi.c b/combi.c
index 5d116aed..79787f04 100644
--- a/combi.c
+++ b/combi.c
@@ -362,57 +362,73 @@ val rperm(val seq, val k)
   }
 }
 
-
-static val k_conses(val list, val k)
+static val k_conses(val list, val k, val self)
 {
-  val iter = list, i = k;
-  list_collect_decl (out, ptail);
+  cnum i, n = c_num(k, self);
+  val iter, out = vector(num(n), nil);
 
-  for (; consp(iter) && gt(i, zero); iter = cdr(iter), i = minus(i, one))
-    ptail = list_collect(ptail, iter);
+  for (iter = list, i = 0; i < n && iter; iter = cdr(iter), i++)
+    out->v.vec[i] = iter;
 
-  return (i != zero) ? nil : out;
+  return (i >= n) ? out : nil;
+}
+
+static val comb_init(val list, val k)
+{
+  if (zerop(k))
+    return nil;
+  return k_conses(list, k, lit("comb"));
 }
 
 static val comb_while_fun(val state)
 {
-  return car(state);
+  if (state) {
+    cnum nn = c_num(length_vec(state), lit("comb"));
+    return tnil(nn > 0 && state->v.vec[0]);
+  }
+  return nil;
 }
 
 static void comb_gen_fun_common(val state)
 {
-  val iter;
-  val prev = nil;
+  cnum i, nn = c_num(length_vec(state), lit("comb"));
 
-  for (iter = state; consp(iter); iter = cdr(iter)) {
-    val curr = first(iter);
-    val curr_rest = rest(curr);
-    if (curr_rest != prev && consp(curr_rest)) {
-      rplaca(iter, curr_rest);
+  for (i = nn - 1; i >= 0; i--)
+  {
+    val cur = state->v.vec[i];
+    val re = rest(cur);
+
+    if ((i == nn - 1 && re) ||
+        (i < nn - 1 && re != state->v.vec[i + 1]))
+    {
+      state->v.vec[i] = re;
       return;
-    } else if (rest(iter)) {
-      val next = second(iter);
-      val next_rest = rest(next);
-      val next_rest_rest = rest(next_rest);
-      prev = curr;
-      if (next_rest != curr && consp(next_rest_rest))
-        prev = sys_rplaca(iter, next_rest_rest);
+    } else if (i > 0) {
+      val nxt = state->v.vec[i - 1];
+      val nxt_r = cdr(nxt);
+      val nxt_r_r = cdr(nxt_r);
+
+      if (nxt_r != cur && consp(nxt_r_r)) {
+        cnum j;
+        for (j = i; j < nn; j++, nxt_r_r = cdr(nxt_r_r))
+          state->v.vec[j] = nxt_r_r;
+      }
     }
   }
 
-  rplaca(state, nil);
+  state->v.vec[0] = nil;
 }
 
 static val comb_list_gen_fun(val state)
 {
-  val out = nreverse(mapcar(car_f, state));
+  val out = mapcar_listout(car_f, state);
   comb_gen_fun_common(state);
   return out;
 }
 
 static val comb_list(val list, val k)
 {
-  val state = nreverse(k_conses(list, k));
+  val state = comb_init(list, k);
   return state ? generate(func_f0(state, comb_while_fun),
                           func_f0(state, comb_list_gen_fun))
                : nil;
@@ -421,12 +437,12 @@ static val comb_list(val list, val k)
 static val comb_vec_gen_fun(val state)
 {
   val self = lit("comb");
-  val nn = length_list(state);
+  val nn = length_vec(state);
   cnum i, n = c_num(nn, self);
-  val iter, out = vector(nn, nil);
+  val out = vector(nn, nil);
 
-  for (iter = state, i = n - 1; i >= 0; iter = cdr(iter), i--)
-    out->v.vec[i] = car(car(iter));
+  for (i = 0; i < n; i++)
+    out->v.vec[i] = car(state->v.vec[i]);
 
   comb_gen_fun_common(state);
   return out;
@@ -434,7 +450,7 @@ static val comb_vec_gen_fun(val state)
 
 static val comb_vec(val vec, val k)
 {
-  val state = nreverse(k_conses(list_vec(vec), k));
+  val state = comb_init(list_vec(vec), k);
   return generate(func_f0(state, comb_while_fun),
                   func_f0(state, comb_vec_gen_fun));
 }
@@ -442,14 +458,14 @@ static val comb_vec(val vec, val k)
 static val comb_str_gen_fun(val state)
 {
   val self = lit("comb");
-  val nn = length_list(state);
+  val nn = length_vec(state);
   cnum i, n = c_num(nn, self);
-  val iter, out = mkustring(nn);
+  val out = mkustring(nn);
 
   out->st.str[n] = 0;
 
-  for (iter = state, i = n - 1; i >= 0; iter = cdr(iter), i--)
-    out->st.str[i] = c_chr(car(car(iter)));
+  for (i = 0; i < n; i++)
+    out->st.str[i] = c_chr(car(state->v.vec[i]));
 
   comb_gen_fun_common(state);
   return out;
@@ -457,7 +473,7 @@ static val comb_str_gen_fun(val state)
 
 static val comb_str(val str, val k)
 {
-  val state = nreverse(k_conses(list_str(str), k));
+  val state = comb_init(list_str(str), k);
   return generate(func_f0(state, comb_while_fun),
                   func_f0(state, comb_str_gen_fun));
 }
@@ -469,11 +485,14 @@ static val comb_hash_while_fun(val state)
 
 static val comb_hash_gen_fun(val hstate)
 {
+  val self = lit("comb");
   cons_bind (state, hash, hstate);
-  val iter, out = make_similar_hash(hash);
+  val nn = length_vec(state);
+  cnum i, n = c_num(nn, self);
+  val out = make_similar_hash(hash);
 
-  for (iter = state; iter; iter = cdr(iter)) {
-    val pair = car(car(iter));
+  for (i = 0; i < n; i++) {
+    val pair = car(state->v.vec[i]);
     sethash(out, car(pair), cdr(pair));
   }
 
@@ -484,7 +503,7 @@ static val comb_hash_gen_fun(val hstate)
 
 static val comb_hash(val hash, val k)
 {
-  val hstate = cons(nreverse(k_conses(hash_alist(hash), k)), hash);
+  val hstate = cons(comb_init(hash_alist(hash), k), hash);
   return generate(func_f0(hstate, comb_hash_while_fun),
                   func_f0(hstate, comb_hash_gen_fun));
 }
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)