Представляем целые числа по d-цифрам с использованием наименьшей возможной базы

Question

Я хотел бы создать функцию, где для произвольного целочисленного входного значения (скажем, без знака 32 бит) и заданного числа d цифры возвращают значение d digit B базовый номер, B является наименьшей базой, которая может использоваться для представления заданного ввода на d цифр.

Вот входной пример - вывод о том, что я имею в виду 3 цифры:

Input Output 

    0  0 0 0 
    1  0 0 1 
    2  0 1 0 
    3  0 1 1 
    4  1 0 0 
    5  1 0 1 
    6  1 1 0 
    7  1 1 1 

    8  0 0 2 
    9  0 1 2 
    10  1 0 2 
    11  1 1 2 
    12  0 2 0 
    13  0 2 1 
    14  1 2 0 
    15  1 2 1 
    16  2 0 0 
    17  2 0 1 
    18  2 1 0 
    19  2 1 1 
    20  0 2 2 
    21  1 2 2 
    22  2 0 2 
    23  2 1 2 
    24  2 2 0 
    25  2 2 1 
    26  2 2 2 

    27  0 0 3 
    28  0 1 3 
    29  1 0 3 
    30  1 1 3 
    ..  ..... 

Назначение должно быть 1: 1, для каждого входного значения должно быть ровно один, уникальное значение выходной. Подумайте об этом, как будто функция должна вернуть значение nth из списка странно отсортированных базовых чисел B.

На самом деле это единственный подход, который я мог придумать до сих пор с - с учетом входного значения, порождают все числа в наименьшей возможной B основанием для представления входных данных на d цифр, а затем применить пользовательскую сортировку результатов («наказывая» значения более высоких цифр и помещая их обратно в сортировку) и возвращает значение nth из отсортированного массива. Это будет работать, но это впечатляюще неэффективная реализация - я бы хотел сделать это, не генерируя все числа до входного значения.

Что было бы эффективным подходом для реализации этой функции? Любой язык или псевдокод в порядке.

Answer 1

Ответ МБО показывает, как найти наименьшую базу, которая будет представлять собой целое число с заданным количеством цифр.

Я не совсем уверен в заказе в вашем примере. Мой ответ основан на другом порядке: Создайте все возможные n -digit номера до основания b (например, все номера до 999 для максимальной базы 10 и 3 цифры). Сначала сортируйте их по их максимальной цифре. Числа сортируются по норме в группе с одинаковой максимальной цифрой.Это сохраняет характеристики, что все значения от 8 до 26 должно быть основание 3, но внутреннее упорядочение отличается:

8  0 0 2 
    9  0 1 2 
10  0 2 0 
11  0 2 1 
12  0 2 2 
13  1 0 2 
14  1 1 2 
15  1 2 0 
16  1 2 1 
17  1 2 2 
18  2 0 0 
19  2 0 1 
20  2 0 2 
21  2 1 0 
22  2 1 1 
23  2 1 2 
24  2 2 0 
25  2 2 1 
26  2 2 2 

Когда база две, жизнь просто: генерировать соответствующий двоичный номер.

Для других баз давайте посмотрим на первую цифру. В приведенном выше примере пять чисел начинаются с 0, пять начинается с 1 и девяти начинается с 2. Когда первая цифра равна 2, максимальная цифра должна быть равна 2. Поэтому мы можем комбинировать 2 с 9 двузначными числами базы 3.

Когда первая цифра меньше максимальной цифры в группе, мы можем объединить ее с 9 двузначными числами базы 3, но мы не должны использовать 4 двузначных числа, которые являются неоднозначный с 4 двузначными числами базы 2. Это дает нам пять возможностей для цифр 0 и 1. Эти возможности – 02, 12, 20, 21 и 22 – могут быть описаны как уникальные номера с двумя цифрами в соответствии с та же схема, но со смещением:

4  0 2 
5  1 2 
6  2 0 
7  2 1 
8  2 2 

Это приводит к рекурсивному решению:

• для одной цифры, просто вернуть сам номер;
• для основания два, возвратите прямое представление в основании 2;
• , если первое число является максимальной цифрой для определенной базы, объедините ее с представлениями о несвязности в этой базе;
• в противном случае объединить его с рекурсивно определенным представлением того же алгоритма с одним меньшим числом.

Вот пример в Python. Представление возвращается как список чисел, так что вы можете представить 2^32 − 1 как [307, 1290, 990].

import math 

def repres(x, ndigit, base): 
    """Straightforward representation of x in given base""" 

    s = [] 

    while ndigit: 
     s += [x % base] 
     x /= base 
     ndigit -= 1 

    return s 



def encode(x, ndigit): 
    """Encode according to min-base, fixed-digit order""" 

    if ndigit <= 1: 
     return [x] 

    base = int(x ** (1.0/ndigit)) + 1 

    if base <= 2: 
     return repres(x, ndigit, 2) 

    x0 = (base - 1) ** ndigit 
    nprev = (base - 1) ** (ndigit - 1) 
    ncurr = base ** (ndigit - 1) 
    ndiff = ncurr - nprev 

    area = (x - x0)/ndiff 

    if area < base - 1: 
     xx = x0/(base - 1) + x - x0 - area * ndiff 
     return [area] + encode(xx, ndigit - 1) 

    xx0 = x0 + (base - 1) * ndiff 
    return [base - 1] + repres(x - xx0, ndigit - 1, base) 



for x in range(32): 
    r = encode(x, 3) 
    print x, r 

Answer 2

Предполагая, что все значения положительны, давайте сделаем простую математику:
d-значный B на основе номер может содержать значение N, если

B ^d> N

так

B > N ^1/d

Таким образом, рассчитать N ^1/d значение, округлое его вверх (приращение, если целое число), и вы получите самую маленькую базу В.
(обратите внимание, что может произойти численные ошибки)

Примеры:

d=2, N=99 => 9.95 => B=10 
d=2, N=100 => 10 => B=11 
d=2, N=57 => 7.55 => B=8 
d=2, N=33 => 5.74 => B=6 

Delphi код

function GetInSmallestBase(N, d: UInt32): string; 
    const 
    Digits = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; 
    var 
    Base, i: Byte; 
    begin 
    Base := Ceil(Power(N, 1/d) + 1.0E-12); 
    if Base > 36 then 
     Exit('Big number, few digits...'); 
    SetLength(Result, d); 
    for i := d downto 1 do begin 
     Result[i] := Digits[1 + N mod Base]; //Delphi string is 1-based 
     N := N div Base; 
    end; 
    Result := Result + Format(' : base [%d]', [Base]); 
    end; 

begin 
    Memo1.Lines.Add(GetInSmallestBase(99, 2)); 
    Memo1.Lines.Add(GetInSmallestBase(100, 2)); 
    Memo1.Lines.Add(GetInSmallestBase(987, 2)); 
    Memo1.Lines.Add(GetInSmallestBase(1987, 2)); 
    Memo1.Lines.Add(GetInSmallestBase(87654321, 6)); 
    Memo1.Lines.Add(GetInSmallestBase(57, 2)); 
    Memo1.Lines.Add(GetInSmallestBase(33, 2)); 

99 : base [10] 
91 : base [11] 
UR : base [32] 
Big number, few digits... 
H03LL7 : base [22] 
71 : base [8] 
53 : base [6]