1
$\begingroup$

Write $\{0,1\}^*$ denote the monoid freely generated by the set $\{0,1\}$. This can be viewed as an infinite binary tree. For example, $001$ would be the node "go left, go left, go right." The empty string is the root.

Suppose we wish to traverse the nodes in the manner suggested by the definition of a heap. Namely: $$\emptyset < 0 < 1<00<01<10<11<000<001<\cdots$$

This amounts to a bijection between $\mathbb{N} = \{0,1,2,3,\ldots\}$ and $\{0,1\}^*.$ For example, $3$ would be represented as $00$ in this notation. So, we've found a way of representing natural numbers as words in the letters $0$ and $1$. Lets call this representation "pseudobinary."

There's also a sensible notion of "pseudoternary", etc.

Pseudobinary is different from (ordinary) binary. In particular, recall that the ordinary binary number system is basically an injection $\mathbb{N} \rightarrow \{0,1\}^*$. The image of this map is all non-empty strings that either equal $0$ start with a $1$. Ergo, binary is an altogether different way of representing numbers as strings of $0$'s and $1$'s.

Binary is nice is because the standard arithmetical operations are very straightforward to implement. Pseudobinary is nice because the strings are slightly shorter, and it provides a sensible way of naming the nodes in the infinite tree $\{0,1\}^*$. Converting between them is easy enough, and you can use this to puzzle out how to do arithmetic with pseudobinary.

Anyway, while working with heaps and other such data structures, it would be nice to have a name for "pseudobinary" so as to help with the naming of functions. For example, when writing code that involves heaps, it's helpful to have names for the two functions $\mathbb{N} \rightarrow \{0,1\}^*$ of interest, like representInBinary and representInPseudobinary.

Question. What's pseudobinary and it's higher-$n$ variants really called?

$\endgroup$
  • $\begingroup$ It's possible that it's just not common enough to have a well-established canonical name. Call it what you want and be sure to explicitly describe it when you do. $\endgroup$ – NovaDenizen Oct 17 '17 at 3:41
  • $\begingroup$ See bijective base-$k$ numeration. $\endgroup$ – r.e.s. Oct 17 '17 at 3:42
  • $\begingroup$ @NovaDenizen, I think that in certain contexts, this is probably a very very very 'common' notation (to use your word). $\endgroup$ – goblin Oct 18 '17 at 1:29
  • 1
    $\begingroup$ Also pertinent: shortlex order. $\endgroup$ – MJD Oct 18 '17 at 2:01
  • $\begingroup$ @MJD, thanks! $\;\!$ $\endgroup$ – goblin Oct 18 '17 at 2:37
6
$\begingroup$

Your systems of "pseudobinary", "pseudoternary", etc., are variants of bijective base-$k$ numeration, which typically uses the digit set $\{1,...,k\}$, rather than $\{0,...,k-1\}$.

More generally, for any finite alphabet $\{\sigma_1,...,\sigma_k\}$ ordered such that $\sigma_1\prec\sigma_2\prec...\prec\sigma_k$, the following two lists are identical:

  1. A list of all finite words on $\{\sigma_1,...,\sigma_k\}$ in shortlex order (shortest first, lexicographical within each length): $\,\epsilon\prec\sigma_1\prec\,...\,\prec\sigma_k\prec\sigma_1\sigma_1\prec\,...\,\prec\sigma_k\sigma_k\prec\sigma_1\sigma_1\sigma_1\prec\,...\,\prec\sigma_k\sigma_k\sigma_k\prec\,...$

  2. A list of all bijective base-$k$ numerals in the natural order of the integers they represent when $\{\sigma_1,...,\sigma_k\}$ is taken as the digit set.

Thus, for $m>0$, the $m$th word in the shortlex ordering of $\{\sigma_1,...,\sigma_k\}^*$ is just $\sigma_{d_n}\sigma_{d_{n-1}}...\sigma_{d_0}$, where $d_nd_{n-1}...d_0$ is the bijective base-$k$ numeral for $m$ (i.e., the $d_i\in\{1,...,k\}$ are such that $m=\sum_{i=0}^n d_i\,k^i$).

Conversely, the number of predecessors of any given nonempty word, say $\sigma_{d_n}\sigma_{d_{n-1}}...\sigma_{d_0}$, in the shortlex ordering of $\{\sigma_1,...,\sigma_k\}^*$, is just $m=\sum_{i=0}^n d_i\,k^i$ (the empty string $\epsilon$ having $m=0$ predecessors).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.