Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

218
Views
Encontrar una cadena de longitud 6 en una matriz de cadenas de 6^26

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?

about 4 years ago · Juan Pablo Isaza
3 answers
Answer question

0

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

about 4 years ago · Juan Pablo Isaza Report

0

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

about 4 years ago · Juan Pablo Isaza Report

0

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

about 4 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!