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

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?

CodePudding user response：

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

CodePudding user response：

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

CodePudding user response：

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