(* Generate constant-weight codes.

   I was thinking about the 2-of-5 code and the design of multiplexed
   capacitive touch keyboards, and it occurred to me that 7C3 was 35,
   which was probably enough keys for a usable keyboard, with three
   electrode wires going to each key, and only 7 wires in all.  And I
   hadn’t written much code lately, nothing in months in fact except a
   cellular automaton in Forth the other night.  So I wrote this
   program to enumerate the combinations explicitly. *)


(* ncm n m returns a list of all lists of m unique naturals less than n
   that are unique up to permutation.

   The Seq library in OCaml may be a better way to do this, or if
   we’re going to be eager we could memoize, but for the time being
   this is okay. *)
let rec ncm (n : int) (m : int) : int list list =
  if n < m then []              (* No possibilities left *)
  else if m == 0 then [[]]      (* One possibility: no items *)
  else (* Either we can choose the last item or we can not choose it.
          Ultimately all our choices come down to this. *)
    let chosen_n = List.map (fun xs -> n-1 :: xs) (ncm (n-1) (m-1))
    and not_chosen_n = ncm (n-1) m
    in chosen_n @ not_chosen_n
;;

if Array.length Sys.argv == 3 then
  (* XXX catch errors *)
  let n = int_of_string Sys.argv.(1)
  and m = int_of_string Sys.argv.(2)
  and a = Char.code 'a'
  in let combinations = ncm n m
  in Printf.printf "%dC%d = %d\n" n m (List.length combinations) ;
     List.iter (fun xs ->
         List.iter (fun n -> print_char(Char.chr(a + n))) (List.rev xs) ;
         print_string "\n")
       (List.rev combinations) ;
     exit 0
else
  output_string stderr ("\
Usage: " ^ Sys.argv.(0) ^ " n m
Produces all nCm unique combinations of m letters
drawn from the first n.  For example, 3 2 gives
ab, ac, and bc.  It produces about a quarter
million combinations per second.
") ;
exit (-1)