Tengo la tarea de crear un script JS que pueda encontrar una cadena mediante la búsqueda binaria en una matriz que contiene todas las permutaciones de los caracteres alfabéticos (solo en minúsculas) con una longitud de 6, es decir, todas las cadenas de esta forma:
['aaaaaa','aaaaab','aaaaac'.... 'zzzzzx','zzzzzy','zzzzzz']
(Para un total de 26 ^ 6 elementos en la matriz)
Debido a su tamaño, no puedo generar la matriz localmente y ejecutar una búsqueda binaria regular en ella, necesito poder encontrar la cadena en la posición n/2 (n = 26^6) sin crear la matriz.
Por otro lado, necesito crear algún tipo de asignación 1 a 1 entre cualquier cadena ('aaaaaa', 'zzzzzz') a un número y al revés (de número a cadena) que luego puedo hacer cálculos de división en y encontrar la cadena media y así sucesivamente.
Preferiblemente, esto debería estar en JS/TS, ya que quiero hacer una aplicación de nodo al final.
¿Algunas ideas?
Puedes hacer algo que funcione como números binarios, quiero decir, escribe el número en base 26 y solo usa el exponente para encontrar la letra correspondiente en el lugar correspondiente.
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);
Y al revés:
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);
Nota
Esta solución generaliza un poco la pregunta a números más grandes. Los números relevantes para la pregunta aún pueden adaptarse al tipo de número JS estándar.
Solución
Puede encontrar la representación az
para un número determinado utilizando el objeto BigInt de JS (enteros de tamaño arbitrario).
En caso de que esté buscando el n/2
-ésimo número en una lista de permutaciones del clasificador, haría lo siguiente:
let bn_x = ((26n ** 6n) / 2n) // BigInt notation , s_x26 = bn_x.toString(26) // Convert in base 26. Digits are represented by 0-9,aq , s_atoz // Will hold s_x26 with digits represented by az ; s_atoz = Array .from(s_x26) // string -> array of chars (ie. array of single-letter strings) .map ( c => { // map aq -> kz, 0-9 -> aj 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);
Por supuesto, este resultado específico también se puede deducir sin cálculo.
Al revés, funciona de manera similar a la idea básica, pero con una advertencia: no hay un constructor BigInt compatible con radix en el momento de la escritura, por lo que el número debe ensamblarse utilizando los pasos elementales de la construcción de radix.
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());
Si solo desea encontrar la cadena que ocurriría en la posición dada en nuestra matriz imaginaria, podemos calcularla con esta función numberToString
:
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)}"`) )
Comenzamos con una función de ayuda que hace la mayor parte del trabajo, aceptando primero el alfabeto que queremos usar. Aquí son todas las letras minúsculas, pero fácilmente podríamos imaginarnos haciendo lo mismo contra "abcde", por ejemplo. Devuelve una función que toma un número, y luego quitamos el último "dígito: de ese número, usándolo como un índice en chars
para el último carácter, y luego para el resto de la cadena, ya sea devolviendo una cadena vacía (en nuestro caso base cuando n
es menor que nuestro conteo de caracteres) o el valor de una llamada recursiva con ese dígito eliminado y el número restante desplazado al dividir nuestro conteo de caracteres por el resto.
Colocamos una función, fixedN2s
, que llama a lo anterior con un argumento de digits
adicional que indica el número de posiciones fijas para rellenar previamente con el primer carácter. Es decir, n2s ('abc...z') (28)
produciría 'bc'
, pero queremos rellenar previamente con a
, para obtener 'aaaabc'
.
Usamos el paso 6
y nuestro alfabeto para esta función para crear numberToString
, nuestra función principal.
Tenga en cuenta que también podríamos hacer lo contrario simplemente, con algo como este fragmento:
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)}`) )