Partición de una secuencia de caracteres en grupos de $3$ o $4$

Question

Tengo un código informático que produce secuencias de caracteres de distintas longitudes. Para facilitar la lectura, me gustaría formatear las secuencias de salida como grupos de $3$ o $4$ caracteres. Ejemplos:

• La secuencia ABCDEF podría formatearse como ABC DEF ( $2$ grupos de $3$ caracteres)
• La secuencia ABCDEFGHIJK podría formatearse como ABC DEFG HIJK ( $1$ grupo de $3$ y $2$ grupos de $4$ caracteres

Me parece que cualquier secuencia con $6$ o más personajes podrían dividirse en grupos de $3$ o $4$ caracteres sin ningún resto. Es decir, para una secuencia de longitud $n$ , donde $n > 5$ parece posible encontrar siempre una solución entera no negativa para $a$ y $b$ en la ecuación $ n = a \times 3 + b \times 4$ .

A esto, tengo dos preguntas matemáticas:

1. ¿Estoy en lo cierto al suponer que esto es siempre posible?
2. ¿Existe una forma rápida y directa de calcular $a$ y $b$ para un determinado $n$ ?

Answer 1

Tu suposición es correcta. Su problema es equivalente al problema de la moneda ( https://en.m.wikipedia.org/wiki/Coin_problem ): la de saber cuál es la mayor cantidad de dinero que no puede se paga con monedas de valor 3 y 4. Si las monedas son de $a $ y $b $ Se ha comprobado que dicha cantidad es $ab - a - b $ . Hacer $a=3, b=4$ da $5$ Así que cualquier cantidad de dinero que valga $6$ o más se puede pagar con monedas de $3$ y $4$ . Para su problema específico, puede dividir esas secuencias de caracteres en esos grupos.

En cuanto a cómo hacerlo: intenta hacer grupos de 3 hasta que el restante sea un múltiplo de 4.

Answer 2

(1) Sí, y el límite de $6$ es agudo: Dados los números coprimos $m, n$ el mayor número entero que no puede escribirse como una combinación integral no negativa de $m$ y $n$ (el llamado Número de Frobenius ) es $m n - m - n$ . Este es el caso de dos monedas del Problema de la moneda de Frobenius .

(2) Aquí está parte de un "algoritmo codicioso" que minimiza el número de grupos (es decir, maximiza el número de agrupaciones de $4$ ): Para una longitud de secuencia dada $L$ , dejemos que $q := \left\lfloor\frac{L}{4}\right\rfloor$ y que $r$ sea el resto de la división de $L$ por $4$ para que $L = 4 q + r$ , $r \in \{0, 1, 2, 3\}$ :

• Si $r = 2$ entonces podemos escribir $L$ como $$L = 4 q + 2 = [(q - 1) \cdot 4 + 4] + 2 = (q - 1) \cdot 4 + 2 \cdot 3 ,$$ para que podamos romper $L$ en $q - 1$ grupos de $4$ y $2$ grupos de $3$ .

¿Puedes resolver los casos $r = 0, 1, 3$ ?

Tenga en cuenta que, en general, hay más de una solución: Para $L \geq 18$ tendremos al menos cuatro grupos de $3$ o tres grupos de $4$ pero siempre se puede sustituir una de estas agrupaciones por la otra.

Answer 3

El PO presenta la ecuación $$ n = 3a + 4b $$ y asume que es posible encontrar siempre una solución entera no negativa para $a$ y $b$ dado cualquier $n > 5$ , donde $n \in \Bbb{Z}$ .

1. ¿Estoy en lo cierto al suponer que esto es siempre posible?

Esto es respondido y confirmado por RSerrao y Travis , refiriéndose al caso de dos monedas del Problema de la moneda .

2. ¿Existe una forma rápida y directa de calcular $a$ y $b$ para un determinado $n$ ?

Siguiendo el ejemplo de Travis , dejemos que $a \in \{0, 1, 2, 3\}$ para minimizar el número de grupos, dejemos $q = \lfloor n/4 \rfloor$ sea el cociente y $r = n \bmod 4$ sea el resto de la división de $n$ por $4$ . Esto da cuatro casos para resolver la ecuación $n=3a+4b$ con enteros no negativos: $$ n = \begin{cases} 3 \times 0 + 4 \times (q - 0), & \text{if $ r = 0 $} \\ 3 \times 3 + 4 \times (q - 2), & \text{if $ r = 1 $} \\ 3 \times 2 + 4 \times (q - 1), & \text{if $ r = 2 $} \\ 3 \times 1 + 4 \times (q - 0), & \text{if $ r = 3 $} \end{cases} $$ A partir de esto, se puede demostrar que $a$ el número mínimo de grupos de $3$ se puede expresar como $$ a = 3-(n+3)\bmod4 $$ y $b$ el número correspondiente de grupos de $4$ se puede expresar como $$b = (n - 3a)/4$$