CtoHTML Output

perm.c

/*
  PERM.C
  ======
  (c) Copyright Paul Griffiths 2000
  Email: mail@paulgriffiths.net

  Prints all the possible permutations of 'n' items.
  'n' must be supplied as the sole command line argument.
*/


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

#include "data.h"
#include "stack.h"
#include "cmdline.h"


static void Perm(unsigned n);

static int count = 0;


int main(int argc, char *argv[]) {
    unsigned n = ParseCmdLine(argc, argv);

    InitializeData(n);

    printf("Permutations of %u items:\n\n", n);
    Perm(n);
    printf("\n%d permutations in all.\n", count);

    FreeData();

    return EXIT_SUCCESS;
}

void Perm(unsigned n) {
    unsigned item;

    if ( n == 0 ) {
        PrintStack();
        ++count;
        return;
    }

    for ( item = 0; item < n; ++item ) {
        Push(RemoveItem(item));
        Perm(n-1);
        InsertItem(Pop(), item);
    }
}

data.h

/*
  DATA.H
  ======
  (c) Copyright Paul Griffiths 2000
  Email: mail@paulgriffiths.net

  Interface to functions for dealing with data
*/


#ifndef PG_DATA_H
#define PG_DATA_H

void InitializeData(unsigned n);
void FreeData(void);
char RemoveItem(unsigned pos);
void InsertItem(char n, unsigned pos);

#endif  /* PG_DATA_H */

data_list.c

/*
  DATA_LIST.C
  ===========
  (c) Copright Paul Griffiths 2000
  Email: mail@paulgriffiths.net

  Functions for manipulating the data using linked lists
*/


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

#include "data.h"


struct node {
    char n;
    struct node * next;
};

static struct node * data;


/*  Initialize memory for data  */

void InitializeData(unsigned n) {
    struct node * temp = NULL;
    char set[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    unsigned i = 0;

    while ( i < n ) {
        if ( data == NULL ) {
            data = malloc(sizeof *data);
            temp = data;
        }
        else {
            temp->next = malloc(sizeof *(temp->next));
            temp = temp->next;
        }

        if ( temp == NULL ) {
            fprintf(stderr, "Memory allocation failure\n");
            exit(EXIT_FAILURE);
        }
        
        temp->n = set[i++];
        temp->next = NULL;
    }
}


/*  Free memory used for data  */

void FreeData(void) {
    struct node * temp = data;

    while ( data ) {
        temp = data->next;
        free(data);
        data = temp;
    }
}


/*  Remove data item at position 'pos'  */

char RemoveItem(unsigned pos) {
    struct node * temp = data;
    struct node * last = NULL;
    char d;

    while ( temp ) {
        if ( 0 == pos-- ) {
            if ( last )
                last->next = temp->next;
            else
                data = temp->next;

            d = temp->n;

            free(temp);
            return d;
        }
        last = temp;
        temp = temp->next;
    }

    fprintf(stderr, "Position specifed out of bounds.\n");
    exit(EXIT_FAILURE);
}


/*  Insert data item 'n' at position 'pos'  */

void InsertItem(char n, unsigned pos) {
    struct node * temp = data;
    struct node * last = NULL;

    while ( temp && pos-- ) {
        last = temp;
        temp = temp->next;
    }

    if ( temp == NULL && pos ) {
        fprintf(stderr, "Position out of bounds\n");
        exit(EXIT_FAILURE);
    }

    if ( last ) {
        last->next = malloc(sizeof *(last->next));
        last = last->next;
    }
    else {
        data = malloc(sizeof *data);
        last = data;
    }

    if ( last == NULL ) {
        fprintf(stderr, "Memory allocation failure\n");
        exit(EXIT_FAILURE);
    }

    last->next = temp;
    last->n = n;
}

stack_list.c

/*
  STACK_LIST.C
  ============
  (c) Copyright Paul Griffiths 2000
  Email: mail@paulgriffiths.net

  Stack operations using linked lists
*/


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

#include "stack.h"


struct node {
    char n;
    struct node * next;
};

static struct node * stack;


/*  Push item 'n' onto the stack  */

void Push(char n) {
    struct node * temp = stack;

    if ( stack == NULL ) {
        stack = malloc(sizeof(struct node));
        temp = stack;
    }
    else {
        while ( temp->next )
            temp = temp->next;
        temp->next = malloc(sizeof(struct node));
        temp = temp->next;
    }

    if ( temp == NULL ) {
        fprintf(stderr, "Memory allocation failure\n");
        exit(EXIT_FAILURE);
    }

    temp->n = n;
    temp->next = NULL;
}


/*  Pop top item from the stack  */

char Pop(void) {
    struct node * temp = stack;
    struct node * last = NULL;
    char n;

    if ( stack == NULL ) {
        fprintf(stderr, "Stack empty!\n");
        exit(EXIT_FAILURE);
    }

    while ( temp->next ) {
        last = temp;
        temp = temp->next;
    }

    n = temp->n;
    free(temp);
    if ( last )
        last->next = NULL;
    else
        stack = NULL;
    
    return n;
}


/*  Output contents of stack  */

void PrintStack(void) {
    struct node * temp = stack;

    while ( temp ) {
        putchar(temp->n);
        temp = temp->next;
    }

    putchar('\n');
}

cmdline.c

/*
  CMDLINE.C
  =========
  (c) Copyright Paul Griffiths 2000
  Email: mail@paulgriffiths.net

  Function to parse command line and return integral argument
*/


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

#include "cmdline.h"


unsigned ParseCmdLine(int argc, char *argv[]) {
    unsigned n;
    char * endptr;

    if ( argc < 2 ) {
        fprintf(stderr, "You must supply an argument\n");
        exit(EXIT_FAILURE);
    }
    else if ( argc > 2 ) {
        fprintf(stderr, "You must only supply one argument\n");
        exit(EXIT_FAILURE);
    }

    n = (unsigned) strtoul(argv[1], &endptr, 0);

    if ( *endptr ) {
        fprintf(stderr, "You must supply a whole number as an argument\n");
        exit(EXIT_FAILURE);
    }
    else if ( n > 26 ) {
        fprintf(stderr, "You must specify a number less than 27\n");
        exit(EXIT_FAILURE);
    }
    else if ( n < 1 ) {
        fprintf(stderr, "You must specify a number greater than 0\n");
        exit(EXIT_FAILURE);
    }

    return n;
}