Manejo de Strings

Iniciado por _whiteBird, 21 Junio 2020, 04:15 AM

0 Miembros y 1 Visitante están viendo este tema.

_whiteBird

Hola, tengo un problema que necesito convertir un string a si misma cambiando las letras a mayúsculas o no en javascript ej

dada la string "string" que al aplicar una funcion nos retorne un array con todas las posibilidades Ej:
[
String,
sTring,
stRing,
strIng,
...
String
STring
StRing
...
STRING
]

No pido que me lo hagan solo que me orienten ya que llevo toda una tarde y no avance nada

@XSStringManolo

Busca el código de un programa de fuerza bruta o generador de diccionarios. Es más difícil de hacer de lo que parece xD.


Tryptophan

Si queres armarlo, vas a necesitar un arbol. La raiz del arbol va a ser la palabra sin transformaciones y cada derivacion del arbol, es una combinacion posible.

Serapis

#3
No es tan complicado...

En primer lugar puesto que se quiere devolver en un array hay que precalcular el tamaño que él mismo tendrá.

Dado que cada carácter tiene 2 variaciones (mayúscula minúscula), que no hay permutaciones de lugar y el tamaño del string...
cantidad = 2^size(delString)
Siendo la cadena: 'string' size=6; 2^6=64. Luego el array tendrá 64 ítems.

La segunda parte, se resuelve en un bucle recursivo... usando grafos. Básicamente es un árbol binario. Nota que no es preciso usar ni construir ninguna estructura especial, más allá del array. Aunque tirando por un árbol binario, te sería más sencillo.

La palabra tendrá un nodo raíz (pongamos '*'), que accede a la primera letra, es decir 's' y 'S' son sus dos nodos hijo.
A su vez cada una de ellas tiene como nodos hijos a la siguiente letra en las dos versiones (mayúscula y minúscula).
Te pongo la jerarquía, de nodos, el de la izquierda es un nodo ya añadido al árbol, los de la derecha son los hijos que se le añaden como hijos:

*= s|S    <--- hijo izquierdo y derecho del nodo raíz.
s= t|T    <--- hijo izquierdo y derecho del nodo izquierdo de raíz
S= t|T    <--- hijo izquierdo y derecho del nodo derecho de raíz
t= r|R     // etc...
T= r|R
r= i|I
R= i|I
i= n|N
I= n|N
n= g|G
N= g|G
g=
G=


Nota que los dos últimos nodos no tienen hijos...

Ahora si se recorre todas las posibilidades del árbol obtendrás las 64 combinaciones distintas (desprecia el nodo raíz para formar la combinación a la hora de pasarlo al array de destino).
El problema de usar una estructura de árbol, es que empleará más espacio del strictamente necesario, ya que por ejemplo, al llegar al último nodo, n y N, cada uno de ellos tendrán por nodos finales 'g' y 'G', es decir se habrá añadido 32 nodos 'g' y 32 nodos 'G'.
Estrictamente basta un array de una estructura simple con cada uno de esos nodos:

Estructura Nodo
   char Nombre
   byte NumHijos
   arrayde Nodo Hijos()   // 2
   boleano Terminal
   entero Indice
Fin estructura

Array de nodo Nodos()


Luego se puede pasar como una cadena de texto, o un array de texto, el contenido de más arriba '*= s|S, s= t|T, S= t|T ..." , el caso es una función recibe y parsea dicho contenido al array Nodos() que se compone de la estructura nodo.
Rellenando dicho array quedaría así:

nodos(0).Nombre = "*"
nodos(0).NumHijos = 2
nodos(0).Hijos(0) =  nodos(1) // 's'
nodos(0).Hijos(1) =  nodos(2) // 'S'
nodos(0).Indice = 0
nodos(0).Terminal = FALSE

nodos(1).Nombre = "s"
nodos(1).NumHijos = 2
nodos(1).Hijos(0) =  nodos(3)  // 't'
nodos(1).Hijos(1) =  nodos(4)  // 'T'
nodos(1).Indice = 1
nodos(1).Terminal = FALSE

nodos(2).Nombre = "S"
nodos(2).NumHijos = 2
nodos(2).Hijos(0) =  nodos(3)  // 't'
nodos(2).Hijos(1) =  nodos(4)  // 'T'
nodos(2).Indice = 2
nodos(2).Terminal = FALSE
...
...
...

nodos(10).Nombre = "N"
nodos(10).NumHijos = 2
nodos(10).Hijos(0) =  nodos(11)  // 'g'
nodos(10).Hijos(1) =  nodos(12)  // 'G'
nodos(10).Indice = 10
nodos(10).Terminal = FALSE

nodos(11).Nombre = "g"
nodos(11).NumHijos = 0
nodos(11).Hijos // no dimensionado.
nodos(11).Indice = 11
nodos(11).Terminal = TRUE

nodos(12).Nombre = "G"
nodos(12).NumHijos = 0
nodos(12).Hijos // no dimensionado.
nodos(12).Indice = 12
nodos(12).Terminal = TRUE


Ahora con dciho array una función recorre recursivamente, tomando en cada ciclo el 'nombre' del nodo visitado, que se usa para ir concatenando la variación adecuada. La recursión finaliza cuando el nodo es terminal...
Como cada nodo tiene 2 hijos (podrían tener 1 o más), se precisa tambén un bucle interno para dicho recorrido de hijos.

La función de recorrido se invoca desde la que parsea la entrada,  sería más o menos así:


Funcion Recorrer(nodo n, entero i, entero xWord, string parcial, array string Salida() )
   entero j, k

   bucle para k desde 0 hasta n.NumHijos-1
       j = n.Hijos(k).Indice
       
       parcial.Add( nodos(j).Nombre, i)         //añade el char de 'nodos(j).Nombre' en la posición 'i' del string 'parcial'
       i +=1
       
       Si (nodos(j).Terminal = TRUE)
           Salida(xWord) = parcial
           xWord +=1
       Sino
           Recorrer(nodos(j), i, xWord, parcial, Salida)
       fin si

       i -=1
       // estrictament esto no es necesario, ya que 'i' permitirá sobrescribir sin borrar el previo.
       parcial.Remove( i)     // elimina de parcial el char en la posición 'i'
   Siguiente
Fin funcion

Esta función (así de simple), recorre todas las combinaciones posibles.

La función que parsea el texto de entrada, lo dejo a tu esfuezo, pués se trata de 'desguazar' dicha cadena en sus nodos, y cada nodos en sus elementos, para generar el array de nodos. Se requieren dos bucles, en el primero se crea el array con los 13 nodos (0 a 12, el 0 es el raíz), aplicando nombre, indice (el mismo del contador del bucle), número de hijos y si es o no terminal. Es terminal si no tiene hijos (caso de 'g' y 'G'). En el segundo bucle, se rellenan los datos que no se conocían , esto es, los hijos, requiere una búsqueda. Por ejemplo: Sabiendo que 't' tiene como hijos a 'r' y a 'R', precisa buscar que posicón ocupan esos nodos 'r' y 'R', para terminar de rellenar los datos (es decir busca rel índice de ?????:

nodos(3).Hijos(0) =  nodos(?????)  // 'r'
nodos(3).Hijos(1) =  nodos(?????)  // 'R'


La funcion principal, invoca a dos, una para generar los nodos y luego para realizar el recorrido.

Array de String() = funcion CombinatoriaMayusMinus(string Palabra)
   entero sizeArray = (2 ^ palabra.size)
   array de String Salida(0 a sizeArray -1)
   string s = Palabra
   entero indexChar =0, indexWord =0


   Llamada a ParseEntrada(Palabra)
   Llamada a Recorrer(nodos(0), indexChar, indexWord , s, Salida)
   Devolver  Salida
fin funcion



La función que construye el array de la estructura 'nodo'...
Nota que aquí tomamos la palabra entrada, sin generar las producciones comentadas al principio (dada la simplicidad de dichas producciones, es todo muy deducible).

Funcion ParseEntrada(string Palabra)
   entero k, j, i, n

   dimensionar nodos(0 a palabra.size * 2)    // esta declarado a nivel raiz (ver más arriba)
   
   nodo(0).Nombre = "*"    // <--- nodo raíz
   nodo(0).Indice = 0
   nodo(0).NumHijos = 2
   nodo(0).Terminal = False

   j = 0
   bucle para k desde 0 hasta palabra.Size -2  // la última letra es terminal y no tiene 'siguiente letra'
       j +=1
       nodo(j).Nombre = palabra.charAt(k).ToLower   //// <---- la minuscula
       nodo(j).Indice = j
       nodo(j).NumHijos = 2   ' porque es mayus y minus
       nodo(j).Terminal = False
       
       j +=1
       nodo(j).Nombre = palabra.charAt(k).ToUpper    // <---- la mayuscula
       nodo(j).Indice = j
       nodo(j).NumHijos = 2   ' porque es mayus y minus
       nodo(j).Terminal = False
   Siguiente

   j +=1
   nodo(j).Nombre = palabra.charAt(k).ToLower   //// <---- la minuscula
   nodo(j).Indice = j
   nodo(j).NumHijos = 0  
   nodo(j).Terminal = TRUE
       
   j +=1
   nodo(j).Nombre = palabra.charAt(k).ToUpper    // <---- la mayuscula
   nodo(j).Indice = j
   nodo(j).NumHijos = 0
   nodo(j).Terminal = TRUE

// -------------------- fin primera fase ----------------
 
   // Ahora falta asociar los hijos a cada nodo.
   //    Siendo siempre solo 2 hijos es muy simple y no hace falta esta busqueda, es deducible
   //    pero en casos con diferente número de hijos, tocará buscar...
   n = (j-2)
   bucle para k desde 0 hasta n
       bucle para i desde 0 hasta nodos(k).NumHijos -1
           j = BuscarNodo(... )  // <--- esta función y los parámetros que deba recibir, los dejo a tu esfuerzo
           // pero para la palabra 'string', para '*' buscamos nodo(?).nombre, donde nombre son  's' y 'S' (en cada ciclo)
           //    para 'R' buscamos 'i' e 'I', etc...
           nodos(k).Hijos(i) = nodos(j)
       Siguiente
   Siguiente

// -------------------- fin segunda fase ----------------
fin funcion


Una captura:
(nota que yo he dejado el 'nombre' de la raíz  '*', con cada uno)




La salida completa sería:
Citar
*= s|S; s= t|T; S= t|T; t= r|R; T= r|R; r= i|I; R= i|I; i= n|N; I= n|N; n= g|G; N= g|G; g=; G=
Nodo Inicial: *
Nodos Finales: g, G


1 ---> *string   0
1 ---> *strinG   0
1 ---> *striNg   0
1 ---> *striNG   0
1 ---> *strIng   0
1 ---> *strInG   0
1 ---> *strINg   0
1 ---> *strING   0
1 ---> *stRing   0
1 ---> *stRinG   0
1 ---> *stRiNg   0
1 ---> *stRiNG   0
1 ---> *stRIng   0
1 ---> *stRInG   0
1 ---> *stRINg   0
1 ---> *stRING   0
1 ---> *sTring   0
1 ---> *sTrinG   0
1 ---> *sTriNg   0
1 ---> *sTriNG   0
1 ---> *sTrIng   0
1 ---> *sTrInG   0
1 ---> *sTrINg   0
1 ---> *sTrING   0
1 ---> *sTRing   0
1 ---> *sTRinG   0
1 ---> *sTRiNg   0
1 ---> *sTRiNG   0
1 ---> *sTRIng   0
1 ---> *sTRInG   0
1 ---> *sTRINg   0
1 ---> *sTRING   0
1 ---> *String   0
1 ---> *StrinG   0
1 ---> *StriNg   0
1 ---> *StriNG   0
1 ---> *StrIng   0
1 ---> *StrInG   0
1 ---> *StrINg   0
1 ---> *StrING   0
1 ---> *StRing   0
1 ---> *StRinG   0
1 ---> *StRiNg   0
1 ---> *StRiNG   0
1 ---> *StRIng   0
1 ---> *StRInG   0
1 ---> *StRINg   0
1 ---> *StRING   0
1 ---> *STring   0
1 ---> *STrinG   0
1 ---> *STriNg   0
1 ---> *STriNG   0
1 ---> *STrIng   0
1 ---> *STrInG   0
1 ---> *STrINg   0
1 ---> *STrING   0
1 ---> *STRing   0
1 ---> *STRinG   0
1 ---> *STRiNg   0
1 ---> *STRiNG   0
1 ---> *STRIng   0
1 ---> *STRInG   0
1 ---> *STRINg   0
1 ---> *STRING   0

Número de nodos: 13
Total de caminos: 126
Total de Salidas: 64

La opción de resolverlo con un árbol, es también adecuada, como te describí más arriba... pero elige el modelo que mejor veas factible de entender e implementar...

@XSStringManolo

Tengo que aprenderme esto xD

Guardado

Emertech

#5
Cita de: _whiteBird en 21 Junio 2020, 04:15 AM
Hola, tengo un problema que necesito convertir un string a si misma cambiando las letras a mayúsculas o no en javascript ej

dada la string "string" que al aplicar una funcion nos retorne un array con todas las posibilidades Ej:
[
String,
sTring,
stRing,
strIng,
...
String
STring
StRing
...
STRING
]

Hay 1 modo más sencillo basado en un método que hice hace tiempo.
-   Crear una matriz m * n, donde m = nro de combinaciones y n = nro de letras.
-   Separar la palabra en 2 filas (sea matriz bidimensional o 2 unidimensionales) separando cada letra en una columna de cada fila, la 1era con sus letras en mayúscula y la 2da con sus letras en minúscula.
-   Llenar la matriz m*n con la fila de letras minúsculas.
-   Reemplazar de derecha a izquierda las columnas de la matriz m*n con la fila de las letras mayúsculas intercalando cada columna empezando con el valor de 1 e incrementando este valor para las siguientes columnas con el doble del valor anterior (dejo unas imágenes en Excel para ilustrar).



-   Dejo un código de prueba en c++ para demostrar lo que menciono que se puede hacer en javascript similar.



Código (cpp) [Seleccionar]
#include <iostream>

int main()
{
char mat01[6][6] = { {'S','T','R','I','N','G'}, {'s','t','r','i','n','g'} };
char mat02[64][6];

int filMax = 64;
int colMax = 6;

for (int fil = 0; fil < filMax; fil++)
{
for (int col = 0; col < colMax; col++)
{
mat02[fil][col] = mat01[1][col];
}
}
int iRep = 1;
for (int col = colMax - 1; col >= 0; col--)
{
int iFlag = 0;
int iCont = 0;
for (int fil = 0; fil < filMax; fil++)
{
if (iCont == 0)iFlag = 0;
if (iCont == iRep)iFlag = 1;

if (iFlag == 1)mat02[fil][col] = mat01[0][col];

if (iCont < iRep && iFlag == 0)
{
iCont++;
}

if (iCont > 0 && iFlag == 1)
{
iCont--;
}
}
iRep = iRep * 2;
}
for (int fil = 0; fil < filMax; fil++)
{
std::cout << "Combinacion: " << fil + 1 << " ";
for (int col = 0; col < colMax; col++)
{
std::cout << mat02[fil][col];
}
std::cout << std::endl;
}
}

Tachikomaia

A mí lo que se me ocurre es ir incrementando un "número binario" así:
000000
000001
000010
etc, de modo que un 0 representa una minúscula y 1 una mayúscula.

Pero el código tendría que pensar cómo sería y no tengo ganas ni tanta capacidad de hacerlo.