//--------------------------------------------------------------------------
// Recursive DB sequence constructions from Knuth Vol 4A (p304-305). The
// The recursion is based on a choosen successur rule function f that
// generates a DB sequence of order n, in order to output a DB sequence
// of order n+1 or 2n respectively.  Each symbol is output in the time
// required and space required by f: O(n) time per symbol, using O(n) space.
// The single recursive is based on Lempel's homomorphism.  The doubly
// recursive construction is based on work by Mitchell, Etzion, Paterson (1996)

// The implementation works for a k-ary alphabet for n>=2.  Four successor
// rules f can be selected: PCR1, PCR2, PCR3, PCR4, or their alternates to
// construct the original DB sequence.

// Implemented by Joe Sawada, May 2026 for debruijnsequence.org
//-------------------------------------------------------------------------
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define Min(a,b) (a<b) ? a : b
#define Max(a,b) (a>b) ? a : b

int n,k;

// ==========================================
// Return TRUE iff b[1..n] is a necklace
// ==========================================
int IsNecklace(int b[]) {
    int i, p=1;

    for (i=2; i<=n; i++) {
        if (b[i-p] > b[i]) return 0;
        if (b[i-p] < b[i]) p = i;
    }
    if (n % p != 0) return 0;
    return 1;
}
// ==================================================================================
// FIRST SYMBOL (WILLIAMS) over {1,2, ... k}
//
// Return the largest value x in {1,2, ..., k-1} such that xa[2..n] is a necklace or
// Return 0 if no such element exists
// ==================================================================================
int GetWilliamsX(int a[]) {
    int i,x=k-1, b[n+1];
    
    for (i=1; i<=n; i++) b[i] = a[i];
    for (i=2; i<=n; i++) x = Min(x, b[i]);
    
    b[1] = x;
    if (IsNecklace(b)) return x;
    return x-1;
}
//--------------------------------------------
int PCR4(int a[]) {
    
    int x = GetWilliamsX(a);
    if (x != 0 && a[1] == x+1) return 1;
    if (x != 0 && a[1] < x+1) return a[1]+1;
    return a[1];
}
//--------------------------------------------
int PCR4b(int a[]) {
    
    int x = GetWilliamsX(a);
    if (x != 0 && a[1] == 1) return x+1;
    if (x != 0 && a[1] > 1 && a[1] <= x+1) return a[1]-1;
    return a[1];
}
// ==================================================================================
// LAST SYMBOL (WONG) over {1,2, ... k}
//
// Return the smallest value x in {2,3, ..., k} such that a[2..n]x is a necklace or
// Return 0 if no such element exists
// ==================================================================================
int GetWongX(int a[]) {
    int i, p=1, b[n+1];
    
    for (i=1; i<=n-1; i++) b[i] = a[i+1];
    
    for (i=2; i<=n-1; i++) {
        if (b[i-p] > b[i]) return 0;
        if (b[i-p] < b[i]) p = i;
    }
    
    if (n%p == 0) return Max(b[n-p],2);
    else if (b[n-p] < k) return b[n-p]+1;
    return 0;
}
//--------------------------------------------
int PCR3(int a[]) {
    
    int x = GetWongX(a);
    if (x != 0 && a[1] == k) return x-1;
    if (x != 0 && a[1] < k && a[1] >= x-1) return a[1]+1;
    return a[1];
}
//--------------------------------------------
int PCR3b(int a[]) {
    
    int x = GetWongX(a);
    if (x != 0 && a[1] == x-1) return k;
    if (x != 0 && a[1] > x-1) return a[1]-1;
    return a[1];
}
// =========================================================================================
// GRANDMAMA - FIRST NON-1 over {1,2, ... k}
//
// Return the largest value x in in {2,3, ..., k} such that 1^{n-j} x a[2..j] is a necklace;
// Return 0 if no such value exists.  This is O(kn), but could be simplified to O(n).
// =========================================================================================
int GetGrandmaX(int a[]) {
    int i,x,j=n,b[n+1];
    
    while (j>1 && a[j] == 1) j--;
    
    // Rotate 1s to front of string
    for (i=1; i<=n-j; i++)    b[i] = 1;
    for (i=n-j+1; i<=n; i++) b[i] = a[i-(n-j)];
    
    for (x=k; x>=2; x--) {
        b[n-j+1] = x;
        if (IsNecklace(b)) return x;
    }
    return 0;
}
//--------------------------------------------
int PCR2(int a[]) {
    
    int x = GetGrandmaX(a);
    if (x != 0 && a[1] == x) return 1;
    if (x != 0 && a[1] < x) return a[1] + 1;
    return a[1];
}
//--------------------------------------------
int PCR2b(int a[]) {
    
    int x = GetGrandmaX(a);
    if (x != 0 && a[1] == 1) return x;
    if (x != 0 && a[1] > 1 && a[1] <=x) return a[1] - 1;
    return a[1];
}
// ======================================================================
// FORD - LAST NON-k (Granddaddy, Lex least) over {1,2, ... k}
//
// Return the smallest value x such that a[j..n] x k^{n-t} is a necklace;
// Return 0 if no such value exists
// ======================================================================
int GetFordX(int a[]) {
    int i,x,p=1,j=2,b[n+1];
    
    while (j<=n && a[j] == k) j++;
    if (j == n+1) return 1;
    
    for (i=1; i<=n-j+1; i++)  b[i] = a[j+i-1];
    
    for (i=2; i<= n-j+1; i++) {
        if (b[i-p] > b[i]) return 0;
        if (b[i-p] < b[i]) p = i;
    }
    
    x = b[n-j+2] = b[(n-j+2)-p];
    for (i=n-j+3; i<=n; i++)  if (b[i-p] < k) return x;
    
    if (n%p == 0) return x;
    else if (x < k) return x+1;
    return 0;
}
//--------------------------------------------
int PCR1(int a[]) {
    
    int x = GetFordX(a);
    if (x != 0 && a[1] == k) return x;
    if (x != 0 && a[1] < k && a[1] >=x) return a[1]+1;
    return a[1];
}
//--------------------------------------------
int PCR1b(int a[]) {
    
    int x = GetFordX(a);
    if (x != 0 && a[1] == x) return k;
    if (x != 0 && a[1] >=x) return a[1]-1;
    return a[1];
}

// ============================================================================
// Apply the given successor rule to find the next bit generated in the
// DB sequence of order n
// ============================================================================
int F(int type, int a[]) {
    int i,next,output;
    
    output = a[1]-1;    // Recursion working on {0,1, ... ,k-1}
    
    // Shift to next state
    if (type == 1) next = PCR1(a);
    if (type == 2) next = PCR2(a);
    if (type == 3) next = PCR3(a);
    if (type == 4) next = PCR4(a);
    if (type == 5) next = PCR1b(a);
    if (type == 6) next = PCR2b(a);
    if (type == 7) next = PCR3b(a);
    if (type == 8) next = PCR4b(a);
    
    for (i=1; i<n; i++) a[i] = a[i+1];
    a[n] = next;
    
    return output;
}
// ============================================================================
// Recursively constructs a DB sequence order n+1 from a DB sequence (generated
// by F) of order n >=2 beginning with 0^n. Alphabet = {0,1, ..., k-1}.
// ============================================================================
void KnuthSingle(int f) {
    int x,y,t,i,count,a[n+1];
    long int len = (long int) pow(k,n+1);
    
    // Initialize f using a[] since f works over alphabet {1,2,..,k}
    for (i=1; i<=n; i++) a[i] =  1;
    
    x = count = 0;
    while (count < len) {
        printf("%d", x); count++;          // R1
        if (x == 0 || t < n) y = F(f,a);   // R2
        if (y == 1) t++;                   // R3
        else t = 0;
        if (t == n && x != 0) {            // R4 (repeat R2/R3)
            y = F(f,a);
            if (y == 1) t++;
            else t = 0;
        }
        x = (x+y) % k;                     // R5
    }
}
// ============================================================================
// Recursively constructs a DB sequence of order 2n from a DB sequence
// of order n beginning with 0^n. Alphabet = {0,1, ..., k-1}. The procedure
// interleaves two traces the same initial DB sequence where the values are
// consumed at different rates.
// ============================================================================
void KnuthDouble(int f) {
    int x,y,t,x2,y2,t2,a[n+1],b[n+1],r,i,count,flag;
    long int len = (long int) pow(k,2*n);
    
    // 0 <= r <= k satisfies gcd(k^n - r, k^n +r) = 2
    if (k%2 == 1) r = 1;
    else r=2;
        
    // Initialize a[] and b[] to 1^n since f works over alphabet {1,2,..,k}
    for (i=1; i<=n; i++) a[i] = b[i] = 1;
    
    x = x2 = k;
    count = 0; flag = 1;
    while (count < len) {
        if (flag == 1) {
            if (t != n || x >= r) y = F(f,a);                       // D1
            if (x != y) { x = y; t = 1;}                            // D2
            else t++;
        }
        if (flag == 1 || flag == 3) { printf("%d", x); count++; }   //D3
            
        y2 = F(f,b);                                                // D4
        if (x2 != y2) { x2 = y2; t2 = 1;}                           // D5
        else t2++;
        
        if (t2 == n && x2 < r && (t<n || x2 < x)) flag = 4;         // D6 GOTO D4
        else if (t2 == n && x2 < r && x2 == x) flag = 3;            // D6 GOTO D3
        else {
            printf("%d", x2);  count++;                             // D7 GOTO D3 or D1
            if (t2 == n && x2 < r) flag = 3;
            else flag = 1;
        }
    }
}
//------------------------------------------------------
int main() {
    int type,f;
    
    printf("Enter [1] for single recursive (n+1) or [2] for double recursive (2n): ");
    scanf("%d", &type);
           
    printf("Enter [n] >=2: "); scanf("%d", &n);
    printf("Enter [k] >=2: "); scanf("%d", &k);
    printf("Enter [1-8] for co-routines PCR1, PCR2, PCR3, PCR4, PCR1(alt), PCR2(alt), PCR3(alt), PCR4(alt): ");
    scanf("%d", &f);
    
    if (type == 1) KnuthSingle(f);
    else KnuthDouble(f);
}