Близкая к вам идея. (более детализировано, чем мое первое редактирование ...).
Пусть наш алфавит будет A = {0,1,2,3}.
Пусть |2| означает, что мы повторяем от 0 до 2, а |2|^2 означает, что мы генерируем декартово произведение лексически отсортированным образом (00,01,10,11).
Мы начинаем с
0 |3|
Итак, у нас есть строка длины 2. Мы "смещаем" di git 1, который "разлагается на множители", поскольку любое значение 0|3|... меньше 1|3|^2.
1 |3|^2
Та же идея: отмените сдвиг 2 и создайте слова длиной 4.
2 |3|^3
Теперь мы можем продолжить и генерировать
3 |2| |3|^3
Уведомление |2|, а не |3|. Теперь наше максимальное число становится 32333. И как вы сделали, теперь мы можем добавить перенос и начать новый суперцикл:
33 0|3|
Это небольшое улучшение, поскольку _ теперь может быть частью нашего алфавита: нам не нужно зарезервируйте его как разделитель токенов.
В нашем случае мы можем представить в суперцикле:
n + n^2 + ... + n^(n-1) + (n-1) * n^(n-1)
\-----------------------/\--------------/
geometric special
В вашем случае особой частью будет n^n (с нюансом, который вы теоретически на один символ меньше, поэтому замените n на n-1 везде)
Предполагаемый суперцикл имеет длину:
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
Вот пример diff с алфавитом 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
Тем не менее, для данного числа x мы можем подсчитать, сколько существует суперциклов (E(x / P)), каждый суперцикл делает два ведущих e (* 1051) * будучи последним символом A). Например: A = {0,1,2} и 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)
Затем для оставшихся (r = x % P) два случая для рассмотрения:
- либо мы попадаем в геометрию c sequence
- либо мы попадаем в
(n-1) * n^(n-1) part.
1. Обращаясь к геометрии c последовательности с кумулятивными суммами (x < S_w)
Пусть S_i будет суммой n, n^2,..
S_i = n\sum_{k = 0}^{i-1} n^k
S_i = n/(n-1)*(n^i - 1)
, что дает S_0 = 0, S_1 = n, S_2 = n + n^2...
Так что, в принципе, если x < S_1, мы получим 0(x), elif x < S_2, мы получим 1(x-S_1)
Пусть S_w = S_{n-1} подсчитает все числа, которые мы можем представить.
Если x <= S_w, то мы хотим, чтобы i было таким, чтобы S_i < x <= S_{i+1} <=> n^i < (n-1)/n * x + 1 <= n^{i+1}
Затем мы могли бы применить некоторые настилы бревен (основание (n)), чтобы получить это i.
Мы можем затем свяжите строку: A[i] + base_n(x - S_i).
Иллюстрация:
На этот раз с A = {0,1,2,3}.
Пусть x будет 17.
Наши последовательные S_i:
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 действительно меньше, чем 84, мы сможем повлиять на один из диапазонов S_i. В частности S_1==4 < x==17 <= S_2==20.
Мы удаляем строки, закодированные лидирующим 0 (есть число S_1 этих строк).
Позиция для кодирования с лидирующей 1 - x - 4 = 13.
И мы заключаем, что строка тринадцати, сгенерированная с первым 1, равна base_4(13) = '31' (idem string -> '131')
Если бы у нас было x = 21, мы бы получили убрал счетчик S_2, то есть 21-20 = 1, что, в свою очередь, дает с лидирующей 2 строку '2001'.
2. Адресация x в специальной части (x >= S_w)
Рассмотрим пример для изучения ниже:
с A = {0,1,2} Специальная часть -
2 |1| |2|^2, то есть:
2 0 00
2 0 01
2 0 02
2 0 10
2 0 11
2 0 12
2 0 20
2 0 21
2 0 22
2 1 20
2 1 21
2 1 22
2 1 10
2 1 11
2 1 12
2 1 20
2 1 21
2 1 22
Каждое увеличенное число второго столбца (здесь 0 до 1 (задано от |1|)) дает комбинацию 3^2.
Это похоже на геометрию c серии за исключением того, что здесь каждый диапазон постоянен. Мы хотим найти диапазон, который означает, что мы знаем, какую строку ставить перед префиксом.
Мы можем представить ее в виде матрицы
20 (00,01,02,10,11,12,20,21,22)
21 (00,01,02,10,11,12,20,21,22)
Часть в скобках - это наша матрица.
Каждый элемент в строке - это просто его позиция base_3 (дополненная слева 0).
Например: n=7 имеет значение base_3 '21'. (7=2*3+1). '21' встречается в позиции 7 в строке.
Предполагая, что мы получаем x (относительно этой специальной части).
E(x / 3^2) дает нам номер строки (здесь E(7/9) = 0 таким образом, префикс '20') x % 3^2 дает нам позицию в строке (здесь base_3(7%9)='21' дает нам окончательную строку '2021')
Если мы хотим наблюдать это, помните, что мы вычли S_w=12 прежде, чем получить x = 7, поэтому мы бы назвали myGen(7+12)
Некоторый код
-
Обратите внимание на один и тот же вывод, пока мы находимся в диапазоне "geometryri c", без суперцикла.
Очевидно, когда начинает появляться перенос, это зависит от того, можно использовать «_» или нет. Если да, мои слова становятся короче, иначе - дольше.
// 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('---\n 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
}