2

Although this question already has partial answers on StackOverflow, those answers are not associated with questions that have the proper name of the process / concept (bijective (base-k) numeration) in the title or among the tags. I anticipate that many answers will essentially be links to those existing answers.

This question is partially answered in How to list from A to Z in PHP, and then on to AA, AB, AC, etc

Bijective base-26 numeration can be used to compute column ID's in the scheme used in many spreadsheet programs, such as LibreOffice Calc, Lotus-123, VisiCalc(I think), ProCalc 3D, and others.

The following is R pseudocode (I'm not yet including the "raw" R code for the dependencies) for one solution. The return is an integer vector (little endian) whose elements are conceptually mapped to the arbitrary symbols used for the representation of the bijective numeration:

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"
Ana Nimbus
  • 635
  • 3
  • 16
  • I agree with the several related questions / answers not referencing the concept properly, but what are you exactly asking here? You seem to already have a working piece of code. Is it about efficiency? If so how efficient a solution are you looking for? – desseim May 08 '22 at 18:01
  • Well, in my pseudocode, I use a logarithm to estimate how many places are needed for the result. The example provided by @Cosine uses string, which I'm guessing (not super familiar with Javascript) is dynamically allocated or over-allocated. Seems like there are some opportunities for trading off a little storage for some speed. Maybe always allocate enough space for the base-2 case? I wonder if those spreadsheet programs use a precalculated lookup table. One source reports VisiCalc had 63 columns, which would not be too bad for a look-up table, even in the late '70's (about 128 bytes). – Ana Nimbus May 08 '22 at 21:02
  • I was pointing out that I think the question would benefit (and potentially get more answers) from being more focused and making clear what particular, single problem you're trying to solve. – desseim May 10 '22 at 15:24

1 Answers1

1

i don't know R, but in case it helps, this is the implementation of bijective numeration that i just wrote in 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();
}
Cosine
  • 572
  • 4
  • 18