Compact way to produce a large sequence of strings in lexical order

Question

I want to generate a sequence of strings with the following properties:

Lexically ordered
Theoretically infinite
Compact over a realistic range
Generated by a simple process of incrementation
Matches the regexp /\w+/

The obvious way to generate a lexically-ordered sequence is to choose a string length and pad the strings with a base value like this: 000000, 000001, etc. This approach poses a trade-off between the number of permutations and compactness: a string long enough to yield many permutations will be filled many zeros along the way. Plus, the length I choose sets an upper bound on the total number of permutations unless I have some mechanism for expanding the string when it maxes out.

So I came up with a sequence that works like this:

Each string consists of a "head", which is a base-36 number, followed by an underscore, and then the "tail", which is also a base-36 number padded by an increasing number of zeros
The first cycle goes from 0_0 to 0_z
The second cycle goes from 1_00 to 1_zz
The third cycle goes from 2_000 to 2_zzz, and so on
Once the head has reached z and the tail consists of 36 zs, the first "supercycle" has ended. Now the whole sequence starts over, except the z remains at the beginning, so the new cycle starts with z0_0, then continues to z1_00, and so on
The second supercycle goes zz0_0, zz1_00, and so on

Although the string of zs in the head could become unwieldy over the long run, a single supercycle contains over 10^56 permutations, which is far more than I ever expect to use. The sequence is theoretically infinite but very compact within a realistic range. For instance, the trillionth permutation is a succinct 7_bqd55h8s.

I can generate the sequence relatively simply with this javascript function:

function genStr (n) {
  n = BigInt(n);
  let prefix = "",
      cycle = 0n,
      max = 36n ** (cycle + 1n);
  while (n >= max) {
    n -= max;
    if (cycle === 35n) {
      prefix += "z";
      cycle = 0n;
    } else {
      cycle++;
    }
    max = 36n ** (cycle + 1n);
  }
  return prefix
         + cycle.toString(36)
         + "_"
         + n.toString(36).padStart(Number(cycle) + 1, 0);
}

The n parameter is a number that I increment and pass to the function to get the next member of the sequence. All I need to keep track of is a simple integer, making the sequence very easy to use.

So obviously I spent a lot of time on this and I think it's pretty good, but I'm wondering if there is a better way. Is there a good algorithm for generating a sequence along the lines of the one I'm looking for?

grodzi · Accepted Answer

A close idea to yours. (more rafined than my first edit...).

Let our alphabet be A = {0,1,2,3}.

Let |2| mean we iterate from 0 to 2 and |2|^2 mean we generate the cartesian product in a lexically sorted manner (00,01,10,11).

We start with

0 |3|

So we have a string of length 2. We "unshift" the digit 1 which "factorizes" since any 0|3|... is less than 1|3|^2.

1 |3|^2

Same idea: unshift 2, and make words of length 4.

2 |3|^3

Now we can continue and generate

3 |2| |3|^3

Notice |2| and not |3|. Now our maximum number becomes 32333. And as you did, we can now add the carry and start a new supercycle:

33 0|3|

This is a slight improvement, since _ can now be part of our alphabet: we don't need to reserve it as a token separator.

In our case we can represent in a supercycle:

n + n^2 + ... + n^(n-1) + (n-1) * n^(n-1)
\-----------------------/\--------------/
  geometric                special

In your case, the special part would be n^n (with the nuance that you have theorically one char less so replace n with n-1 everywhere)

The proposed supercycle is of length :

P = (n \sum_{k = 0}^{n-2} n^k) + (n-1) * n^(n-1) 
P = (n \sum_{k = 0}^{n-3} n^k) + n^n
P = n(n^{n-2} - 1)/(n-1) + n^n

Here is an example diff with alphabet A={0,1,2}

my  genStr(grandinero)
,00 0_0                 
,01 0_1                 
,02 0_2                 
,100 1_00               
,101 1_01               
,102 1_02               
,110 1_10               
,111 1_11               
,112 1_12               
,120 1_20               
,121 1_21               
,122 1_22               
,2000 2_000     
,2001 2_001     
,2002 2_002     
,2010 2_010     
,2011 2_011     
,2012 2_012     
,2020 2_020     
,2021 2_021     
,2022 2_022     
,2100 2_100     
,2101 2_101     
,2102 2_102     
,2110 2_110     
,2111 2_111     
,2112 2_112     
,2120 2_120     
,2121 2_121     
,2122 2_122     
22,00 2_200 <-- end of my supercycle if no '_' allowed
22,01 2_201     
22,02 2_202     
22,100 2_210     
22,101 2_211     
22,102 2_212     
22,110 2_220     
22,111 2_221     
22,112 2_222 <-- end of yours    
22,120 z0_0

That said, for a given number x, we can can count how many supercycles (E(x / P)) there are, each supercycle making two leading e (e being the last char of A). e.g: A = {0,1,2} and x = 43

e = 2
P = n(n^{n-2} - 1)/(n-1) + n^n = 3(3^1 -1)/2 + 27 = 30
// our supercycle is of length 30
E(43/30) = 1 // 43 makes one supercycle and a few more "strings"
r = x % P = 13 // this is also x - (E(43/30) * 30) (the rest of the euclidean division by P)

Then for the left over (r = x % P) two cases to consider:

either we fall in the geometric sequence
either we fall in the (n-1) * n^(n-1) part.

1. Adressing the geometric sequence with cumulative sums (`x < S_w`)

Let S_i be the cumsum of n, n^2,..

S_i = n\sum_{k = 0}^{i-1} n^k
S_i = n/(n-1)*(n^i - 1)

which gives S_0 = 0, S_1 = n, S_2 = n + n^2...

So basically, if x < S_1, we get 0(x), elif x < S_2, we get 1(x-S_1)

Let S_w = S_{n-1} the count of all the numbers we can represent.

If x <= S_w then we want the i such that S_i < x <= S_{i+1} <=> n^i < (n-1)/n * x + 1 <= n^{i+1}

We can then apply some log flooring (base(n)) to get that i.

We can then associate the string: A[i] + base_n(x - S_i).

Illustration:

This time with A = {0,1,2,3}.

Let x be 17.

Our consecutive S_i are:

S_0 = 0
S_1 = 4
S_2 = S_1 + 4^2 = 20
S_3 = S_2 + 4^3 = 84
S_w = S_{4-1} = S_3 = 84

x=17 is indeed less than 84, we will be able to affect it to one of the S_i ranges. In particular S_1==4 < x==17 <= S_2==20.

We remove the strings encoded by the leading 0(there are a number S_1 of those strings).

The position to encode with the leading 1 is x - 4 = 13.

And we conclude the thirteen's string generated with a leading 1 is base_4(13) = '31' (idem string -> '131')

Should we have had x = 21, we would have removed the count of S_2 so 21-20 = 1, which in turn gives with a leading 2 the string '2001'.

2. Adressing x in the special part (`x >= S_w`)

Let's consider study case below:

with A = {0,1,2} The special part is

2 |1| |2|^2 that is:

Each incremented number of the second column (here 0 to 1 (specified from |1|)) gives 3^2 combination.

This is similar to the geometric series except that here each range is constant. We want to find the range which means we know which string to prefix.

We can represent it as the matrix

20 (00,01,02,10,11,12,20,21,22)
21 (00,01,02,10,11,12,20,21,22)

The portion in parenthesis is our matrix.

Every item in a row is simply its position base_3 (left-padded with 0).

e.g: n=7 has base_3 value '21'. (7=2*3+1). '21' does occur in position 7 in the row.

Assuming we get some x (relative to that special part).

E(x / 3^2) gives us the row number (here E(7/9) = 0 so prefix is '20')
x % 3^2 give us the position in the row (here base_3(7%9)='21' giving us the final string '2021')

If we want to observe it remember that we substracted S_w=12 before to get x = 7, so we would call myGen(7+12)

Some code

Notice the same output as long as we stand in the "geometric" range, without supercycle.
Obviously, when carry starts to appear, it depends on whether I can use '_' or not. If yes, my words get shorter otherwise longer.

// https://www.cs.sfu.ca/~ggbaker/zju/math/int-alg.html
// \w insensitive could give base64
// but also éè and other accents...
function base_n(x, n, A) {
  const a = []
  while (x !== 0n) {
    a.push(A[Number(x % n)])
    x = x / n // auto floor with bigInt
  }
  return a.reverse().join('')
}

function mygen (A) {
  const n = A.length
  const bn = BigInt(n)

  const A_last = A[A.length-1]
  const S = Array(n).fill(0).map((x, i) => bn * (bn ** BigInt(i) - 1n) / (bn - 1n))
  const S_w = S[n-1]

  const w = S_w + (bn - 1n) * bn ** (bn - 1n)
  const w2 = bn ** (bn - 1n)
  const flog_bn = x => {
    // https://math.stackexchange.com/questions/1627914/smart-way-to-calculate-floorlogx
    let L = 0
    while (x >= bn) {
      L++
      x /= bn
    }
    return L
  }
  return function (x) {

    x = BigInt(x)
    let r = x % w
    const q = (x - r) / w
    let s
    if (r < S_w) {
      const i = flog_bn(r * (bn - 1n) / bn + 1n)
      const r2 = r - S[i]
      s = A[i] + base_n(r2, bn, A).padStart(i+1, '0')
    } else {
      const n2 = r - S_w
      const r2 = n2 % w2
      const q2 = (n2 - r2 ) / w2
      s = A_last + A[q2] + base_n(r2, bn, A).padStart(n-1, '0')
    }
    // comma below __not__ necessary, just to ease seeing cycles
    return A_last.repeat(2*Number(q)) +','+ s 
  }
}

function genStr (A) {
  A = A.filter(x => x !== '_')
  const bn_noUnderscore = BigInt(A.length)
  return function (x) {
    x = BigInt(x);
    let prefix = "",
        cycle = 0n,
        max = bn_noUnderscore ** (cycle + 1n);
    while (x >= max) {
      x -= max;
      if (cycle === bn_noUnderscore - 1n) {
        prefix += "z";
        cycle = 0n;
      } else {
        cycle++;
      }
      max = bn_noUnderscore ** (cycle + 1n);
    }
    return prefix
           + base_n(cycle, bn_noUnderscore, A)
           + "_"
           + base_n(x, bn_noUnderscore, A).padStart(Number(cycle) + 1, 0);    
  }
}
function test(a, b, x){
  console.log(a(x), b(x))
}
{
  console.log('---my supercycle is shorter if underscore not used. Plenty of room for grandinero')
  const A = '0123456789abcdefghijklmnopqrstuvwxyz'.split('').sort((a,b)=>a.localeCompare(b))
  let my = mygen(A)
  const grandinero = genStr(A)
  test(my, grandinero, 1e4)
  test(my, grandinero, 1e12)
  test(my, grandinero, 106471793335560744271846581685593263893929893610517909620n) // cycle ended for me (w variable value)
}
{
  console.log('---
 my supercycle is greater if underscore is used in my alphabet (not grandinero since "forbidden')
  // underscore used
  const A = '0123456789abcdefghijklmnopqrstuvwxyz_'.split('').sort((a,b)=>a.localeCompare(b))
  let my = mygen(A)
  const grandinero = genStr(A)
  test(my, grandinero, 1e12)
  test(my, grandinero, 106471793335560744271846581685593263893929893610517909620n) // cycle ended for me (w variable value)
  test(my, grandinero, 1e57) // still got some place in the supercycle
}

Compact way to produce a large sequence of strings in lexical order

Answers (2)

1. Adressing the geometric sequence with cumulative sums (`x < S_w`)

2. Adressing x in the special part (`x >= S_w`)

Some code

Related Questions

Compact way to produce a large sequence of strings in lexical order

Answers (2)

1. Adressing the geometric sequence with cumulative sums (x < S_w)

2. Adressing x in the special part (x >= S_w)

Some code

Related Questions

1. Adressing the geometric sequence with cumulative sums (`x < S_w`)

2. Adressing x in the special part (`x >= S_w`)