//----------------------------------------------------------------------------------------
// Concatentation constructions of universal cycles for shorthand permutations
//
// BASED ON: "Shorthand Universal Cycles for Permutations" by Holroyd, Ruskey, Williams
//           (Algorithmica, 2012) One minor typo in the paper addressed.
// PROGRAMMED BY: Joe Sawada -- 2020
//----------------------------------------------------------------------------------------

#include<stdio.h>
int n,a[100];
long long int total=0;

//------------------------------------------------------
void Print(){
    
    for (int i=0; i<n; i++) {
        if (a[i] < 10) printf("%d", a[i]);
        else printf("%c", a[i]-10+'A'); // Uset letters for 10+
    }
    total+=n;
}
//------------------------------------------------------
void Swap(int i, int j) {
    int tmp;
    
    tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
//------------------------------------------------------
void Shift(int x, int y) {
    int i,tmp;
    
    tmp = a[x];
    for (i=x; i<y; i++) a[i] = a[i+1];
    a[y] = tmp;
}

//------------------------------------------------------
void Cool(int m) {
    int i,j;
    
    Print();
    for (j=1; j<=m-2; j++) {
        Shift(j,m-1);
        for (i=m-2; i>=j; i--) {
            Cool(i+1);  // TYPO FROM RESEARCH PAPER
            Swap(i,i+1);
        }
    }
}
//------------------------------------------------------
void Bell(int m) {
    int i;
    
    if (m == n) { Print(); return; }
    Bell(m+1);
    Shift(n-m,n-1);
    for (i=n-2; i>= n-m; i--) {
        Bell(m+1);
        Swap(i,i+1);
    }
}
//------------------------------------------------------
int main() {
    int i,type;
    
    printf("Enter n>1: ");   scanf("%d", &n);
    printf("Enter type (1) Coolex (2) Bell-ringer: ");   scanf("%d", &type);
    
    // INITIAL STRING
    for (i=0; i<n; i++) a[i] = n-i;
    
    if (type == 1) Cool(n);
    if (type == 2) Bell(2);

    printf("\n\nLength = %lld\n\n", total);
}