/****************************************
* Section : 10
* Roll No. : 20CS10000 / 20CS30000
* Name : Aritra Hazra
* Assignment No : 5B
* Description : Derangement Statistics
* Date : 01-Jun-2021
****************************************/

#include <stdio.h>

#define MAX 1024 // 1024 ought to be big enough for anybody

typedef unsigned long long LONG;

// counting and showing all derangements
LONG derangements(int depth, int length, int d[], int show)
{
  int i, tmp;
  LONG distance = 0;
  LONG count = 0;
 
  if (depth == length) { // base condition
    if (show) { // showing derangements
      for (i = 0; i < length; i++) {
        printf(" %d", d[i]+1); // printing derangement sequence
        
        // computing distance measure of the derangement
        if(d[i] > i) {
          distance += (d[i] - i);
        }
        else{
          distance += (i - d[i]);
        }
      }
      // printing the distance of each derangement obtained
      printf("\t[Distance = %llu]\n", distance);
    }
    return 1;
  }
  for (i = length - 1; i >= depth; i--) { // recursive formulation
    if (i == d[depth])
      continue;
    
    // swap the positions of depth and current value
    tmp = d[i]; d[i] = d[depth]; d[depth] = tmp;
    //recursive call to the rest part of sequence
    count += derangements(depth + 1, length, d, show);
    // swap back the positions
    tmp = d[i]; d[i] = d[depth]; d[depth] = tmp;
  }
  return count;
}

// counting number of derangement directly from recurrence formula
LONG countDerangementsRec(int n)
{
  if (n < 2){
    return (1-n);
  }
  else {
    return (countDerangementsRec(n-1) + countDerangementsRec(n-2)) * (n-1);
  }
}

// recursive computation of factorial
LONG factorial(int n) {
  if(n == 0) {
    return 1;
  }
  else {
    return n * factorial(n-1);
  }
}

// total count of derangement using iterative formula expanded from left-to-right 
LONG countDerangementsItrLR(int n)
{
  int i, sign;
  LONG term = factorial(n); // leftmost term
  LONG count = term;
  for(i = 1; i <= n; i++) {
    term /= i; // producing the term immediately after
    sign = (i%2)? -1 : +1; // generating the sign
    count += sign*term; // partial count upto produced terms
  }
  
  return count;
}

// total count of derangement using iterative formula expanded from right-to-left
LONG countDerangementsItrRL(int n)
{
  int i, sign;
  LONG term = 1; // rightmost term
  LONG count = term;
  for(i = n; i >= 1; i--) {
    term *=i; // producing the term immediately before
    count = term - count; // partial count upto produced terms
  }
  
  return count;
}
 
int main()
{
  int n, i;
  int arr[MAX];
  
  // user entry of number of positions
  printf("++ Enter n [1-1024]: ");
  scanf("%d", &n);
  
  // proper positional sequence
  printf("\n** The Proper Sequence:");
  for (i = 0; i < n; i++){
    arr[i] = i;
    printf(" %d", arr[i]+1);
  }
  
  // printing total number of derangements using recursive formula
  printf("\n** Recursive Count of Derangements: %llu", countDerangementsRec(n));
  
  // printing total number of derangements using iterative formula (left-to-right)
  printf("\n** Iterative Count of Derangements: %llu [Left-to-Right]", countDerangementsItrLR(n));
  
  // printing total number of derangements using iterative formula (right-to-left)
  printf("\n** Iterative Count of Derangements: %llu [Right-to-Left]", countDerangementsItrRL(n));
  
  // printing total number of derangements while producing these recursively
  printf("\n** The # %llu # Derangements are: \n", derangements(0,n,arr,0));
  // printing all possible derangements while producing these recursively
  derangements(0,n,arr,1);
  
  return 0;
}