Program: Permutations and combinations

After a long hiatus from writing mind-numbing and skull-cracking(i.e. meaningless and inefficient) programs which used to be my hallmark, I have decided to reestablish myself. And this time, the target is the field of combinatorics. Yes, this time I have decided to attack and desecrate an entire field with my thoughts and observations rather than restrict myself to individual problems.

As a part of this massacre, I had a go at writing a couple of programs to generate permutations and combinations. I proudly present thee these programs:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 * In order to generate permutations of a string, say, abcde,
 * pluck 'a' and then generate all permutations of bcde,
 * pluck 'b' and generate all permutations of acde,
 * pluck 'c' and generate all permutations of abde,
 * and so on.
 */

void rotate_left(char *a)
{
  int i, n = strlen(a);
  char temp = a[0];
  for(i=0;i<n-1;i++)
      a[i] = a[i+1];
  a[i] = temp;
}

int gen_perms(char *prestr, char *str)
{
  static int nperms = 0;
  int i, n, np;
  char *tempstr, *newprestr;

  n = strlen(str);
  np = strlen(prestr);

  if(n==1) {
      printf(prestr);
      printf(str);
      printf("\n");
      nperms++;
      return nperms;
  }

  tempstr = (char*)malloc(n*sizeof(char));
  newprestr = (char*)malloc((np+2)*sizeof(char));

  for(i=0;i<n;i++) {
      strcpy(tempstr, str+1);

      strcpy(newprestr, prestr);
      newprestr[np]=str[0];
      newprestr[np+1]='\0';

      gen_perms(newprestr, tempstr);
      rotate_left(str);
  }
  free(newprestr);
  free(tempstr);

  return nperms;
}

void generate_perms(char *a)
{
  int nperms = gen_perms("", a);
  printf("\nTotal number of permutations: %d\n", nperms);
}

int main(int argc, char *argv[])
{
  int i,n;
  char *a;

  if(argc!=2) {
      printf("\nUsage: generate_perms <numelems>\n");
      return 1;
  }
  sscanf(argv[1], "%d", &n);

  if(n<0) {
      printf("\nInvalid input\n");
      return 1;
  }

  a = (char*)malloc((n+1)*sizeof(char));
  for(i=0;i<n;i++)
      a[i]='a'+i;
  a[n]='\0';

  generate_perms(a);

  free(a);
  return 0;
}

- - - - - -

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
 * In order to generate, say 3 letter combinations of string abcde,
 * pluck 'a' and then generate all 2 letter combinations of bcde,
 * discard 'a', then pluck 'b' and generate all 2 letter combinations of cde,
 * discard 'b', then pluck 'c' and generate all 2 letter combinations of de,
 * and so on.
 */

int gen_combs(char *prestr, char *str, int nc)
{
static int ncombs = 0;
int i, j, n, np;
char *newprestr;

n = strlen(str);
np = strlen(prestr);

if(nc==1) {
  for(i=0;i<n;i++) {
    printf(prestr);
    printf("%c\n",str[i]);
    ncombs++;
  }
  return ncombs;
}

newprestr = (char*)malloc((np+2)*sizeof(char));
strcpy(newprestr, prestr);

for(i=0;i<n;i++) {
  newprestr[np]=str[i];
  newprestr[np+1]='\0';

  gen_combs(newprestr, str+i+1, nc-1);
}
free(newprestr);

return ncombs;
}

void generate_combs(char *a, int nc)
{
int ncombs = gen_combs("", a, nc);
printf("\nTotal number of combinations: %d\n", ncombs);
}

int main(int argc, char *argv[])
{
int i,n,r;
char *a;

if(argc!=3) {
  printf("\nUsage: generate_combs <c> <r>\n");
  return 1;
}
sscanf(argv[1], "%d", &n);
sscanf(argv[2], "%d", &r);

if(n<0 || r<0 || n<r) {
  printf("\nInvalid input\n");
  return 1;
}

a = (char*)malloc((n+1)*sizeof(char));
for(i=0;i<n;i++)
  a[i]='a'+i;
a[n]='\0';

generate_combs(a, r);

free(a);
return 0;
}