Encontré un problema algorítmico y no sé cómo resolverlo en principio, porque no encontré ninguno de los algoritmos que podrían usarse aquí. Tal vez alguien pueda ayudarme con esto.
Tarea: Hay una serie de caracteres latinos. Cada carácter de la matriz se puede reemplazar por cualquier número entero. Después del reemplazo, todos los caracteres idénticos también serán reemplazados por el mismo número. ¿Es posible hacer que la suma de los valores de la matriz sea igual a k?
Aporte:
Salida: booleana: puede o no hacer que la suma de los valores de la matriz sea igual a k
Ejemplo (dardo):
var array = ["x", "x", "x", "y", "z"]; var k = 10; print(getResult(array, k)); // return true, because [2, 2, 2, 3, 1]Primero puede recorrer la matriz y contar el número de ocurrencias de "x", "y" y "z". Llamaré a esos recuentos x, y y z. Entonces el problema se convierte en:
¿Puedes encontrar los números enteros a, b y c tales que a * x + b * y + c * z = k.
Si los números pueden ser negativos entonces es relativamente simple: es posible si k % mcd(x, y, z) = 0 (ignorando los 0, entonces si x es 0 entonces k % mcd(y, z) = 0). En otras palabras, solo es posible fallar si puede hacer múltiplos de mcd (x, y, z) y k no es un múltiplo de esos números.
Si a, b y c tienen que ser no negativos, entonces se vuelve un poco más complejo. Estamos lidiando con el problema de las monedas con las monedas x, y y z. Si k % mcd(x, y, z) != 0 entonces nunca es posible. Ahora podríamos simplificar el problema dividiendo k, x, y y z por mcd(x, y, z). Después de eso, podemos ver si es fácilmente posible usando los números de Frobenius:
n = 2: todos los números > x * y - x - y se pueden construir
n = 3: se pueden construir todos los números > sqrt(3 * x * y * z)
Si k es más pequeño que eso, podemos verificar si k se puede construir utilizando la solución de programación dinámica común para el problema de la moneda.
Por supuesto, hay algunos casos extremos con los que tienes que lidiar. Por ejemplo, k = 0 o si solo se da un número, entonces es solo k % x = 0.
Observación: dados n x, m y, etc., al cambiar cualquiera de los valores de x,y,... por uno, la suma puede cambiarse solo en incrementos de GCD(n, m, ...), donde GCD es el mayor divisor común (se puede encontrar con el algoritmo de Euclides).
Por lo tanto, la condición puede cumplirse solo cuando k es un múltiplo de sus cantidades MCD.
Nota: esto supone que x, y, ... pueden no ser únicos y pueden ser negativos
Aquí hay una solución simple que funciona con las suposiciones de que:
function findNumbers([s,sum]) { // count occurences of characters: let ar1 = Object.entries(s.split("").reduce((a, c) => (a[c] = (a[c] || 0) + 1, a), {})) .sort((a, b) => b[1] - a[1]); // sort: most frequent characters first // assign interger values to each character (starting with 1 ... let ar2=ar1.map(([c, n], i) =>{ // c: character, n: occurences, i: index sum-=n*(i+1); return [c, i+1<ar1.length? i+1: ar1.length+sum] }); return [Object.fromEntries(ar2),ar2.pop()[1]>ar2.pop()[1]]; // add a results flag to each solution: true/false } let res=[["xxxyz",10],["ghijjk",17],["abcabcabd",12],["abccdef",18],["abcd",9]].map(findNumbers) console.log(res) // true, true, false, false, false Obviamente, este fue un tiro rápido. Todavía no compruebo si el carácter menos frecuente solo aparece una vez. Ciertamente necesita más refinamiento, pero ya indica bastante rápido si sería posible una solución con números enteros positivos. Si el último número no es mayor que el penúltimo, no se pueden encontrar los números adecuados y se devuelve la bandera false .