title: Compact way to produce a large sequence of strings in lexical order
body: <p>I want to generate a sequence of strings with the following properties:</p>
  
  <ol>
  <li>Lexically ordered</li>
  <li>Theoretically infinite</li>
  <li>Compact over a realistic range</li>
  <li>Generated by a simple process of incrementation</li>
  <li>Matches the regexp <code>/\w+/</code></li>
  </ol>
  
  <p>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: <code>000000</code>, <code>000001</code>, 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.</p>
  
  <p>So I came up with a sequence that works like this:</p>
  
  <ol>
  <li>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</li>
  <li>The first cycle goes from <code>0_0</code> to <code>0_z</code></li>
  <li>The second cycle goes from <code>1_00</code> to <code>1_zz</code></li>
  <li>The third cycle goes from <code>2_000</code> to <code>2_zzz</code>, and so on</li>
  <li>Once the head has reached <code>z</code> and the tail consists of 36 <code>z</code>s, the first "supercycle" has ended. Now the whole sequence starts over, except the <code>z</code> remains at the beginning, so the new cycle starts with <code>z0_0</code>, then continues to <code>z1_00</code>, and so on</li>
  <li>The second supercycle goes <code>zz0_0</code>, <code>zz1_00</code>, and so on</li>
  </ol>
  
  <p>Although the string of <code>z</code>s 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 <code>7_bqd55h8s</code>.</p>
  
  <p>I can generate the sequence relatively simply with this javascript function:</p>
  
  <pre class="lang-js prettyprint-override"><code>function genStr (n) {
    n = BigInt(n);
    let prefix = "",
        cycle = 0n,
        max = 36n ** (cycle + 1n);
    while (n &gt;= 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);
  }
  </code></pre>
  
  <p>The <code>n</code> 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.</p>
  
  <p>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?</p>