//==========================================================================================
// BASED ON: Holroyd, Ruskey and Williams. Shorthand Universal Cycles for Permutations, 2012

// Constructs/ranks/unranks the "Bell-ringer" universal cycle for shorthand permutations
// PROGRAMMED BY: Colin Campbell -- Aug,2025
//==========================================================================================

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

int  n;            
unsigned long long fact;  
unsigned long long blocksTotal; // (n-1)!
unsigned long long blocksCount = 0;
int *blocks; // store (n-1)! blocks, flattened
long writePos = 0;
int  a[15];     
int *U;            

int* unrank7Order(int n, unsigned long long r);

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

// Helper function to shift a[i..j] left by one (move a[i] to a[j])
void shift(int i, int j){
    int tmp = a[i];
    for (int k = i; k < j; k++) a[k] = a[k+1];
    a[j] = tmp;
}

// Store the sub-permutation a[1..n-1] into blocks
void visit(){
  if (blocksCount < blocksTotal) {
    int base = (int) blocksCount * (n - 1);
    for (int i = 0; i < n - 1; i++) blocks[base + i] = a[i + 1]; // a[1..n-1]
    blocksCount++;
  }
}

// Build the candidate shorthand s from a (size n-1), b (size n-1) and j (1..n-1).
// Pattern from paper: s = a_{j+1} ... a_{n-1}  n  b1 ... b_{j-1}
static void buildcandidate(int *scand, int *a, int *b, int n, int j){
    // j in 1..n-1; a, b are length n-1
    int idx = 0;
    // a_{j+1} .. a_{n-1}  => a[j .. n-2] (0-based)
    for (int k = j; k <= n-2; ++k) scand[idx++] = a[k];
    // then n
    scand[idx++] = n;
    // then b1 .. b_{j-1} => b[0 .. j-2] if j>=2
    for (int k = 0; k <= j-2; ++k) scand[idx++] = b[k];
    // idx should be n-1
}

// ==================================================== //
// Construction function
// ==================================================== //
// Recursive implementation of the bell7 algorithm
// as presented in the Holroyd-Ruskey-Williams paper
void Bell7(int m){
    if (m == n){
        visit();
    }else{
        Bell7(m+1);
        shift(n - m, n - 1);

        for (int i = n - 2; i >= n - m; i--) {
            Bell7(m + 1);
            int tmp = a[i];
            a[i] = a[i + 1];
            a[i + 1] = tmp;
        }

    }
}

// ==================================================== //
// Ranking functions
// ==================================================== //
// Recursive implementation of the Holroyd-Ruskey–Williams 7 order ranking
// algorithm. Given a permutation of [0..n] will return a rank [0..n!-1]
unsigned long long rank7Order(int *perm, int n){

    // Base case if the perm is only one element 
    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 
    if (pos == 0) return n * rank7Order(perm + 1, n - 1);
    
    // If the permutation has n somewhere other than the first position
    int m = n - 1;
    int *newPerm = malloc(m * sizeof(int));
    if (!newPerm){
        printf("Memory allocation failed\n");
        return -1;
    }

    // Set the first part of the new permutation up to n to be the same as the original 
    for (unsigned int i = 0; i < pos; i++) newPerm[i] = perm[i];

    // Skip over n and then copy over the rest of the original 
    for (unsigned int i = pos; i < m; i++) newPerm[i] = perm[i + 1];     

    // Now we can find the rank of the new permutation
    // which is the original permutation with n removed
    unsigned long long r = rank7Order(newPerm, m);
    free(newPerm);

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

// Ranking function given by the procedure mentioned in Section 7.2 
// of the paper to efficiently rank the bell-ringer SP-cycle
unsigned long long rankBOrder(int *perm, int n){ 
    if (n <= 1) return 0ULL;
    if (n == 2){
        if (perm[0] == 2 && perm[1] == 1) return 0ULL; // descending -> 0
        return 1ULL;
    }

    // Special-case: descending permutation n, n-1, ..., 1 maps to r == 0
    int isDesc = 1;
    for (int i = 0; i < n; ++i){
        if (perm[i] != (n - i)){ isDesc = 0; break; }
    }
    if (isDesc) return 0ULL;

    // Build shorthand substring s (length n-1)
    int *s = malloc((n-1) * sizeof(int));
    if (!s) { fprintf(stderr, "malloc failed\n"); return (unsigned long long)-1; }
    for (int i = 0; i < n-1; ++i) s[i] = perm[i];

    // If n not present in s
    int foundN = 0;
    for (int i = 0; i < n-1; ++i) if (s[i] == n) { foundN = 1; break; }
    if (!foundN){
        unsigned long long r7 = (unsigned long long) rank7Order(s, n-1);
        free(s);
        return 1ULL + (unsigned long long)n * r7;
    }

    // if n is present in s we find its 0-based position pos
    // and then compute j = n - pos(1-based)
    int pos0 = 0;
    while (pos0 < n-1 && s[pos0] != n) ++pos0;
    unsigned long long j = (unsigned long long) n - (pos0 + 1); // j in 1..n-1

    // Precompute (n-1)! to iterate all a in 7-order
    unsigned long long factN1 = 1ULL;
    for (unsigned long long k = 2; k <= (unsigned long long int)(n-1); ++k) factN1 *= k;

    int *scand = malloc((n-1) * sizeof(int));
    if (!scand){ free(s); fprintf(stderr, "malloc failed\n"); return (unsigned long long)-1; }

    for (unsigned long long r7 = 0ULL; r7 < factN1; ++r7){
        int *a = unrank7Order(n-1, r7); // Length n-1
        unsigned long long r7next = (r7 + 1ULL) % factN1;
        int *b = unrank7Order(n-1, r7next); // Successor in 7-order
        
        // build sCandidate using a,b and j
        // sCandidate = a_{j+1}..a_{n-1}, n, b1..b_{j-1}
        int idx = 0;
        for (unsigned long long k = j; k <= n-2; ++k) scand[idx++] = a[k];
        scand[idx++] = n;
        // We need to check this as j is unsigned 
        if ((long long) j - 2 >= 0){
            for (unsigned long long k = 0; k <= j-2; ++k) scand[idx++] = b[k];
        }

        // compare with s
        int eq = 1;
        for (int t = 0; t < n-1; ++t){ if (scand[t] != s[t]) { eq = 0; break; } }

        free(a); 
        free(b);

        if (eq){
            free(s); 
            free(scand);
            // paper's R(s) = 1 + j + n * R7(a); unrank uses r==0 as special; we must return that same r
            return 1ULL + (unsigned long long) j + (unsigned long long) n * r7;
        }
    }

    free(s); 
    free(scand);
    fprintf(stderr, "rankBOrder: failed to locate matching (a,b) for shorthand. n=%d\n", n);
    return (unsigned long long)-1;
}

// ==================================================== //
// Unranking functions
// ==================================================== //
// Given r in [0 .. n! - 1], return the perm at the corrsponding rank
// using the seven ordering convention
int* unrank7Order(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;

    // Recurse for a smaller permutation
    int* a = unrank7Order(n - 1, j);
    
    // Space for the perm that we will return
    int* result = malloc(sizeof(int) * n);
    
    // If the remainder is 0 then we know n will be 
    // in the first postion of the perm and we can 
    // insert it there concatenating a to the end of it
    if (rem == 0){
        result[0] = n;
        for (int i = 0; i < n - 1; i++) result[i + 1] = a[i];

    // If the remainder is non-zero then we need to determine 
    // the postion of n within this perm 
    }else{
        // Find the 0 baised postion of n within the perm
        int pos = n - rem;

        // Copy elements of a before insertion point
        for (int i = 0; i < pos; i++) result[i] = a[i];
        
        // Insert n
        result[pos] = n;

        // Copy elements of a after insertion point
        for (int i = pos; i < n - 1; i++) result[i + 1] = a[i]; 
    }
    
    free(a);
    return result;
}


int *unrankBOrder(int n, unsigned long long r){
    if (n <= 1){
        int *one = malloc(sizeof(int)); 
        if (!one) return NULL;
        one[0] = 1; 
        return one;
    }
    if (n == 2){
        int *p = malloc(2 * sizeof(int));
        if (r == 0ULL){ p[0] = 2; p[1] = 1; }
        else { p[0] = 1; p[1] = 2; }
        return p;
    }

    unsigned long long factN1 = 1ULL;
    for (unsigned long long k = 2; k <= (unsigned long long)(n-1); ++k) factN1 *= k;


    if (r == 0ULL){
        // We know this perm will always have the form n, n-1, ..., 1
        int *res = malloc(n * sizeof(int));
        for (int i = 0; i < n; ++i) res[i] = n - i;
        return res;
    }

    unsigned long long t = r - 1ULL;
    unsigned long long r7 = t / (unsigned long long) n;
    unsigned long long j = t % (unsigned long long) n; // j in 0..n-1

    if (j == 0ULL){
        // If n not present in shorthand
        // s is permutation in Π(n-1) with rank r7
        int *a = unrank7Order(n-1, r7); // length n-1
        int *res = malloc(n * sizeof(int));
        for (int i = 0; i < n-1; ++i) res[i] = a[i];
        res[n-1] = n; // missing symbol is n
        free(a);
        return res;
    }else{
        // j in 1..n-1: shorthand s is built from a and its successor b and j.
        int jj = (int) j;
        int *a = unrank7Order(n-1, r7);
        unsigned long long r7next = (r7 + 1ULL) % factN1;
        int *b = unrank7Order(n-1, r7next);

        int *s = malloc((n-1) * sizeof(int));
        buildcandidate(s, a, b, n, jj);

        // Determine the missing symbol m from 1..n-1 not in s (since s contains n)
        int present[15];
        memset(present, 0, sizeof(present));
        for (int i = 0; i < n-1; ++i) if (s[i] >= 1 && s[i] <= n-1) present[s[i]] = 1;

        int m = -1;
        for (int v = 1; v <= n-1; ++v) if (!present[v]) { m = v; break; }
        if (m == -1){
            fprintf(stderr, "unrankBOrder: failed to find missing symbol\n");
            free(a); 
            free(b); 
            free(s);
            return NULL;
        }

        // the decoded permutation is s followed by m
        int *res = malloc(n * sizeof(int));
        for (int i = 0; i < n-1; ++i) res[i] = s[i];
        res[n-1] = m;

        free(a); 
        free(b); 
        free(s);
        return res;
    }
}


// ==================================================== //
// Example usage
// ==================================================== //

int main(int argc, char **argv){
    int type = 0;
   
    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) {
        // Set the total number of blocks to (n-1)!
        blocksTotal = 1; 
        for (unsigned int i = 2; i < n; i++) blocksTotal *= i;

        U = malloc(fact * sizeof(int));
        if (!U){
            fprintf(stderr, "Error allocating memory -> terminating program\n\n");
            return 1;
        }

        blocks = malloc(blocksTotal * (n - 1) * sizeof(int));
        if (!blocks){ 
            fprintf(stderr, "Error allocating memory -> terminating program\n\n"); 
            free(U); 
            return 1; 
        }

        // Initialize a to n, n-1 ... 1
        for (int i = 0; i < n; i++) a[i] = n - i;
        
        Bell7(2);

        // Build the full SP-cycle U by inserting n between successive blocks
        for (unsigned long long b = 0; b < blocksTotal; b++){
            U[writePos++] = n;
            // Append block b (n-1 entries)
            int base = (int)b * (n - 1);
            for (int j = 0; j < n - 1; j++) U[writePos++] = blocks[base + j];
        }

        if (writePos != (long)fact) {
            fprintf(stderr, "Internal error: expected %llu entries but wrote %ld\n", fact, writePos);
        }

        // print the SP-cycle (n! symbols)
        for (long i = 0; i < writePos; i++) printf("%d", U[i]);
        printf("\n");

        free(U);
        free(blocks);

    }
    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 + rankBOrder(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 = unrankBOrder(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;
}