//------------------------------------------------------------------------
// Univeral cycles for k-subsets and k-multisets via O(n) time successor
// rules using difference and shorthand frequency reps, using both
// PCR-based and MSR-based cycle-joining trees.  The UCs are based on
// bounded weight de Bruijn sequences.

// Programmed by Joe Sawada, 2025.
//------------------------------------------------------------------------
#include<stdio.h>
#define Min(a,b) (a<b) ? a : b
#define MAX_N 100

int n,k,w,a[MAX_N];
// ==========================================
// Return TRUE iff a[1..n] = 0^n
// ==========================================
int Zeros(int a[]) {
    for (int i=1; i<=n; i++) if (a[i] != 0) return 0;
    return 1;
}
// ==========================================
// Return the weight of a[1..n]
// ==========================================
int Weight(int a[]) {
    int i,w=0;
    for (i=1; i<=n; i++) w += a[i];
    return w;
}
// ==========================================
// Return TRUE iff b[1..t] is a necklace
// ==========================================
int IsNecklace(int b[], int t) {
    int i, p=1;

    for (i=2; i<=t; i++) {
        if (b[i-p] > b[i]) return 0;
        if (b[i-p] < b[i]) p = i;
    }
    if (t % p != 0) return 0;
    return 1;
}
//=======================================================================
// Scan string to find smallest symbol after any 0^s substring in a[2..t]
//=======================================================================
int MaxNext(int a[], int t, int s) {
    int i, z=0, v=k-1;
    
    for (i=2; i<=t; i++) {
        if (z == s) v = Min(v,a[i]);
        if (a[i] == 0) z++;
        else z = 0;
    }
    return v;
}
// =========================================================================================
// Let j be the largest index of a non-0 symbol (or 1 if no such index exists)
// Return the largest value x in in {1,2, ..., k-1} such that 0^{n-j} x a[2..j] satisfies
// the weight constraint and is a necklace. Return -1 if no such value exists.
// =========================================================================================
int GetGrandmaX(int a[]) {
    int i,x,j=n,b[MAX_N];
    
    while (j>1 && a[j] == 0) j--;
    
    // Rotate 0s to front of string
    for (i=1; i<=n-j; i++)   b[i] = 0;
    for (i=n-j+1; i<=n; i++) b[i] = a[i-(n-j)];
    
    // OPTIMIZATION TO GET FIRST VIABLE OPTION FOR x
    x = Min(w - Weight(a) + a[1], MaxNext(a,j,n-j));
    if (x == 0) return -1;
   
    b[n-j+1] = x;
    if (IsNecklace(b,n)) return x;
    else if (x>1) return x-1;
    return -1;
}
//--------------------------------------------
int Grandmama(int a[]) {
    
    int x = GetGrandmaX(a);
    if (x != -1 && a[1] == x) return 0;
    if (x != -1 && a[1] < x)  return a[1] + 1;
    return a[1];
}
//--------------------------------------------
int Grandmama2(int a[]) {
    
    int x = GetGrandmaX(a);
    if (x != -1 && a[1] == 0) return x;
    if (x != -1 && a[1] > 0 && a[1] <=x) return a[1] - 1;
    return a[1];
}
// =========================================================================================
// Let j be the largest index of a non-0 symbol (or 1 if no such index exists)
// Return the largest value x in {1,...,k-1} such that (i) y=z-x+a[1] in {0,...,k-1}
// and (ii) 0^{n-j} xy a[2..j] is a necklace.  There is weight constraint w < k.
// Return -1 if no such value exists.
// =========================================================================================
int GetMSRX(int a[], int z) {
    int i,x,j=n,b[MAX_N+1];
    
    while (j>1 && a[j] == 0) j--;
    
    // Rotate 0s to front of string and insert position for missing symbol after 0s
    for (i=1; i<=n-j; i++)   b[i] = 0;
    for (i=n-j+1; i<=n; i++) b[i+1] = a[i-(n-j)];
    
    // OPTIMIZATION TO GET FIRST VIABLE OPTION FOR x
    x = Min(z+a[1], MaxNext(a,j,n-j));
    if (x == 0) return -1;
    
    b[n-j+1] = x;
    b[n-j+2] = z-x+a[1];
    if (IsNecklace(b,n+1)) return x;
    else if (x > 1) return x-1;
    return -1;
}
//--------------------------------------------
int MSR(int a[]) {
    
    int z = w - Weight(a);
    int x = GetMSRX(a,z);
        
    if (n==1) return (a[1]+1) % (w+1);
    
    if (x != -1 && z == x) return 0;
    if (x != -1 && z < x)  return z + 1;
    return z;
}
//--------------------------------------------
int MSR2(int a[]) {
    
    int z = w - Weight(a);
    int x = GetMSRX(a,z);
    
    if (n==1) return (a[1]+w) % (w+1);
            
    if (x != -1 && z == 0) return x;
    if (x != -1 && z > 0 && z <= x)  return z - 1;
    return z;
}
// =====================================================================
// Generate universal cycles by iteratively applying a successor rule
// =====================================================================
void UC(int type) {
    int i, new_bit, count = 0;

    // Initialize first n bits
    for (i=0; i<=n; i++)  a[i] = 0;
    do {
        count++;
        printf("%d", a[1]);
        
        if (type == 1) new_bit = Grandmama(a);
        if (type == 2) new_bit = Grandmama2(a);
        if (type == 3) new_bit = MSR(a);
        if (type == 4) new_bit = MSR2(a);

        // Shift and add new bit
        for (i=1; i<=n; i++) a[i] = a[i+1];
        a[n] = new_bit;
    } while (!Zeros(a));
    
    printf("\nLength = %d\n\n", count);
}
//------------------------------------------------------
int main() {
    
    printf("Construct bounded-weight de Bruijn sequences.  Enter converted values of n and k with the upper bound on the weight w to obtain universal cycles for subsets and multisets.\n\n");
    printf("Enter n k w: ");    scanf("%d %d %d", &n, &k, &w);
    
    printf("Grandmama (incr):\n");
    UC(1);
    printf("Grandmama (decr):\n");
    UC(2);

    if (w < k) {
        printf("MSR (incr):\n");
        UC(3);
        printf("MSR (decr):\n");
        UC(4);
    }
}