Standard Positional to Bijective Base Conversion

Question

We know that a b-based standard positional number system uses digits, 0, 1, 2, ..., b-1. But a bijective number system uses digits, 1, 2, ..., b. So a 4-based standard number system sequence looks like,

0
1
2
3
10
11
12
13
20
21
22
23
30
31
32
33 (base-4, 16th number standard)
100 (base-4, 17th number standard)
101
.
.
.

On the other hand bijective number system for 4-based looks like,

λ (base-4, 1st number, empty-string)
1
2
3
4
11
12
13
14
21
22
23
24
31
32
33 (base-4, 16th number bijective)
34 (base-4, 17th number bijective)
41 
.
.
.

Example:

34152 (in bijective base-5) = 3×54 + 4×53 + 1×52 + 5×51 + 2×1 = 2427 (in decimal). 119A (in bijective base-10, with "A" representing the digit value ten) = 1×103 + 1×102 + 9×101 + 10×1 = 1200 (in decimal).

I wonder if there is any easy way to find n'th position bijective value in same base.

For example,

lets say in base-4 5th positional value = 10 (standard) but 5th positional value = 11 (bijective). Any pseudocode is ok to understand the concept.

Answer 1

This routine implements the conversion. (Which resolved to @4386427's method.) If you want the other version, where 100 (base 4 std) -> 41 (base 4 bij') then compile with -D NO_EMPTY_STRING

#include <stdio.h>
#include <string.h>
void print_be_digits(const char *prefix, const unsigned char *le_num, size_t len)
{
  size_t i;
  printf("%s", prefix);
  for(i=0; i<len; i++)
  {
    printf("%d ", (int)le_num[len-i-1]);
  }
  printf("\n");
}

void nth_bij(int n, int k)
{
  ssize_t i;
  size_t std_len;
  size_t bij_len;
  size_t work;
  unsigned char le_std_digits[256];
  unsigned char le_bij_digits[256];

  //convert to standard radix-k digits
  work = n;
  for(std_len = 0; work; std_len++)
  {
    le_std_digits[std_len] = work % k;
    work /= k;
  }

  print_be_digits("  std: ", le_std_digits, std_len);

  //convert standard to bij
  memcpy(le_bij_digits, le_std_digits, std_len);
  bij_len = std_len;

  #ifdef NO_EMPTY_STRING
  // Step 1: increment LSd
  le_bij_digits[0]++;
  #endif

  // Step 2: borrow on zeros
  // scan back from the end
  for(i=bij_len-1; i>= 0; i--)
  {
    //if we find a zero, borrow, and ripple toward MSd as necessary
    if(le_bij_digits[i] == 0)
    {
      size_t j;

      //Ripple borrow toward MSd, as necessary
      for(j=i+1; j<bij_len; j++)
      {
        le_bij_digits[j-1] = k; //k is the radix

        if(--le_bij_digits[j])
        {
          break;
        }
      }//end ripple

      //adjust bij_len if we rippled to the end
      if(j == bij_len)
      {
        bij_len--;
      }
    }
  }//end scan
  print_be_digits("  bij: ", le_bij_digits, bij_len);
}

Simple driver:

int main(int argc, char *argv[])
{
  printf("Test: 16 decimal (->base 4): \n");
  nth_bij(16,4);
  printf("\n");

  printf("Test: 8 decimal (->base 2): \n");
  nth_bij(8,2);
  printf("\n");

  printf("Test: 13 decimal (->base 2): \n");
  nth_bij(13,2);
  printf("\n");

  printf("Test: 2427 decimal (->base 5): \n");
  nth_bij(2427, 5);
  printf("\n");

  printf("Test: 1200 decimal (->base 10): \n");
  nth_bij(1200, 10);
  printf("\n");
}

Compiling for my version:

$ gcc -D NO_EMPTY_STRING bij.c
$ ./a.exe
Test: 16 decimal (->base 4):
  std: 1 0 0
  bij: 4 1

Test: 8 decimal (->base 2):
  std: 1 0 0 0
  bij: 1 2 1

Test: 13 decimal (->base 2):
  std: 1 1 0 1
  bij: 2 2 2

Test: 2427 decimal (->base 5):
  std: 3 4 2 0 2
  bij: 3 4 1 5 3

Test: 1200 decimal (->base 10):
  std: 1 2 0 0
  bij: 1 1 10 1

Compiling for @4386427's version:

$ gcc bij.c
$ ./a.exe
Test: 16 decimal (->base 4):
  std: 1 0 0
  bij: 3 4

Test: 8 decimal (->base 2):
  std: 1 0 0 0
  bij: 1 1 2

Test: 13 decimal (->base 2):
  std: 1 1 0 1
  bij: 2 2 1

Test: 2427 decimal (->base 5):
  std: 3 4 2 0 2
  bij: 3 4 1 5 2

Test: 1200 decimal (->base 10):
  std: 1 2 0 0
  bij: 1 1 9 10