Как эффективно вычислить биективное число с основанием k (и/или обратное ему) в R или любом другом свободно доступном языке программирования?

Хотя на этот вопрос уже есть частичные ответы в StackOverflow, эти ответы не связаны с вопросами, имеющими правильное название процесса/концепции (биективная нумерация (с основанием k)) в заголовке или среди тегов. Я ожидаю, что многие ответы будут по сути ссылками на эти существующие ответы.

На этот вопрос частично дан ответ в Как составить список от А до Я в PHP, а затем перейти к AA, AB, AC и т. д.

Биективная нумерация с основанием 26 может использоваться для вычисления идентификаторов столбцов в схеме, используемой во многих программах для работы с электронными таблицами, таких как LibreOffice Calc, Lotus-123, VisiCalc(кажется), ProCalc 3D и другие.

Ниже приведен псевдокод R (я пока не включаю "сырой" код R для зависимостей) для одного решения. Возврат представляет собой целочисленный вектор (с прямым порядком байтов), элементы которого концептуально сопоставляются с произвольными символами, используемыми для представления биективной нумерации:

bijective.numeral <- function(n, symbols=26L) {
    if (!is_among.contiguous.integers(n)) return (NULL)
    if (n  < 0) return(iNA)
    if (n == 0) return(integer())
    intermediate <- pseudo.log(n, symbols) %|% integer
            # PREALLOCATE A VECTOR LONG ENOUGH FOR THE RESULT
    m <- 0L
    while (n) {
        m <- 1L + m
        intermediate[[m]] <- 1:symbols %[mod% n
        n <- n %|% pred %/% symbols }
    intermediate[1:m] }

LETTERS[16384 %|% bijective.numeral] %|% rev %|% `%//%`

# [1] "XFD"

numbers symbols enumeration representation bijection
person Ana Nimbus    schedule 03.02.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

я не знаю R, но если это поможет, это реализация биективной нумерации, которую я только что написал в javascript:

function bijectiveString(m, k) {
  if (m == 0) {
      return [];
  }
  let string = [];
  function f(x) {
    return Math.ceil(x) - 1;
  }
  let qn = f(m / k); // q0
  string.push(m - qn * k); // a0
  while (qn != 0) {
    let qnInc = f(qn / k);
    let anInc = qn - qnInc*k;
    string.push(anInc);
    qn = qnInc;
  }
  return string.reverse();
}
person Cosine    schedule 18.03.2020