Home > Back-end >  Algorithm to transform number into a string, based on available alphabet and considering minimum str
Algorithm to transform number into a string, based on available alphabet and considering minimum str

Time:09-03

I'm trying to figure out how to transform a number, into a string based on an available alphabet, and also considering a minimum string length.

For example:

Considering I have this alphabet: AB12 And that I define the minimum string length to be: 2

The number 1 would be = AA
The number 2 would be = AB
The number 3 would be = A1
The number 4 would be = A2
The number 5 would be = BA
The number 6 would be = BB
The number 7 would be = B1
The number 8 would be = B2
The number 9 would be = 1A
The number 10 would be = 1B
...
if I run out of combinations, string length should increase:
The number 16 would be = 22
The number 17 would be = AAA
The number 18 would be = AAB
...

How can I define a formula for this ? ( I will implement this formula with PHP programming language but I guess this is math right ? How can I create a 'formula' for this ? Can you help me get there?

Will it always cost a recursive iteration ? Is there a way to quickly get to the result ?

Lets say my number is at 400000 or 1 000 000, will it always cost alot of iteration to get to the result? Is there a way to avoid the iteration/cost?

Thanks

CodePudding user response:

You have an alphabet containing k symbols, and you want to make n distinct combinations of these symbols.

Map your k symbols to digits 0, 1, 2, ..., k-1. Then your problem is as easy as rewriting a number into base-k.

In PHP you can use function base_convert to convert a number from base 10 to base k, then function strtr to replace the standard digits of base k into your custom symbols.

To convert 400000 into your base AB12:

$s = base_convert("400000", 10, 4)
$s = strtr($s, "0123", "AB12")

echo $s

CodePudding user response:

While I'd first question if you could find a way to have more flexibility around these constraints (e.g. limited alphabet), for the sake of the question I'll assume the constraints are unchangeable.

To do this then you're essentially needing to create your own cipher with a limited alphabet. That cipher (key/value pairs) used to encode/decode this would need to be manually defined. Your numbers will only be able to go as high as the number of permutations possible from the allowed characters.

Here's a conceptual example:

// get permutations based on characters - while this function isn't defined here, and example (that allows you to specify length as well) can be found at https://www.tutorialspoint.com/generate-all-combinations-of-a-specific-size-from-a-single-set-in-php
$allowedPermutations = getPermutationsFromCharaceters(['a', 'b', 1, 2, 3]);

$wordToNumber = [];
$numberToWord = [];
$number = 0;

foreach($allowedPermutations as $permutation) {

  $wordToNumber[$permutation] = $number;
  $numberToWord[$number] = $permutation;
  $number  ;

}

// output word equivalent of 3
echo $numberToWord[3];

// output number equivalent of whatever 3 equated to
echo $wordToNumber[$numberToWord[3]];
  • Related