// =========================================================================================
// Constructing k-ary de Bruijn sequences of order n based on an arbitray non-singular
// feedback function f.  If C is the length of the longest cycle in the partition induced
// by f then the running time is O(nkc) per symbol using only O(n) space.  For functions like
// f(a[1..n]) = a[1] + s, whose largest cycle is O(kn) the algorithm requires O(k^2 n^2) per
// symbol.  However, this could be optimized to O(k^2 n) by using O(kn) space.
//
// Research by Joe Sawada and Daniel Gabric
// Programmed by Joe Sawada, 2018.
// =========================================================================================
#include<stdio.h>
#define MAX_N 100

int n,k,a[MAX_N];

// =========================================================================================
int Mod(int x) {
    
    while (x < 1) x+=k;
    while (x > k) x-=k;
    return x;
}
// =========================================================================================
int f(int a[]) {
    
    return ( Mod(a[1]+1) );  // INSERT ANY NON-SINGULAR FEEDBACK FUNCTION
}
// =========================================================================================
int Ones(int a[]) {
    for (int i=1; i<=n; i++) if (a[i] != 1) return 0;
    return 1;
}
// =========================================================================================
// Return TRUE iff b[1..n] is a cycle rep = lex smallest string in cycle
// =========================================================================================
int IsRep(int b[]) {
    int i, new_bit, cycle[MAX_N];
    
    for (i=1; i<=n; i++) cycle[i] = b[i];
    
    while (1) {
        // Shift and add new bit until returning to b[]
        new_bit = f(cycle);
        for (i=1; i<=n; i++) cycle[i] = cycle[i+1];
        cycle[n] = new_bit;
        
        // Compare b[] to another in the cycle
        for (i=1; i<=n; i++) {
            if (b[i] < cycle[i]) break;
            if (b[i] > cycle[i]) return 0;
        }
        if (i > n) return 1; // Back to initial string b[]
    }
}
// =========================================================================================
// Compute tau[] and return its size
// =========================================================================================
int TauLastSymbol(int a[], int tau[]) {
    int i,p=0,b[MAX_N];
    
    // Shift and try all values for b[n]
    for (i=1; i<=n; i++) b[i] = a[i+1];
    
    for (i=1; i<=k; i++) {
        b[n] = i;
        if (IsRep(b)) {
            if (i == 1 && !Ones(b)) {
                a[1] = 1;
                tau[++p] = f(a);   // a[1] is never used again, so no need to restore
            }
            else if (i > 1 && p == 0) tau[++p] = 1;
            tau[++p] = i;
        }
    }
    return p;
}
// =========================================================================================
int LastSymbol(int a[]) {
    int tau[MAX_N],i,j,v;
    
    v = f(a);
    j = TauLastSymbol(a,tau);
    
    for (i=1; i<=j; i++) {
        if (v == tau[i] && i < j)  return tau[i+1];
        if (v == tau[i] && i == j) return tau[1];
    }
    return v;
}
// =========================================================================================
int LastSymbol2(int a[]) {
    int tau[MAX_N],i,j,v;
    
    v = f(a);
    j = TauLastSymbol(a,tau);
    
    for (i=1; i<=j; i++) {
        if (v == tau[i] && i == 1)  return tau[j];
        if (v == tau[i] && i > 1)   return tau[i-1];
    }
    return v;
}
// =========================================================================================
// Compute tau'[] and return its size
// =========================================================================================
int TauFirstNonOne(int a[], int tau[]) {
    int i,v,t,j=0,p=0,b[MAX_N];
    
    for (i=1; i<=n; i++) b[i] = a[i];
    
    // Shift the j 1s in the suffix to front of string
    while (j < n && b[n-j] == 1) j++;
    for (i=1; i<=n-j; i++) {
        v = f(b);
        for (t=1; t<n; t++) b[t] = b[t+1];
        b[n] = v;
    }
    if (j == n) return 0;
    
    // Try all values > 1 at position j+1 to see if it is a representative
    p=0;
    for (i=2; i<=k; i++) {
        b[j+1] = i;
        if (IsRep(b)) {
            if (p == 0) tau[++p] = 1;
            tau[++p] = i;
        }
    }
    return p;
}
// =========================================================================================
int FirstNonOne(int a[]) {
    int tau[MAX_N],i,j,v;
    
    v = f(a);
    j = TauFirstNonOne(a,tau);
    
    for (i=1; i<=j; i++) {
        if (v == tau[i] && i < j)  return tau[i+1];
        if (v == tau[i] && i == j) return tau[1];
    }
    return v;
}
// =========================================================================================
int FirstNonOne2(int a[]) {
    int tau[MAX_N],i,j,v;
    
    v = f(a);
    j = TauFirstNonOne(a,tau);
    
    for (i=1; i<=j; i++) {
        if (v == tau[i] && i == 1)  return tau[j];
        if (v == tau[i] && i > 1)   return tau[i-1];
    }
    return v;
}
// =========================================================================================
// Generate de Bruijn sequences by iteratively applying a successor rule h() or h2()
// =========================================================================================
void DB(int type) {
    int i, new_bit;

    // Initialize first n bits to 1^n - could start with any string changing the termination
    for (i=0; i<=n; i++)  a[i] = 1;
    do {
        printf("%d", a[1]-1);
        if (type == 1) new_bit = LastSymbol(a);
        if (type == 2) new_bit = LastSymbol2(a);
        if (type == 3) new_bit = FirstNonOne(a);
        if (type == 4) new_bit = FirstNonOne2(a);
        
        // Shift and add new bit
        for (i=1; i<=n; i++) a[i] = a[i+1];
        a[n] = new_bit;
        
    } while (!Ones(a));
}
// =========================================================================================
int main() {

    printf("The feedback function is hard coded to f(a[1..n]) = (a[1]+1) mod k.\n");
    printf("It can be modified to be any non-singular feedback function\n\n");
    printf("Enter n: ");    scanf("%d", &n);
    printf("Enter k: ");    scanf("%d", &k);
   
    printf("Last symbol (incr):\n");  DB(1);  printf("\n\n");
    printf("Last symbol (decr):\n");  DB(2);  printf("\n\n");
    printf("First non-1 (incr):\n");  DB(3);  printf("\n\n");
    printf("First non-1 (decr):\n");  DB(4);  printf("\n\n");
}