Convert a number to the shortest possible character string while retaining uniqueness

Question

I have a number, say "123456", and I need to map it to a string, any string. The only constraint on the map functions are:

each number must map to a unique character string (this means the string can be arbitrarily long)
character string can only contain 0-9, a-z, A-Z

What map function would produce the shortest strings?

Solutions in JavaScript are preferred.

Note: Clearly the simplest solution is to use the original number, so make sure you solution does better than that.

You say "a list of digits" rather than "a number". Does this mean you want "000006" treated differently from "6" ? — AakashM, Apr 01 '10 at 11:33
A good question. No I don't. I'll correct that to make it more clear. — alumb, Apr 01 '10 at 15:55

Daniel Vassallo · Accepted Answer · 2010-04-01T11:31:10.243

33

You may want to use Base 36 or Base 62.

Base 36 would be the most compact for case-insensitive alphanumerical characters, but if you want to exploit case-sensitivity, Base 62 would be approximately 20% more compact.

For Base 36, you can easily use JavaScript's Number.toString(radix) method, as follows:

var n = 123456;
n.toString(36); // returns: "2n9c"

For Base 62, you may want to check this forum post. Basically you should be able to do the following:

Number.prototype.toBase = function (base) {
    var symbols = 
    "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");
    var decimal = this;
    var conversion = "";

    if (base > symbols.length || base <= 1) {
        return false;
    }

    while (decimal >= 1) {
        conversion = symbols[(decimal - (base * Math.floor(decimal / base)))] + 
                     conversion;
        decimal = Math.floor(decimal / base);
    }

    return (base < 11) ? parseInt(conversion) : conversion;
}

var n = 123456;
n.toBase(62); // returns: "w7e"

edited Apr 01 '10 at 11:31

answered Apr 01 '10 at 00:54

Daniel Vassallo

337,827
72
505
443

Unless I'm mistaken, OP requires base 62. – spender Apr 01 '10 at 00:57
@spender: Yes, you're right, since A-Z was explicitly mentioned. Modified my answer. – Daniel Vassallo Apr 01 '10 at 01:01
123456.toString(36) does satisfy the requirements... too bad it doesn't do base 62, that would be better. – alumb Apr 01 '10 at 01:03
4

You are computing `Math.floor(decimal / base)` twice, I wouldn't call `parseInt` at the end, and I would throw a RangeError exception instead of returning false. – Alsciende Apr 01 '10 at 13:22
The answer should contain a way to convert the base36 back to "normal" string. – shredding Dec 26 '14 at 10:04
1

```parseInt('2n9c', 36)``` – shredding Dec 26 '14 at 10:09
@Tresdin See http://stackoverflow.com/questions/5943726/string-charatx-or-stringx for why `str[idx]` is unwise. – Ahmed Fasih Aug 25 '16 at 15:59
Here’s a module that does both encoding and decoding, for arbitrary dictionaries (not just `[0-9a-z]` or `[0-9a-zA-Z]`): https://www.npmjs.com/package/numbase – Ahmed Fasih Aug 25 '16 at 22:38

Regular Jo · Answer 2 · 2015-04-15T01:23:50.530

I made this to create YouTube-like keys. It uses regex to capture numbers and then cycles over a match-list to assemble the the string.

Order of the chars array is arbitrary, you can actually make it anything you like, but once you have it set in place, don't change it later, otherwise you may run into duplicate keys, and make sure you don't have any duplicates.

Here, num, is the variable that holds the input key. It's very long in this sample, but it can be any length.

var chars = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
num = "000102030405060708091011121314151617181920212223242526272829303132333435373839404142434445464748495051525354555657585960616263646566";
getnums = num.match(/(0|6[0-1]|[0-5]?[0-9])/g);
to62 = "";
for (var i=0;i<getnums.length;i++) {
    to62 = to62 + chars[parseInt(getnums[i])];
    // console.log(getnums[i] + ": " + chars[parseInt(getnums[i])])
}
console.log(to62);

And here's an implementation in Cold Fusion that uses 1-based arrays rather than javascript's 0-based arrays, in case it helps anyone.

<cfscript>
  chars = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"];
  num = "0001020304050607080910111213141516171819202122232425262728293031323334353738394041424344454614748495051525354555657585960616263646566";
  getnums = ReMatch("(0|6[0-1]|[0-5]?[0-9])",num);
  to62 = "";
  for (i=1; i<=arraylen(getnums); i=i+1) {
      to62 = to62 & chars[getnums[i]+1];
  }
  writeoutput(to62);
</cfscript>

Convert a number to the shortest possible character string while retaining uniqueness

2 Answers2

Linked

Related