//=================================================================================== // Ranking and unranking algorithms for k-ary necklaces, Lyndon words and de Bruijn // sequences over the alphabet {1,2, ... ,k} // // Programmed by Joe Sawada Dec, 2015 //=================================================================================== #include #define MAX 63 // n=62 is largest feasible for long long integers when k=2 int mu[MAX] = { 0,1,-1,-1,0,-1,1,-1,0,0,1,-1,0,-1,1,1,0,-1,0,-1,0, 1,1,-1,0,0,1,0,0,-1,-1,-1,0,1,1,1,0,-1,1,1,0,-1, -1,-1,0,0,1,-1,0,0,0,1,0,-1,0,1,0,1,1,-1,0,-1,1}; int phi[MAX] = { 0,1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12, 10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18, 24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18, 40,24,36,28,58,16,60,30}; int k, NECKLACE=0, LYNDON=0, DB=0; long long int power[MAX]; //=================================================================================== // Find the longest prefix of w[1..n] that is a Lyndon word //=================================================================================== int Lyn(int n, int w[]) { int i,p=1; for (i=2; i<=n; i++) { if (w[i] < w[i-p]) return p; if (w[i] > w[i-p]) p = i; } return p; } //=================================================================================== // Return whether or not w[1..n] is a necklace //=================================================================================== int IsNecklace(int n, int w[]) { int i,p=1; for (i=2; i<=n; i++) { if (w[i] < w[i-p]) return 0; if (w[i] > w[i-p]) p=i; } if (n%p == 0) return 1; return 0; } //=================================================================================== // Compute the largest necklace neck[1..n] <= w[1..n] //=================================================================================== void LargestNecklace(int n, int w[], int neck[]) { int i,p; for (i=1; i<=n; i++) neck[i] = w[i]; while (!IsNecklace(n,neck)) { p = Lyn(n,neck); neck[p]--; for (i=p+1; i<=n; i++) neck[i] = k; } } //=================================================================================== // Compute the largest Lyndon word neck[1..n] <= w[1..n] //=================================================================================== void LargestLyndon(int n, int w[], int neck[]) { int i,p; for (i=1; i<=n; i++) neck[i] = w[i]; while (Lyn(n,neck) != n) { p = Lyn(n,neck); neck[p]--; for (i=p+1; i<=n; i++) neck[i] = k; } } //=================================================================================== // Return the number of strings whose necklace is <= w[1..n] //=================================================================================== long long int T(int n, int w[]) { int i,j,t,s,neck[MAX],suf[MAX][MAX]; long long int tot, B[MAX][MAX]; // Sets neck[1..n] to the largest necklace less than or equal to w[1..n] LargestNecklace(n, w, neck); // Compute B[t][j] = number of strings of length t with prefix neck[1..j] but // no suffix less than neck[1..n] B[0][0] = 1; for (t=1; t<=n; t++) { B[t][t] = 0; for (j=t-1; j>=0; j--) B[t][j] = B[t][j+1] + ((k - neck[j+1]) * B[t-j-1][0]); } // Compute suf[i][j] = longest suffix of neck[i..j] that is a prefix of neck[1..n] for (i=2; i<=n; i++) { s = i; for (j=i; j<=n; j++) { if (neck[j] > neck[j-s+1]) s = j+1; suf[i][j] = j-s+1; } } // Compute T(...) tot = Lyn(n,neck); for (t=1; t<=n; t++) { for (j=0; j neck[s+1]) tot += B[n-j+s][s+1] + (neck[j+1]-neck[s+1]-1) * B[n-j-1][0]; } } } return(tot); } //=================================================================================== // Return the rank of w[1..n] - a valid Lyndon word or necklace - in lex order //=================================================================================== long long int Rank(int n, int w[]) { int i; long long int r=0; for (i=1; i<=n; i++) { if (n%i == 0) { if (NECKLACE) r += phi[n/i] * T(i,w); if (LYNDON) r += mu[n/i] * T(i,w); } } return(r/n); } //=================================================================================== // Return the necklace or Lyndon w[1..n] for a given valid rank in lex order //=================================================================================== void UnRank(int n, long long int r, int w[]) { int j,min,max,prev,t; // Start with necklace or Lyndon word with largest rank for (j=1; j<=n; j++) w[j] = k; if (LYNDON) w[1] = k-1; // Determine character w[j] from left to right using a binary search for (j=1; j<=n; j++) { min = 1; max = k; while (min < max) { prev = w[j]; t = (min+max)/2; w[j] = t; if (NECKLACE && IsNecklace(n,w) && Rank(n,w) >= r) max = t; else if (LYNDON && Lyn(n,w) == n && Rank(n,w) >= r) max = t; else { w[j] = prev; min = t+1; } } } } //=================================================================================== // Return the rank of w[1..n] in the lexicographically smallest de Bruijn sequence //=================================================================================== long long int RankDB(int n, int w[]) { int i,t,j,s=0,neck[MAX],prev[MAX]; // w[1..n] = k^t 1^{n-t} for t >= 1, which includes all wraparounds t=0; while (w[t+1] == k && t+1 <=n) t++; j=t; while (w[j+1] == 1 && j+1 <=n) j++; if (t >= 1 && j == n) return(power[n]-t+1); // w[1..n] is a necklace if (IsNecklace(n,w)) return(1 - Lyn(n,w) + T(n,w)); // Find the necklace neck[1..n] of w[1..n] and its offset for (i=1; i<=n; i++) neck[i] = w[i]; while (!IsNecklace(n,neck)) { s++; for (i=1; i<=n; i++) { if (i+s <= n) neck[i] = w[i+s]; else neck[i] = w[i+s-n]; } } if (s != t) return (RankDB(n,neck) + Lyn(n,neck) - s); if (Lyn(n,neck) < n) return (RankDB(n,neck) - s); for (i=n-s+1; i<=n; i++) neck[i] = 1; LargestNecklace(n,neck,prev); return (RankDB(n,prev) + Lyn(n,prev) - s); } //=================================================================================== // Return the string starting at index r in the lex smallest de Bruijn sequence //=================================================================================== void UnRankDB(int n, long long int r, int w[]) { int i,j,min,max,last,t,p,neck[MAX],prev[MAX],prev2[MAX]; long long int d; // Special case for strings in the wraparound d = power[n] - r+1; if (d < n) { for (j=1; j<= d; j++) w[j] = k; for (j=d+1; j<=n; j++) w[j] = 1; return; } //-------------------------------------------------------------------------------- // Find the smallest necklace neck[1..n] whose rank is greater than or equal to r for (j=1; j<=n; j++) neck[j] = k; // Determine character neck[j] from left to right using a binary search for (j=1; j<=n; j++) { min = 1; max = k; while (min < max) { last = neck[j]; t = (min+max)/2; neck[j] = t; if (IsNecklace(n,neck) && RankDB(n,neck) >= r) max = t; else { neck[j] = last; min = t+1; } } } //--------------------------------------------------------------------------------- d = RankDB(n,neck) - r; if (d == 0) { for (i=1; i<=n; i++) w[i] = neck[i]; } else { // Get the previous 2 necklaces prev and prev2 in lex order neck[n]--; LargestNecklace(n,neck,prev); neck[n]++; prev[n]--; LargestNecklace(n,prev,prev2); prev[n]++; p = Lyn(n,prev); j = 1; if (p >= d) { for (i=1; i<=d; i++) w[j++] = prev[n-d+i]; } else { for (i=1; i<=d-p; i++) w[j++] = prev2[n-(d-p)+i]; for (i=1; i<=p; i++) w[j++] = prev[i]; } for (i=1; i<=n-d; i++) w[j++] = neck[i]; } } //=================================================================================== // Compute the number of necklaces (or Lyndon words) with a given prefix by computing // the rank of the largest necklace with the given prefix (r2) and subtracting the // rank of the largest necklace with a smaller prefix (r1). //=================================================================================== long long int CountGivenPrefix(int pre[], int n, int j) { int i,p,w[MAX]; long long int r1,r2; if (j == n) { if (LYNDON && Lyn(n,pre) == n) return 1; if (!LYNDON && IsNecklace(n,pre)) return 1; return 0; } for (i=j+1; i<=n; i++) pre[i] = 1; if (LYNDON) LargestLyndon(n,pre,w); else LargestNecklace(n,pre,w); r1 = Rank(n,w); for (i=j+1; i<=n; i++) pre[i] = k; if (LYNDON) LargestLyndon(n,pre,w); else LargestNecklace(n,pre,w); r2 = Rank(n,w); // Check if prefix is of form 111...11 i = 1; while (pre[i] == 1 && i <=j) i++; if (i == j && pre[1] == 1) return r2; else return r2 - r1; } //=================================================================================== int main() { int i,j,n,option,w[MAX],pre[MAX]; long long int r; printf("1 = Rank Necklaces \n"); printf("2 = Rank Lyndon Words \n"); printf("3 = Rank de Bruijn Sequence \n\n"); printf("4 = UnRank Necklaces \n"); printf("5 = UnRank Lyndon Words \n"); printf("6 = UnRank de Bruijn Sequence \n\n"); printf("7 = Count Necklaces with a given prefix \n"); printf("8 = Count Lyndon Words with a given prefix \n\n"); printf("Select option #: "); scanf("%d", &option); printf("Enter n k: "); scanf("%d %d", &n, &k); // PRECOMPUTE power[i] = k^i power[0] = 1; for (i=1; i<=n; i++) power[i] = power[i-1] * k; if (option == 1 || option == 4 || option == 7) NECKLACE = 1; if (option == 2 || option == 5 || option == 8) LYNDON = 1; if (option == 3 || option == 6) DB = LYNDON = 1; if (option == 1 || option == 2 || option == 3) { printf("Enter string w[1..n] over alphabet {1,2,...,k}\n"); for (i=1; i<=n; i++) { printf(" w[%d] = ", i); scanf("%d", &w[i]); } if (option == 3) printf("\nRank = %lld\n", RankDB(n,w)); else printf("\nRank = %lld\n", Rank(n,w)); } if (option == 4 || option == 5 || option == 6) { printf("Enter rank: "); scanf("%lld", &r); if (option == 6) UnRankDB(n,r,w); else UnRank(n,r,w); for (i=1; i<=n; i++) printf("%d", w[i]); printf("\n"); } if (option == 7 || option == 8) { printf("Enter prefix length 1 < j < n: "); scanf("%d", &j); printf("Enter prefix over alphabet {1,2,...,k}\n"); for (i=1; i<=j; i++) { printf(" p[%d] = ", i); scanf("%d", &pre[i]); } printf("Count = %lld\n", CountGivenPrefix(pre,n,j)); } }