//------------------------------------------------------------------------
// Listings of k-ary de Bruijn sequences via the following successor rules:
//   1. Wong successor
//   2. Williams Successor
//   3. Lex minimal for Granddaddy sequence
//   4. Colex
//
// Research by Joe Sawada, Aaron Williams, Dennis Wong, Daniel Gabric
// Programmed by Joe Sawada, 2015-2018.
//------------------------------------------------------------------------
#include<stdio.h>
#include<math.h>
#define Min(a,b) (a<b) ? a : b
#define Max(a,b) (a>b) ? a : b
#define MAX_N 100

int n,k,a[MAX_N];

// ==========================================
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 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)
// ==========================================
// ==================================================================================
// 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[MAX_N];
    
    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 Williams(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 Williams2(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)
// ==================================================================================
// 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[MAX_N];
    
    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 Wong(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 Wong2(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
// =========================================================================================
// 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[MAX_N];
    
    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 Grandmama(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 Grandmama2(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];
}
// ================
// Granddaddy - LEX LEAST
// ======================================================================
// 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 GetGranddaddyX(int a[]) {
    int i,x,p=1,j=2,b[MAX_N];
    
    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 Granddaddy(int a[]) {
    
    int x = GetGranddaddyX(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 Granddaddy2(int a[]) {
    
    int x = GetGranddaddyX(a);
    
    if (x != 0 && a[1] == x) return k;
    if (x != 0 && a[1] >=x) return a[1]-1;
    return a[1];
}
// ==========================================
// Generate de Bruijn sequences by iteratively
// applying a successor rule
// ==========================================
void DB(int type) {
    int i, new_bit;

    // Initialize and output first n bits
    for (i=0; i<=n; i++)  a[i] = 1;
    do {
        printf("%d", a[1]-1);

        switch(type) {
            case 1: new_bit = Williams(a); break;
            case 2: new_bit = Williams2(a); break;
            case 3: new_bit = Wong(a); break;
            case 4: new_bit = Wong2(a); break;
            case 5: new_bit = Grandmama(a); break;
            case 6: new_bit = Grandmama2(a); break;
            case 7: new_bit = Granddaddy(a); break;
            case 8: new_bit = Granddaddy2(a); break;
            default: break;
        }
        
        // 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() {
    int i;
    
	printf("Enter n: ");    scanf("%d", &n);
    printf("Enter k: ");    scanf("%d", &k);

    for (i=1; i<=8; i++) {
        switch(i) {
            case 1: printf("First Symbol (incr):\n");  break;
            case 2: printf("First Symbol (decr):\n");  break;
            case 3: printf("Last Symbol (incr):\n"); break;
            case 4: printf("Last Symbol (decr):\n"); break;
            case 5: printf("Grandmama (incr):\n"); break;
            case 6: printf("Grandmama (decr):\n"); break;
            case 7: printf("Granddaddy lex minimal (incr):\n"); break;
            case 8: printf("Granddaddy (decr):\n"); break;
            default: break;
        }
        DB(i);
        printf("\n\n");
    }
}