//==============================================================
// BASED ON: F. Ruskey and A. Williams. An explicit universal cycle for the
// (n-1)-permutations of an n-set. ACM Transactions on Algorithms (TALG), 2010.

// Constructs/ranks/unranks the "direct" universal cycle for shorthand permutations
// PROGRAMMED BY: Colin Campbell -- 2025
//==============================================================

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

unsigned long long fact;

// ====================================================
// Helper functions 
// ====================================================

// Helper function to rotate a string of size n one position to the left
void rotate_n(int *p, int n){
    int first = p[0];
    for(int i = 0; i < n-1; i++) p[i] = p[i+1];
    p[n-1] = first;
}
  
// Helper function to rotate a string of size n one position  
// to the left while holding the last element constant
void rotate_n_minus_1(int *p, int n){
    int first = p[0];
    for (int i = 0; i < n-2; i++) p[i] = p[i+1];
    p[n-2] = first;
}

// ==================================================== //
// Construction function
// ==================================================== //
// Generate and output the shorthand universal cycle for pi (n),
// using the loopless sigma_n/sigma_(n-1) algorithm of Ruskey-Williams
void generateAndOutputUniversalCycle(int n){
    if (n < 2){
        printf("%d", n);
        return;
    }

    // Set up arrays for the bitstring generation algorithm
    int *a = calloc(n + 2, sizeof(int));
    int *d = malloc((n + 2) * sizeof(int));
    int *f = malloc((n + 1) * sizeof(int));

    // Check if memory allocation was successful
    if (!a || !d || !f){
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }

    // Initialize the starting permutation to n, n-1, ..., 1
    int *perm = malloc(n * sizeof(int));
    if (!perm) {
        free(a); free(d); free(f);
        return;
    }
    for(int i = 0; i < n; i++) perm[i] = n-i;

    int j;

    // Initially do d_n,...,d_1 <- 1...1
    // and f_n, f_(n-1),..., f_1 <- n + 1, n-1...1 
    for (int i = 1; i < n; i++){
        d[i] = 1;
        f[i] = i;
    }
    d[n] = 1;
    f[n] = n + 1;

    // This is a error in the original paper, d[n+1] is never defined
    // in the pseudocode however it is used by the algorithm. The max 
    // value of j is n+1 so we need to ensure that d[n+1] exists when 
    // the program attempts to access it. 
    d[n+1] = 1;

    do{
        // Output the current first element of the permutation
        if (perm[0] < 10) printf("%d", perm[0]);
        else printf("%c", perm[0]-10+'A');

        // Grab and then reset the first element of f
        j = f[1];
        f[1] = 1;

        // Now if j is even XOR (a[j] - d[j] <= 0 OR a[j] - d[j] >= n - j), then
        // the next bit is 0, otherwise it is 1
        int diff = a[j] - d[j];
        int flip = ((j % 2 == 0) ^ (diff <= 0 || diff >= (n - j)));
        char bit = flip ? '0' : '1';
        a[j] = a[j] + d[j];

        // Apply the rotation based on the bit
        if (bit == '0') rotate_n(perm, n);
        else rotate_n_minus_1(perm, n);

        // Check to see if we need to update d[j] and f[j]
        if (a[j] == 0 || a[j] == n - j){
            d[j] = -d[j];
            f[j] = f[j + 1];
            f[j + 1] = j + 1;
        }
    } while (j < n);

    // Clean up allocated memory
    free(a);
    free(d);
    free(f);
    free(perm);
}

// ==================================================== //
// Ranking function 
// ==================================================== //

// Recursive implementation of the Ruskey-Williams ranking algorithm.
// Given a permutation of [0..n] will return a rank [0..n!-1]
unsigned long long rankRuskeyWilliams(int *perm, int n){
    // This algorithm presumes that perm is a 
    // permutation of {1..n} and it will then split the perm
    // into (alpha)n(beta) where alpha and beta are permutations of {1..n-1}
    // and n is the largest element in the permutation.

    // Base case alpha = beta = epsilon 
    if (n <= 1) return 0;

    // Find the position of n in permutation
    int pos = 0;
    while (pos < n && perm[pos] != n) pos++;

    // If n is in position 0 then we have alpha = epsilon != beta
    if (pos == 0) return n * rankRuskeyWilliams(perm + 1, n - 1);
    
    // If the permutation is (alpha)n(beta)
    int m = n - 1;
    int lenBetta = m - pos;     
    int *newPerm = malloc(m * sizeof(int));
    if (!newPerm){
        printf("Memory allocation failed\n");
        return -1;
    }

    // Set the first part of the new permutation to be sigma(beta)
    // where sigma(beta) is beta rotated one position to the right
    newPerm[0] = perm[n-1];
    for (unsigned int i = 1; i < lenBetta; i++){
        newPerm[i] = perm[pos + i];    
    }

    // Now append alpha to the new permutation
    for (unsigned int i = lenBetta; i < m; i++){
        newPerm[i] = perm[i - lenBetta];
    }

    // Now we can find the rank(sigma(beta)alpha)
    int r = rankRuskeyWilliams(newPerm, m);
    free(newPerm);

    // And with that we can compute the rank of the original permutation
    return n - pos + n * r;
}

// ==================================================== //
// Unranking function 
// ==================================================== //
int* unrankRW(int n, unsigned long long r){
    // Base case
    if (n == 1){
        int *base = malloc(sizeof(int));
        if (!base){
            printf("Memory allocation failed\n");
            return NULL;
        }
        base[0] = n;
        return base;
    }

    // Find the quotient and remainder of r / n
    unsigned long long j = r / (unsigned long long) n;
    unsigned long long rem = r % (unsigned long long) n;

    // If the remainder is 0 then we know n will be in the 
    // first postion of the permutation therefore we can 
    // recurse to find the remaning part
    if (rem == 0){
        int *sub = unrankRW(n - 1, j);

        // Allocate space for the rest of the perm
        int *pi = malloc(sizeof(int) * n);
        if (!pi){
            printf("Memory allocation failed\n");
            return NULL;
        }

        // Set pi[0] = n as we knew this from r % n being 0 
        // then copy sub[0..n-2] -> pi[1..n-1]
        pi[0] = n;
        for (int i = 0; i < n - 1; i++) pi[i + 1] = sub[i];

        free(sub);
        return pi;
    }

    // If n is not in the first pos of the current perm
    else{
        // set k to be the 1-based position of n
        int k = n - rem + 1;  

        // Caculate the remainder of the perm
        int *sigma = unrankRW(n - 1, j);
        int *pi = malloc(n * sizeof(int));

        // Find the length of the beta segment 
        int L = n - k; 

        // Place n at position k-1 
        pi[k - 1] = n;

        // Handle the beta segment by rotating left by one
        if (L > 0){
            int first = sigma[0];  
            for (int i = 0; i < L - 1; i++) pi[k + i] = sigma[i + 1];        
            pi[k + L - 1] = first;
        }

        // Place the alpha segment
        for (int i = 0; i < k - 1; i++){
            pi[i] = sigma[L + i];
        }

        free(sigma);
        return pi;
    }
}

// ==================================================== //
int main(int argc, char **argv){
    
    int type = 0,n;
   
    printf("What would you like to do to the direct UC for shorthand permutations?\n");
    printf("\t1. Generate it\n");
    printf("\t2. Rank a shorthand permutation\n");
    printf("\t3. Unrank a shorthand permutation\n");
    printf("Enter the number corresponding to the option you want: ");
    scanf("%d", &type);
    
    if (type < 1 || type > 3) { printf("Invalid selection\n"); return 0; }
  
    printf("Enter the order n between 2 and 15: ");
    scanf("%d", &n);
    
    if (n < 2 || n > 15) { printf("Invalid order n\n"); return 0; }
    
    fact = 1;
    for (unsigned int i = 2; i <= n; i++) fact *= i;

    if(type == 1){
        // OUTPUT THE UC directly without storing in memory
        printf("\n");
        generateAndOutputUniversalCycle(n);
        printf("\n\n");
    }
    else if (type == 2) {
        int perm[n], sum = 0;
        for(int i = 0; i < n-1; i++){
            printf("Enter the value (between 1 and %d) in position %d: ", n,i+1);
            scanf("%d",&perm[i]);
            sum +=perm[i];
        }
        
        // Validate perm
        for (int i=0; i<n-1; i++) {
            if (perm[i] < 1 || perm [i] > n) { printf("Invalid shorthand perm\n"); return 0; }
            for (int j=i+1; j<n-1; j++) if (perm[i] == perm[j]) { printf("Invalid shorthand perm\n"); return 0; }
        }
        
        // Find the missing symbol
        int missing = (n * (n + 1) / 2) - sum;
        perm[n-1] = missing;

        // Rank relative to 0, so increment by 1 
        unsigned long long rank = 1+ rankRuskeyWilliams(perm, n);

        printf("\nThe rank of ");
        for(unsigned long long j=0; j < n-1; j++) {
            if (perm[j] < 10) printf("%d", perm[j]);
            else printf("%c",perm[j]-10+'A');
        }
        
        printf(" is %lld\n\n",rank);
    }
    else {
        unsigned long long r;
        printf("Enter rank between 1 and %lld: ", fact);
        scanf("%lld", &r);
        
        // Validate rank
        if (r <= 0 || r > fact) { printf("Invalid rank\n"); return 0; }
        
        // Subtract 1 from r since the algorithm is 0 relative
        int *perm = unrankRW(n, r-1);
        
        printf("\nThe shorthand permutation at rank %lld is ",r);
        for(unsigned long long j=0; j < n-1; j++) {
            if (perm[j] < 10) printf("%d", perm[j]);
            else printf("%c",perm[j]-10+'A');
        }
        printf("\n\n");

        free(perm);
    }
    
    return 0;
}