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?

·

Juan Pablo Isaza

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);
```

·
Juan Pablo Isaza
Report

**Note**

This solution somewhat generalizes the question to larger numbers. The numbers relevant to the question can still be accomodated by the standard JS number type.

**Solution**

You can find the `a-z`

representation for a given number by using JS's BigInt object (arbitrary size integers).

In case you are looking for the `n/2`

-th number in a sorter permutation list, you'd go as follows:

```
let bn_x = ((26n ** 6n) / 2n) // BigInt notation
, s_x26 = bn_x.toString(26) // Convert in base 26. Digits are represented by 0-9,a-q
, s_atoz // Will hold s_x26 with digits represented by a-z
;
s_atoz =
Array
.from(s_x26) // string -> array of chars (ie. array of single-letter strings)
.map ( c => { // map a-q -> k-z, 0-9 -> a-j
return String.fromCharCode((( c.charCodeAt(0) < 'a'.charCodeAt(0) ) ? (c.charCodeAt(0) + ( 'a'.charCodeAt(0) - '0'.charCodeAt(0) )) : ( c.charCodeAt(0) + 10 )));
})
.join('') // array of chars -> string
;
console.log(s_atoz);
```

Of course, this specific result can also be deduced without computation.

The other way round works similar wrt the basic idea, but with a caveat: There is no radix-aware BigInt constructor at the time of writing, so the number needs to be assembled using the elementary steps from radix construction.

```
let s_atoz = 'naaaaa'
, abn_x26 =
Array
.from(s_atoz)
.map ( c => {
return BigInt(c.charCodeAt(0) - 'a'.charCodeAt(0));
})
, bn_x = abn_x26.reduce ( (previousValue, currentValue) => {
return BigInt(previousValue) * 26n + BigInt(currentValue);
}
, 0n
)
;
console.log(bn_x.toString());
```

·
Juan Pablo Isaza
Report

If you just want to find the string that would occur at the given position in our imaginary array, we can calculate it with this `numberToString`

function:

```
const n2s = (chars, len = chars .length) => (n) =>
(n < len ? '' : n2s (chars, len) (~~ (n / len)))
+ chars [n % len]
const fixedN2s = (digits, chars) => (n) =>
n2s (chars) (n) .padStart (digits, chars [0])
const numberToString = fixedN2s (6, 'abcdefghijklmnopqrstuvwxyz')
; [28, 268041553, 202214284, 26 ** 6 / 2] .forEach (
s => console .log (`numberToString (${s}) //=> "${numberToString (s)}"`)
)
```

We start with a helper function that does the bulk of the work, accepting first the alphabet we want to use. Here it's all the lower-case letters, but we could easily imagine doing the same against "abcde", for instance. It returns a function which takes a number, and then we peel off the last "digit: of that number, using it as an index into `chars`

for the last character, and then for the rest of the string either returning an empty string (in our base case when `n`

is less than our character count) or the value of a recursive call with that digit stripped and the remaining number shifted over by dividing our character count into the remainder.

We layer on a function, `fixedN2s`

, which calls the above with an additional `digits`

argument that tells the number of fixed positions to prefill with the first character. That is, `n2s ('abc...z') (28)`

would yield `'bc'`

, but we want to prefill with `a`

, to get `'aaaabc'`

.

We use pass `6`

and our alphabet to to this function to create `numberToString`

, our main function.

Note that we could do the reverse simply enough as well, with somthing like this snippet:

```
const s2n = (chars,
encoding = [...chars] .reduce ((a, d, i) => ((a [d] = i), a), {})
) => ([...ss]) => ss .length == 0
? 0
: chars .length * s2n (chars, encoding) (ss .slice (0, -1)) + encoding [ss .at (-1)]
const stringToNumber = s2n ('abcdefghijklmnopqrstuvwxyz')
; ['abc', 'woolen', 'random', 'naaaaa'] .forEach (
s => console .log (`stringToNumber ("${s}") //=> ${stringToNumber (s)}`)
)
```

·
Juan Pablo Isaza
Report

Loading