Отображение целых чисел в строки в заданном строковом пространстве

Question

Предположим, у меня есть алфавит 'abcd' и максимальная длина строки 3. Это дает мне 85 возможных строк , включая пустую строку.То, что я хотел бы сделать, это отобразить целое число в диапазоне [0,85) на строку в моем строковом пространстве без использования таблицы поиска.Примерно так:

0 => ''
1 => 'a'
...
4 => 'd'
5 => 'aa'
6 => 'ab'
...
84 => 'ddd'

Это достаточно просто сделать, если строка фиксированной длины, используя этот алгоритм псевдокода:

str = ''
for i in 0..maxLen do
    str += alphabet[i % alphabet.length]
    i /= alphabet.length
done

Я не могу найти хороший, эффективный способделать это, хотя, когда длина строки может быть где-нибудь в диапазоне [0,3).Это будет работать в узком цикле со случайными входами, поэтому я бы хотел избежать ненужных переходов или поисков.

Answer 1

Сдвиньте свой индекс на единицу и временно игнорируйте пустую строку.Таким образом, вы бы отобразили 0 -> "a", ..., 83 -> "ddd".

Тогда отображение будет

n -> base-4-encode(n - number of shorter strings)

С 26 символами, это схема нумерации столбцов Excel.

С s символов, есть s + s^2 + ... + s^l непустых строк длиной не более l.Оставляя в стороне тривиальный случай s = 1, эта сумма (частичная сумма геометрического ряда) s*(s^l - 1)/(s-1).

Итак, при заданном n найдите наибольшее l такое, что s*(s^l - 1)/(s-1) <= n,то есть

l = floor(log((s-1)*n/s + 1) / log(s))

Затем позвольте m = n - s*(s^l - 1)/(s-1) и закодируйте m в виде l+1 -символьной строки в базе s ('a' ~> 0, 'b' ~> 1, ...).

Для задачи, включающей пустую строку, сопоставьте 0 с пустой строкой и для n > 0 кодируйте n-1, как указано выше.

Answer 2

В Haskell

encode cs n = reverse $ encode' n where
  len = length cs
  encode' 0 = ""
  encode' n = (cs !! ((n-1) `mod` len)) : encode' ((n-1) `div` len)

Проверка:

* Main> map (кодировка "abcd") [0..84] ["", "a", "б»,„в“,„г“,„аа“,„б“,„ас“,„объявление“,„ба“,„бб“,„БК“,„шд“,„са“,„Си-Би“, "CC", "CD", "да", "DB", "DC", "дд", "ааа", "AAB", "ААС", "КИР", "АВА", "АВВ",»а», "абд", "АС", "ACB", "АСС", "ДС", "Ад", "ADB", "АДЦ", "добавить", "б", "бабам", "БАК", "плохо", "ВВ", "БББ", "Би-би", "BBD", "ДСС", "БКБ", "BCC", "BCD", "АРП", "BDB", "НМТ",»БДД», "САК", "кабина", "сас", "подлец", "СВА", "CBB", "CBC", "КБР", "ССА", "БКК", "ссс", "БДД""CDA", "СБК", "ЦКЗ", "РИО", "даа", "тыкать", "КОР", "папа", "DBA", "DBB", "СНД", "DBD",»dca "," dcb "," dcc "," dcd "," dda "," ddb "," ddc "," ddd "]

Answer 3

Вот решение C #:

    static string F(int x, int alphabetSize)
    {
        string ret = "";
        while (x > 0)
        {
            x--;
            ret = (char)('a' + (x % alphabetSize)) + ret;
            x /= alphabetSize;
        }

        return ret;
    }

Если вы хотите оптимизировать это дальше, вы можете сделать что-то, чтобы избежать конкатенации строк. Например, вы можете сохранить результат в предварительно выделенном массиве char [].

Answer 4

Определите количество строк для каждой длины: N0, N1, N2 и N3 (на самом деле вам не понадобится N3). Затем используйте эти значения для разбиения пространства целых чисел: 0..N0-1 имеют длину 0, N0..N0 + N1-1 имеют длину 1 и т. Д. В каждом разделе вы можете использовать свой алгоритм фиксированной длины.

В худшем случае вы значительно уменьшили размер таблицы поиска.