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?
Advertisement
Answer
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);