comb.c

Go to the documentation of this file.

#include <stdio.h>
#include <stdlib.h>
#include "comb.h"
#include "error.h"
#include "standard.h"

combinations *new_combinations(int numbers[], int n, int r)
     /*
      * Makes a combinations record which can be used in successive calls
      * to next_combination() in order to go through all the combinations
      * of length r from a set of numbers of length n. 
      */
{
  int i;
  combinations *bob = (combinations *) malloc(sizeof(combinations));
  if (bob != NULL) {
    bob->n = n;
    bob->r = r;
    bob->numbers = (int *) malloc(n * sizeof(int));

    if ((bob->numbers==NULL) && (n>0))
      error("new_combinations", "malloc failed..");
    else {
      for (i=0; i<n; i++)
        bob->numbers[i] = numbers[i];
    }

    bob->curr = (int *) malloc(r * sizeof(int));
    bob->next = (int *) malloc(r * sizeof(int)); 
    if (((bob->curr == NULL) || (bob->next == NULL)) && (r > 0)) {
      error("new_combinations", "malloc failed...");
    }
    else {
      for (i=0; i<r; i++)
        bob->next[i] = i;
    }
    
    bob->x = (int *) malloc(r * sizeof(int));
    if ((bob->x == NULL)&&(r>0)) {
      error("new_combinations", "malloc failed....");
    }
    else {
      for (i=0; i<r; i++) 
        bob->x[i] = bob->numbers[i];
    }
    bob->last = 0;
  }
  else {
    error("new_combinations", "malloc failed.");
  }
  return (bob);
}


static int incr(int *x, int n, int r)
     /*
      * Increments combination pointers.  
      * Returns 0 iff the input was the last combination. 
      */
{
  int tmp;

  if (r <= 0) {
    return (0);
  }
  else  if (r == 1) {
    return (++x[0] < n);
  } 
  else {
    if (++x[r-1] >= n) {
      tmp = incr(x, n-1, r-1);
      x[r-1] = x[r-2]+1;
      return(tmp);
    }
    else {
      return(1);
    }
  }
}


int *next_combination(combinations *bob)
     /*
      * Returns a pointer to an array of integers describing the next 
      * combination of the array of numbers stored in (bob).  
      */
{
  int *this = NULL;
  int i;
  if (bob != NULL) {
    if (!bob->last) {
      for (i=0; i<bob->r; i++) {
        bob->curr[i] = bob->next[i];
        bob->x[i] = bob->numbers[bob->curr[i]];
      }
      this = bob->x;
      if (!incr(bob->next, bob->n, bob->r))
        bob->last = 1;
    }
  } 
  else {
    warn("next_combination", "invalid combinations.");
  }
  return (this);
}


void close_combinations(combinations *bob)
     /*
      * Frees some memory.
      */
{
  if (bob != NULL) {
    if (bob->numbers != NULL)
      free(bob->numbers);
    if (bob->curr != NULL)
      free(bob->curr);
    if (bob->next != NULL)
      free(bob->next);
    if (bob->x != NULL)
      free(bob->x);
    free(bob);
  }
}

---