type indice == int;;
type partie == indice list;;

(* Première partie*)

let rec card = function [] -> 0 |i::q -> 1 + card q;;

let rec delta p1 p2 =
  match p1,p2 with
     [],_ -> p2
    |_,[] -> p1
    |i1::q1,i2::q2 when i1 = i2 -> delta q1 q2
    |i1::q1,i2::_ when i1 < i2 -> i1::delta q1 p2
    |_,i2::q2 -> i2::delta p1 q2;;
    
let test p1 p2 =
  let rec imprime_partie = function
    [] -> print_newline ()
   |i::q -> printf__printf "%d " i;  imprime_partie q
  in imprime_partie (delta p1 p2);;
  
(* Deuxième partie *)

let succ p =
  let rec insere j = function
    [] -> [j] |i::q when j < i -> j::i::q |i::q -> (* cas j = i *) insere (j+1) q
  in insere 0 p;;

let test_incr N =
  let p1 = ref [] and p2 = ref []
  in
  while card !p1 <> N do
    p2 := succ !p1;
    test !p1 !p2;
    print_newline ();
    p1 := !p2
  done;
  test !p1 [];;
  
(* Troisième partie *)

let test_gray N =
  let rec T n =
    match n with
       0 -> []
      |_ -> let l = T (n-1) in l@((n-1)::l)
  in
  let f i = printf__printf "%d " i; print_newline()
  in
  do_list f (T N);
  printf__printf "%d " (N-1); print_newline();;
  
let rec gray = function
   [] -> [0]
  |p -> if (card p) mod 2 = 0 then delta p [0] else delta p [1 + hd p];;

(* Quatrième partie *)

let rec test_sur p1 p2 =
  match p1,p2 with
     [],_ -> do_list (printf__printf "%d ") p2
    |_,[] -> do_list (printf__printf "%d ") p1
    |i1::q1,i2::_ when i1 < i2 -> printf__printf "%d " i1;
                                  test_sur q1 p2
    |i1::q1,i2::q2 when i1 = i2 -> test_sur q1 q2
    |i1::q1,i2::q2 -> test_sur p1 q2;
                      printf__printf "%d " i2;;
                      
let test_panne N K =
  let rec T n k =
    match n,k with
       1,_ -> [0]
      |_,1 -> (T (n-1) 1) @ [n - 2;n - 1]
      |_ -> (T (n-1) k) @ [n - 1] @ (rev (T (n - 1) (k - 1)))
  in
  do_list (printf__printf "%d ") (T N K);
  printf__printf "%d " (N - 1);;