Finding a string of length 6 in a 6^26 array of strings

Question

I have a task to create a JS script that is able to find a string using binary search on an array containing all permutations of the alphabetic chars (only lower case) with length 6 - meaning all strings of this form:

['aaaaaa','aaaaab','aaaaac'.... 'zzzzzx','zzzzzy','zzzzzz']

(For a total of 26^6 items in the array)

Due to its size - I cannot generate the array locally and run a regular binary search on it, I need to be able to find the string in the n/2 position (n = 26^6) without creating the array.

On the other hand - I need to create some sort of 1-to-1 mapping between any string ('aaaaaa', 'zzzzzz') to a number and the other way around (from number to a string) which I can then make division calculations on and find the middle string and so on.

Preferably this should be in JS/TS as I want to make a node app out of it in the end.

Any ideas?

Answer 1

You can do something that works like binary numbers, I mean write the number in base26 and just use the exponant to find the corresponding letter at the corresponding spot.

let number = (26**6)/2
let exponants = number.toString(26)
let correspondingString = exponants
  .split('')
  .map(elem => parseInt(elem, 26))
  .map(elem => (elem + 10).toString(36))
  .join('')
console.log(correspondingString);

And reverse :

let string = 'naaaaa'
let correspondingNumber = string
  .split('')
  .map(elem => parseInt(elem, 36) - 10)
  .map((elem, index) => elem*(26**(5-index)))
  .reduce((sum, value)=> sum + value, 0)
console.log(correspondingNumber);
console.log(correspondingNumber == (26**6)/2)