Printing all permutations of a string

You can use the following C code to print all two character permutations (with repetition allowed) of a string:

	#include <stdio.h>
	#include <string.h>
	int main() {
	char* s = "abc"; //set of possible characters
	const int r = 2; //nb of characters in permutations
	const int n = strlen(s);
	char p[r+1]; //+1 is for end of line character
	p[r] = 0; //end of line character
	int c = 0;
	for(int i=0; i < n; i++) {
	p[0] = s[i]; //first character in permutation
	for(int j=0; j < n; j++) {
	p[1] = s[j]; //second character in permutation
	printf("%d. %s\n", ++c, p);
	}
	}
	}

view raw perm1.c hosted with ❤ by GitHub

If you would like to print three character permutations, you have to add another for loop:

	#include <stdio.h>
	#include <string.h>
	int main() {
	char* s = "abc";
	const int r = 3;
	const int n = strlen(s);
	char p[r+1];
	p[r] = 0;
	int c = 0;
	for(int i=0; i < n; i++) {
	p[0] = s[i];
	for(int j=0; j < n; j++) {
	p[1] = s[j];
	for(int k=0; k < n; k++) {
	p[2] = s[k];
	printf("%d. %s\n", ++c, p);
	}
	}
	}
	}

view raw perm2.c hosted with ❤ by GitHub

As you can see, this is not generalizable because you have to keep adding or deleting for loops manually. Also notice that with each loop, the p[] index is increased by one. We could use this fact to write a recursive function that could handle all character permutations:

	#include <stdio.h>
	#include <string.h>
	static int c = 0;
	void printPermutations(char* p, const char* s, int pos, const int n, const int r) {
	if(pos == r) printf("%d. %s\n",++c, p); //reached last character, print current permutation
	else {
	for(int i=0; i < n; i++) {
	p[pos] = s[i];
	printPermutations(p, s, pos+1, n, r); //note that pos in incremented by one
	}
	}
	}
	int main() {
	char* s = "abc";
	const int r = 2;
	const int n = strlen(s);
	char p[r+1];
	p[r] = 0;
	printPermutations(p, s, 0, n, r);
	}

view raw perm3.c hosted with ❤ by GitHub

This is a nice example of first writing the simple cases, seeing a pattern and reaching the general case, i.e. inductive reasoning.