Permutations: C code

Permutation processing is both interesting and important.

This page looks at some aspects of permutation processing. Note: This is a more advanced program that will be presented. The final program is something that could be used in an introductory programming course but is not something that could be developed from scratch by students in an introductory programming course. The module developed will not use any global variables.

This makes it a little less machine efficient, but is satisfactory for the present purposes since it provides a cleaner design for understanding purposes.

Permutations are used in many applications.

Secret codes and security
Solving certain types of constraint problems
Games, puzzles, etc.

A mathematical and recursive definition of a permutation of n objects is as follows.

The permutation of 1 object is the object itself.
The permutation of n objects (n > 1) is obtained by taking each object of the n objects and permuting it with every permutation of the remaining n-1 objects.

We will use a swap procedure defined as follows. For more information, see Procedure to swap values .

void swap(int *a1, int *b1) {
	int c1;
	c1 = *a1;
	*a1 = *b1;
	*b1 = c1;
	}

A data list contains the data to be processed, as in the following.

char data1[4][256];
scanf("%s",data1[1]);
scanf("%s",data1[2]);
scanf("%s",data1[3]);
printf("Direct access:\n");
printf("\t%s\n",data1[1]);
printf("\t%s\n",data1[2]);
printf("\t%s\n",data1[3]);

It is often easier and better to work with pointers to array elements rather than the array elements themselves. An array of integer elements can be used such that each integer element is and index to another array.

Here is an example of indirect access (via array pointers).

int data0[4];
data0[1] = 1;
data0[2] = 2;
data0[3] = 3;
printf("Indirect access:\n");
printf("\t%s\n",data1[data0[1]]);
printf("\t%s\n",data1[data0[2]]);
printf("\t%s\n",data1[data0[3]]);

Since the data is accessed indirectly (via the array pointer) this process is called indirection. Here is the C code.

#include <stdio.h>

int main() {
	// direct data access
	char data1[4][256];
	scanf("%s",data1[1]);
	scanf("%s",data1[2]);
	scanf("%s",data1[3]);
	printf("Direct access:\n");
	printf("\t%s\n",data1[1]);
	printf("\t%s\n",data1[2]);
	printf("\t%s\n",data1[3]);

	// indirect data access
	int data0[4];
	data0[1] = 1;
	data0[2] = 2;
	data0[3] = 3;
	printf("Indirect access:\n");
	printf("\t%s\n",data1[data0[1]]);
	printf("\t%s\n",data1[data0[2]]);
	printf("\t%s\n",data1[data0[3]]);
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

one
two
three

For the above example input, here is the expected output.

Direct access:
	one
	two
	three
Indirect access:
	one
	two
	three

To do this, start with the following data structures.

#define DATAMAX 16

// global variables
char dataList1[DATAMAX+2][256];
int dataLen1;
int permuteList1[DATAMAX+1];
int permuteCount1;

DATAMAX is the maximum number of elements to permute.
dataList1 is the list of array elements to be permuted.
dataLen1 is the number of elements in the list, starting at 1.
permuteList1 is the list of array element pointers to the array containing the values.
permuteCount1 is the count of the current permutation

Arrays dataList1 and permuteList1 are parallel arrays.

The input is read, line by line, using gets until the end of file is reached.

printf("Input:\n");
printf("\n");
dataLen1 = 0;
while (gets(dataList1[dataLen1+1])) {
	dataLen1++;
	printf("\t%d. \"%s\"\n",dataLen1,dataList1[dataLen1]);
	}

The following procedure showDo1 is used to show the permutation found.

void showDo1() {
	permuteCount1++;
	printf("\t%d.",permuteCount1);
	for (int dataPos1=1; dataPos1 <= dataLen1; dataPos1++) {
		printf(" ");
		printf("%s",dataList1[permuteList1[dataPos1]]);
		}
	printf("\n");
	}

The global value permuteCount1 is used to keep track of the number of permutations found/processed.

The procedure actionDo1 is the procedure called for each new permutation. Any selection or criteria used in constraint programming can be placed here (in the brute force approach).

void actionDo1() {
	// selection criteria goes here
	showDo1();
	}

For this example, there is no selection criteria and every permutation is displayed using show1.

Here is the recursive permute procedure permute1.

// step case - finish out the permutations

void permute1(int start1, int stop1, int *list1, void (*action1)()) {
	if (start1 == stop1) {
		action1();
		}
	else {
		for (int pos1=start1; pos1 <= stop1; pos1++) {
			swap(&list1[start1],&list1[pos1]);
			permute1(start1+1,stop1,list1,action1);
			swap(&list1[start1],&list1[pos1]);
			}
		}
	}

Note the passing of a function (pointer) to permute1. To perform permutations, one calls procedure permute0 defined as follows.

// base case - get the permutations started

void permute0(int *list1, int len1, void (*action1)()) {
	for (int pos1=1; pos1 <= len1; pos1++) {
		list1[pos1] = pos1;
		}
	permute1(1,len1,list1,action1);
	}

Note the passing of a function (pointer) to permute0. That action passed as a function will be the "callback" action.

The interface is abstracted as follows.

void permute0(int *list1, int len1, void (*action1)());

Here is the C code.

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

// begin rsPermute interface

void permute0(int *list1, int len1, void (*action1)());

// end rsPermute interface

#define DATAMAX 16
// global variables
char dataList1[DATAMAX+2][256];
int dataLen1;
int permuteList1[DATAMAX+1];
int permuteCount1;

void showDo1() {
	permuteCount1++;
	printf("\t%d.",permuteCount1);
	for (int dataPos1=1; dataPos1 <= dataLen1; dataPos1++) {
		printf(" ");
		printf("%s",dataList1[permuteList1[dataPos1]]);
		}
	printf("\n");
	}

void actionDo1() {
	// selection criteria goes here
	showDo1();
	}

int main() {
	printf("Input:\n");
	printf("\n");
	dataLen1 = 0;
	while (gets(dataList1[dataLen1+1])) {
		dataLen1++;
		printf("\t%d. \"%s\"\n",dataLen1,dataList1[dataLen1]);
		}
	printf("\n");
	printf("Permutations:\n");
	printf("\n");
	permuteCount1 = 0;
	permute0(permuteList1,dataLen1,actionDo1);
	return 0;
	}

// begin rsPermute implementation

void swap(int *a1, int *b1) {
	int c1;
	c1 = *a1;
	*a1 = *b1;
	*b1 = c1;
	}

// step case - finish out the permutations

void permute1(int start1, int stop1, int *list1, void (*action1)()) {
	if (start1 == stop1) {
		action1();
		}
	else {
		for (int pos1=start1; pos1 <= stop1; pos1++) {
			swap(&list1[start1],&list1[pos1]);
			permute1(start1+1,stop1,list1,action1);
			swap(&list1[start1],&list1[pos1]);
			}
		}
	}

// base case - get the permutations started

void permute0(int *list1, int len1, void (*action1)()) {
	for (int pos1=1; pos1 <= len1; pos1++) {
		list1[pos1] = pos1;
		}
	permute1(1,len1,list1,action1);
	}

// end rsPermute implementation

Here are some examples of input and output for the above program code.

Here is an example input.

a
b
c

For the above example input, here is the expected output.

Input:

	1. "a"
	2. "b"
	3. "c"

Permutations:

	1. a b c
	2. a c b
	3. b a c
	4. b c a
	5. c b a
	6. c a b

Programming languages have various ways of abstracting and encapsulating code to be used between different programs. Some terms for these are the following - which are not all the same but have the same very general meaning.

library
module
package (e.g., Python)
namespace (e.g., C# and .NET languages)
unit (e.g., Delphi)
class (e.g., Java)

In C, the interface becomes a .h file while the implementation becomes a .c file.

For the abstraction of the permutation code, the name used will be rsPermute. Here is a code module in C [module rsPermute in rsPermute.c].

// begin rsPermute implementation

void swap(int *a1, int *b1) {
	int c1;
	c1 = *a1;
	*a1 = *b1;
	*b1 = c1;
	}

// step case - finish out the permutations

void permute1(int start1, int stop1, int *list1, void (*action1)()) {
	if (start1 == stop1) {
		action1();
		}
	else {
		for (int pos1=start1; pos1 <= stop1; pos1++) {
			swap(&list1[start1],&list1[pos1]);
			permute1(start1+1,stop1,list1,action1);
			swap(&list1[start1],&list1[pos1]);
			}
		}
	}

// base case - get the permutations started

void permute0(int *list1, int len1, void (*action1)()) {
	for (int pos1=1; pos1 <= len1; pos1++) {
		list1[pos1] = pos1;
		}
	permute1(1,len1,list1,action1);
	}

// end rsPermute implementation

Here is a code interface in C [header rsPermute in rsPermute.h].

#ifndef RSPERMUTE_H
#define RSPERMUTE_H

// begin rsPermute interface

void permute0(int *list1, int len1, void (*action1)());

// end rsPermute interface

#endif

In C (and other code) that use include, a common way to avoid including a header file more than once is the following.

Including a header file more than once can cause errors. 1. Define a symbol for the module, such as RSPERMUTE_H (for header file rsPermute.h)

2. Put the following at the start of the header (interface) file.

#ifndef RSPERMUTE_H #define RSPERMUTE_H

3. Put the following at the end of the header (interface) file.

#endif

The first time the header file is included, symbol RSPERMUTE_H is not defined. So the preprocessor defines that symbol and then includes the header body.

If the header file is included again (nested includes), then the symbol RSPERMUTE_H is already defined so that header would not be included again.

Here then is the above program using rsPermute.

Here is the C code.

#include <stdio.h>
#include <string.h>
#include "rsPermute.h"

#define DATAMAX 16
// global variables
char dataList1[DATAMAX+2][256];
int dataLen1;
int permuteList1[DATAMAX+1];
int permuteCount1;

void showDo1() {
	permuteCount1++;
	printf("\t%d.",permuteCount1);
	for (int dataPos1=1; dataPos1 <= dataLen1; dataPos1++) {
		printf(" ");
		printf("%s",dataList1[permuteList1[dataPos1]]);
		}
	printf("\n");
	}

void actionDo1() {
	// selection criteria goes here
	showDo1();
	}

int main() {
	printf("Input:\n");
	printf("\n");
	dataLen1 = 0;
	while (gets(dataList1[dataLen1+1])) {
		dataLen1++;
		printf("\t%d. \"%s\"\n",dataLen1,dataList1[dataLen1]);
		}
	printf("\n");
	printf("Permutations:\n");
	printf("\n");
	permuteCount1 = 0;
	permute0(permuteList1,dataLen1,actionDo1);
	return 0;
	}

Here are some examples of input and output for the above program code.

Here is an example input.

a
b
c

For the above example input, here is the expected output.

Input:

	1. "a"
	2. "b"
	3. "c"

Permutations:

	1. a b c
	2. a c b
	3. b a c
	4. b c a
	5. c b a
	6. c a b

Note that when using modules, the gcc command to compile the program needs to include any used modules. Here is an example.

gcc myprog1.c rsPermute.c -o myprog1.exe

When a program needs a lot of modules, and those modules need other modules, etc., this process can get very complex.

Much of this complexity can be hidden in a make command.