/* 
* Code example for CP264 Data Structures II
* Permutation
* HBF 
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int count=0;
int numberperline = 10;

void allstr_recursion(char *symbols, char *prefix, int symbolcount, int len, int n); 
void allstr_iteration(char symbols[], int symbolcount, int len); 
void swap(char *x, char *y);
void permutation_recursion(char *a, int l, int r);
void permutation_iteration(char s[], int n);
void permutation_iteration1(char* input, int n);

void main(int argc, char *args[]) {

  int len = 2;
  if (argc >= 2) len = atoi(args[1]); 

  char symbols[] = "ABC";
  //char symbols[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
   
  int symbolcount = sizeof(symbols)-1;

  char prefix[len];
  printf("====fixed length string enumeration by recursion====\n");
  count = 0;
  allstr_recursion(symbols, prefix, symbolcount, len, len);
  printf("\ncounter==%d\n", count);
 
  printf("\n====fixed length string enumeration by iteration====\n");
  allstr_iteration(symbols, symbolcount, len);
  
  printf("\n====permutation by recursion====\n");
  char str[] = "ABCD";
  int n = strlen(str);
  count = 0;
  permutation_recursion(str, 0, n-1);
  printf("\ncounter==%d\n", count);
  
  printf("\n====permutation by iteration====\n");
  permutation_iteration(str, n);
  
  printf("\n====permutation by iteration 2====\n");
  permutation_iteration1(str, n);
}

void allstr_recursion(char *symbols, char *prefix, int symbolcount, int len, int n) {
  int i;
  if (n == 0) {
    count++;
    for (i=0;i<len;i++) 
      printf("%c", prefix[i]);
    
	if (count % numberperline == 0) printf("\n");
	else 
		printf(" ");
	
  }
  else {
    for (i=0;i<symbolcount;i++) {
      prefix[len-n] = symbols[i];
      allstr_recursion(symbols, prefix, symbolcount, len, n-1);
    }
  }
}

void allstr_iteration(char symbols[], int symbolcount, int len) {
  int s[len], i, j, counter=0;
  for (i=0; i<len; i++) s[i] = 0;
  
  do {
     counter++;
     for (i=0; i<len; i++) {
		printf("%c", symbols[s[i]]);
	 }
	 if (counter % numberperline == 0) printf("\n");
	 else printf(" ");
     
	 for (i=len-1; i>=0; i--) {
	    if (s[i]<symbolcount-1) break; //find the first the increase postion from right
	 }
	 if (i == -1) break; // if no increase position is found, done
	 
	 s[i] = s[i] + 1; // increase by one at the increase position,
	 for (j=i+1;j<len;j++) s[j] = 0;  // change to 0 after the increasing position
	 
  } while (1);
  
  printf("\ncounter==%d\n", counter);
}

//increasing order algorithm
void permutation_iteration(char symbols[], int n) {
  int p[n], i, j, k, counter=0, temp;
 
  for (i=0; i<n; i++) p[i] = i;
  do {
     counter++;	  
     for (k=0; k<n; k++) {
		printf("%c", symbols[p[k]]);
	 }
	 
	 if (counter % numberperline == 0) printf("\n");
	 else printf(" ");
     
	 //find the first position from right
	 for (i=n-2; i>=0; i--) {
	    if (p[i]<p[i+1]) break; //find the first 
	 }
	 
	 if (i == -1 ) break;  // if first position is not found, done
	 	 
	 //i is the first position
	 for (j=i+1; j<n; j++) {
		 if ( p[j] < p[i] ) break; 
	 }
	 j--;  
	 //j is the second position, swap with the first position	 
	 temp = p[i]; 
	 p[i] = p[j];
	 p[j] = temp;
	 	 
	 // reverse from position i+1 to end;
	 for (j=i+1, k=n-1; j<k; j++, k--) {
		temp = p[j]; 
		p[j] = p[k];
	    p[k] = temp;; 
	 }
	 
  } while (1);

  printf("\ncounter==%d\n", counter);  
  
}

void permutation_iteration1(char* input, int n) {
	int counter = 0;
	if (n == 0) return ;

	int i, j;
	int p[n];
    for( j = 0; j < n; ++j )  p[j] = j ;
   
	char s[n+1]; 
	strcpy(s, input);
		
    // core algorithm begins
	i = 0; 
	j = 0;
	while(i<n) {
		p[i]--;
	    j = i % 2 * p[i];
		swap(&s[i], &s[j]) ;
		counter++ ;
		printf("%s ", s);
		if (counter % numberperline == 0) printf("\n");
		i = 1;
	    while (!p[i]) {
	        p[i] = i;
	        i++;
        }	
   }
   printf("\ncounter==%d\n", counter);  
}


//https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permutation_recursion(char *a, int l, int r)
{
   int i;
   if (l == r) {
     count++;
	 printf("%s ", a);
	 if (count % numberperline == 0) printf("\n");
   }
   else
   {
       for (i = l; i <= r; i++)
       {
		  swap((a+l), (a+i));
          permutation_recursion(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}


/*
====fixed length string enumeration by recursion====
AA AB AC BA BB BC CA CB CC
counter==9

====fixed length string enumeration by iteration====
AA AB AC BA BB BC CA CB CC
counter==9

====permutation by recursion====
ABCD ABDC ACBD ACDB ADCB ADBC BACD BADC BCAD BCDA
BDCA BDAC CBAD CBDA CABD CADB CDAB CDBA DBCA DBAC
DCBA DCAB DACB DABC
counter==24

====permutation by iteration====
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA
BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB
DBAC DBCA DCAB DCBA
counter==24

====permutation by iteration 2====
ABCD BACD CABD ACBD BCAD CBAD CBDA BCDA DCBA CDBA
BDCA DBCA DACB ADCB CDAB DCAB ACDB CADB BADC ABDC
DBAC BDAC ADBC DABC
counter==24
*/