#define  MaxN        20000

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "math.h"
#include "time.h"


struct elem
{
  int el;
  struct elem * next;
};

struct conj
{
  struct elem * first;
  struct conj * next;
};

long int I_SEED = 1234567;

/* Prototypes */

float clockT ();

struct conj * comb (int , int);
int printL (struct conj * );

/*   --->  I/O variables  */

char  file_code[4];

FILE  *p_out;

/****************************************************************/
/*								*/
/*								*/
/****************************************************************/

main()

{
  struct conj * L;

  int n,m;

  printf(" n:");
  scanf("%d", &n);
  printf(" m:");
  scanf("%d", &m);


  /* Gera combinacoes de n m a m  */

  printf("Clock: %f \n", clockT() );

  L = comb(n, m);
     
  printf("Clock: %f \n", clockT() );

  n = printL (L);

  printf("Clock: %f \n", clockT() );

}




/****************************************************************/
/*								*/
/*								*/
/****************************************************************/

int printL( struct conj *L )
{
  struct conj *currC;
  struct elem * curr;
  int cont;

  printf("\n Combinacoes \n");
  currC = L;
  cont = 0;
  while ( currC != NULL )
    {
      cont++;
      printf(" %4d : ", cont);
      curr = currC->first;
      while (curr != NULL)
	{
	  printf(" %d ",curr->el);
	  curr = curr->next;
	}
      printf("\n");
      currC = currC->next;
    }

}


/****************************************************************/
/*								*/
/*								*/
/****************************************************************/

struct conj * comb(int n, int m)
{
  struct conj *L1, *L2, *L, *currC, *prevC;
  struct elem *add, *curr;
  int i;

  if  (m == 0) return (NULL);
  if  (n == m)
    {
      L = (struct conj *) malloc( sizeof(struct conj) );
      add = (struct elem *) malloc( sizeof(struct elem) );
      L->first = add;
      L->next = NULL;
      add->el = n;
      add->next = NULL;
      curr = add;
      for (i=n-1; i>=1; i--)
	{
	  add = (struct elem *) malloc( sizeof(struct elem) );
	  add->el = i;
	  add->next = NULL;
	  curr->next = add;
	  curr = add;
	}
      return ( L );
    }

  L1 = comb(n-1,m);

  L2 = comb(n-1,m-1);


  /* Adiciona n-esimo elemento `a L2 */

  currC = L2;
  prevC = currC;
  while (currC != NULL)
    {
      add = (struct elem *) malloc( sizeof(struct elem) );
      add->el = n;
      add->next = currC->first;
      currC->first = add;
      prevC = currC;
      currC = currC->next;
    }

  /* Se L2 esta' vazia, ela devera' passar a conter somente
     un conjunto com o elemente n, i.e. L2' = { {n} }  */

  if (L2 == NULL)
    {
      L2 = (struct conj *) malloc( sizeof(struct conj) );
      add = (struct elem *) malloc( sizeof(struct elem) );
      L2->first = add;
      L2->next = NULL;
      add->el = n;
      add->next = NULL;
      prevC = L2;
    }

  /* Concatena as listas */

  prevC->next = L1;
  return(L2);

}



/****************************************************************/
/*                                                              */
/*                                                              */
/****************************************************************/

float clockT ( )
{
    unsigned long int ti;

    ti = clock();
    return( ((float)ti)/1000000. );

}