//===========================================================================
// Genereate the (upper) bounded weight "Grandmama" de Bruijn sequence for
// over alphabet {0,1, ... , k-1} and upper bound on weight of w.
// It can be applied to construct a UC for t-subsets or t-multisets of an n-set.
//
// Runs in O(1) amortized time per symbol generated, using O(kn) space
// PROGRAMMED BY: Joe Sawada -- 2025
//===========================================================================
#include<stdio.h>
int a[100],n,k,w;
long long int total=0;

//=============================================================================
// Test if a[1..n] is a necklace, if so return the length of its longest prefix
// otherwise return 0
//===========================================================================
int IsNecklace(int a[]) {
    int i,p=1;
    
    for (i=1; i<=n; i++) {
        if (a[i] < a[i-p]) return 0;
        if (a[i] > a[i-p]) p=i;
    }
    if (n%p == 0) return p;
    return 0;
}

//=============================================================================
// Visit tree in RCL order by dynamically generating children of the current
// node a[1..n], with aperiodic prefix of length p and change index c
//=============================================================================
void RCL(int a[], int p, int c, int weight) {
    int i,j;
    
    // VISIT: Print aperiodic prefix of a[1..n]
    for (i=1; i<=p; i++) printf("%d", a[i]); 
    total += p;
    if (weight == w) return;    // No children when max weight achieved
    
    // Scan from c left to determine the first index for a child
    a[c]++;
    if (a[c] < k && !IsNecklace(a))  { a[c]--; return; }
    a[c]--;
    
    j=c-1;
    a[j] = 1;
    while (j >=1 && IsNecklace(a)) {
        a[j] = 0; j--; a[j] = 1;
    }
    a[j] = 0;
    
    // Visit children from left to right, handle change index separately
    for (i=j+1; i<c; i++) {
        a[i] = 1;
        RCL(a, IsNecklace(a), i, weight+1);
        a[i] = 0;
    }
    if (a[c] < k-1) {
        a[c]++;
        RCL(a, IsNecklace(a), c, weight+1);
        a[c]--;
    }
}
//===============================================
int main() {
    int i;
    
    printf("Construct the Grandmama bounded-weight de Bruijn sequence via a concatenation approach.  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);
    for (i=1; i<=n; i++) a[i] = 0;
    RCL(a,1,n,0);
    
    printf("\nLength = %lld\n\n", total);
}