#include <stdio.h>
 
// To enable debug messages uncomment #define
#define TEST 1
//#define DEBUG 1
 
#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif
 
void permute(char *s, int start, int end);
void swap(char *s, int start, int end);
void startTesting();
 
int main(void) {
#ifdef TEST
    startTesting();
#endif
 
	return 0;
}
 
void swap(char *s, int start, int end) {
    char temp = s[start];
    s[start] = s[end];
    s[end] = temp;
}  
 
void permute(char *s, int start, int end) {
	int i = 0;
 
    if (start == end) {
    	printf("%s\n", s);
    	D(printf("\n############\n"));
    } else {
        for (i = start; i <= end; i++) {
 
            D(printf("Fix '%c' instead of '%c'\n", s[j], s[start]));            
            swap(s, start, i);
 
            D(printf("Call Permute on string %s from  '%c' to '%c'\n", s, s[start + 1], s[end]));
 
            permute(s, start + 1, end);
 
            D(printf("Backtrack swap '%c' & '%c'\n", s[start], s[j]));
            swap(s, start, i);
            D(printf("After Backtrack string %s\n", s));
        }    
    }         
}
 
void test1()
{
    char s[] = "ABCD";
    printf("permute(\"%s\", 0, 3)\n", s);
    permute(s, 0, 3);
    printf("\n");
}
 
void startTesting()
{
    test1();
}