regex - regulares - regular expression examples

expresiones regulares para emparejar fracciones irreductibles

Question

¿Cómo puedo relacionar fracciones irreducibles con expresiones regulares?

Por ejemplo, 23/25, 3/4, 5/2, 100/101, etc.

En primer lugar, no tengo idea sobre la realización del algoritmo gcd en expresiones regulares.

Actualice para todos aquellos que respondan como "Está utilizando la herramienta incorrecta":

Sí, muchachos, me estoy dando cuenta para qué regex se usa normalmente. Está bien. Pero que esta pregunta sea extraña es una especie de su punto.

Actualizado 2: la idea es encontrar una expresión regular que pueda ser útil en una situación como:

$> echo "1/2" | grep -P regex
1/2
$> echo "2/4" | grep -P regex

Por lo tanto, la expresión regular debe ser solo una cadena, sin utilizar ningún script ni variable. Sólo regex.

En realidad, ya conozco algunas expresiones regulares que coinciden con fracciones reducibles escritas en el sistema numérico único.

$> echo "11/1111" | grep -P ''^1/1+$|(11+)+/1+//1+$''
11/1111

Entonces, la cosa es convertir de decimal a un sistema numérico unico en expresiones regulares, pero no sé cómo.

Answer 1

ACTUALIZAR

Como el póster solicitó una expresión regular única que coincida con cadenas como "36/270", pero dice que no importa cuán legible sea, esa expresión regular es:

my $reducible_rx = qr{^(/d+)/(/d+)$(?(?{(1x$1."/".1x$2)=~m{^(?|1+/(1)|(11+)/1*//1+)$}})|^)};

Pero, como yo, crees que un regex ilegible es absolutamente inaceptable, lo escribirás de forma más legible como:

my $reducible_rx = qr{
  # first match a fraction:
    ^ ( /d+ ) / ( /d+ ) $
  # now for the hard part:
    (?(?{ ( 1 x $1 . "/" . 1 x $2 ) =~ m{
                ^
                (?|    1+      / (1)  # trivial case: GCD=1
                  |  (11+) /1* / /1+  # find the GCD
                )
                 $
            }x
        })
          # more portable version of (*PASS)
     | ^  # more portable version of (*FAIL)
     )
}x;

Puede mejorar la capacidad de mantenimiento dividiendo la versión que coincida con la versión única de la que coincide con la versión decimal como esta:

# this one assumes unary notation
my $unary_rx = qr{
    ^ 
    (?|   1+       / (1)
      | (11+)  /1* / /1+ 
    ) 
    $
}x;

# this one assumes decimal notation and converts internally
my $decimal_rx = qr{
  # first match a fraction:
    ^ ( /d+ ) / ( /d+ ) $ 
  # now for the hard part:
    (?(?{( 1 x $1 . "/" . 1 x $2 ) =~ $unary_rx})
          # more portable version of (*PASS)
     | ^  # more portable version of (*FAIL) 
     )
}x;

¿No es mucho más fácil al separarlo en dos expresiones regulares nombradas? Eso haría que $reducible_rx lo mismo que $decimal_rx , pero la versión $decimal_rx es su propia cosa. Así es como lo haría, pero el póster original quería un solo regex, por lo que tendría que interpolar el anidado para eso como lo presento por primera vez arriba.

De cualquier manera, puede enchufar el arnés de prueba a continuación usando:

    if ($frac =~ $reducible_rx) {
        cmp_ok($frac, "ne", reduce($i, $j), "$i/$j is $test");
    } else {
        cmp_ok($frac, "eq", reduce($i, $j), "$i/$j is $test");
    }

Y verá que es una expresión regular correcta que pasa todas las pruebas, y además lo hace usando una sola expresión regular, por lo que, habiendo superado todos los requisitos de la pregunta original, declaro Qᴜᴏᴅ ᴇʀᴀᴛ ᴅᴇᴍᴏɴsᴛʀᴀɴᴅᴜᴍ: "Salir, ya está hecho". 😇

Y eres bienvenido.

La respuesta es hacer coincidir la expresión regular ^(?|1+/(1)|(11+)/1*//1+)$ contra la fracción una vez que se haya convertido de decimal a notación unaria, momento en el que el mayor el factor común se encontrará en $1 en un partido; De lo contrario son coprimes. Si está utilizando Perl 5.14 o superior, incluso puede hacerlo en un solo paso:

use 5.014;
my $reg  = qr{^(?|1+/(1)|(11+)/1*//1+)$};
my $frac = "36/270";  # for example
if ($frac =~ s/(/d+)/1 x $1/reg =~ /$reg/) { 
    say "$frac can be reduced by ", length $1;
} else {
    say "$frac is irreducible";
}

Que informará correctamente de que:

36/270 can be reduced by 18

(Y, por supuesto, reducir en 1 significa que ya no hay un denominador).

Si quisiera divertirse un poco con sus lectores, incluso podría hacerlo de esta manera:

use 5.014;
my $regex = qr{^(?|1+/(1)|(11+)/1*//1+)$};
my $frac  = "36/270";  # for example
if ($frac =~ s/(/d+)/"1 x $1"/regex =~ /$regex/) {
    say "$frac can be reduced by ", length $1;
} else {
    say "$frac is irreducible";
}

Aquí está el código que demuestra cómo hacer esto. Además, construye un conjunto de pruebas que prueba su algoritmo utilizando todos los numeradores y denominadores (positivos) hasta su argumento, o 30 de forma predeterminada. Para ejecutarlo bajo un arnés de prueba, póngalo en un archivo llamado coprimes y haga esto:

$ perl -MTest::Harness -e ''runtests("coprimes")''
coprimes .. ok       
All tests successful.
Files=1, Tests=900,  1 wallclock secs ( 0.13 usr  0.02 sys +  0.33 cusr  0.02 csys =  0.50 CPU)
Result: PASS

Este es un ejemplo de su salida cuando se ejecuta sin el arnés de prueba:

$ perl coprimes 10
1..100
ok 1 - 1/1 is 1
ok 2 - 1/2 is 1/2
ok 3 - 1/3 is 1/3
ok 4 - 1/4 is 1/4
ok 5 - 1/5 is 1/5
ok 6 - 1/6 is 1/6
ok 7 - 1/7 is 1/7
ok 8 - 1/8 is 1/8
ok 9 - 1/9 is 1/9
ok 10 - 1/10 is 1/10
ok 11 - 2/1 is 2
ok 12 - 2/2 is 1
ok 13 - 2/3 is 2/3
ok 14 - 2/4 is 1/2
ok 15 - 2/5 is 2/5
ok 16 - 2/6 is 1/3
ok 17 - 2/7 is 2/7
ok 18 - 2/8 is 1/4
ok 19 - 2/9 is 2/9
ok 20 - 2/10 is 1/5
ok 21 - 3/1 is 3
ok 22 - 3/2 is 3/2
ok 23 - 3/3 is 1
ok 24 - 3/4 is 3/4
ok 25 - 3/5 is 3/5
ok 26 - 3/6 is 1/2
ok 27 - 3/7 is 3/7
ok 28 - 3/8 is 3/8
ok 29 - 3/9 is 1/3
ok 30 - 3/10 is 3/10
ok 31 - 4/1 is 4
ok 32 - 4/2 is 2
ok 33 - 4/3 is 4/3
ok 34 - 4/4 is 1
ok 35 - 4/5 is 4/5
ok 36 - 4/6 is 2/3
ok 37 - 4/7 is 4/7
ok 38 - 4/8 is 1/2
ok 39 - 4/9 is 4/9
ok 40 - 4/10 is 2/5
ok 41 - 5/1 is 5
ok 42 - 5/2 is 5/2
ok 43 - 5/3 is 5/3
ok 44 - 5/4 is 5/4
ok 45 - 5/5 is 1
ok 46 - 5/6 is 5/6
ok 47 - 5/7 is 5/7
ok 48 - 5/8 is 5/8
ok 49 - 5/9 is 5/9
ok 50 - 5/10 is 1/2
ok 51 - 6/1 is 6
ok 52 - 6/2 is 3
ok 53 - 6/3 is 2
ok 54 - 6/4 is 3/2
ok 55 - 6/5 is 6/5
ok 56 - 6/6 is 1
ok 57 - 6/7 is 6/7
ok 58 - 6/8 is 3/4
ok 59 - 6/9 is 2/3
ok 60 - 6/10 is 3/5
ok 61 - 7/1 is 7
ok 62 - 7/2 is 7/2
ok 63 - 7/3 is 7/3
ok 64 - 7/4 is 7/4
ok 65 - 7/5 is 7/5
ok 66 - 7/6 is 7/6
ok 67 - 7/7 is 1
ok 68 - 7/8 is 7/8
ok 69 - 7/9 is 7/9
ok 70 - 7/10 is 7/10
ok 71 - 8/1 is 8
ok 72 - 8/2 is 4
ok 73 - 8/3 is 8/3
ok 74 - 8/4 is 2
ok 75 - 8/5 is 8/5
ok 76 - 8/6 is 4/3
ok 77 - 8/7 is 8/7
ok 78 - 8/8 is 1
ok 79 - 8/9 is 8/9
ok 80 - 8/10 is 4/5
ok 81 - 9/1 is 9
ok 82 - 9/2 is 9/2
ok 83 - 9/3 is 3
ok 84 - 9/4 is 9/4
ok 85 - 9/5 is 9/5
ok 86 - 9/6 is 3/2
ok 87 - 9/7 is 9/7
ok 88 - 9/8 is 9/8
ok 89 - 9/9 is 1
ok 90 - 9/10 is 9/10
ok 91 - 10/1 is 10
ok 92 - 10/2 is 5
ok 93 - 10/3 is 10/3
ok 94 - 10/4 is 5/2
ok 95 - 10/5 is 2
ok 96 - 10/6 is 5/3
ok 97 - 10/7 is 10/7
ok 98 - 10/8 is 5/4
ok 99 - 10/9 is 10/9
ok 100 - 10/10 is 1

Y aquí está el programa:

#!/usr/bin/env perl
#
# coprimes - test suite to use unary coprimality algorithm
# 
# Tom Christiansen <[email protected]>
# Sun Apr 17 12:18:19 MDT 2011

use strict;
use warnings;

my $DEFAULT = 2*3*5;
my $max = @ARGV ? shift : $DEFAULT;

use Test::More;
plan tests => $max ** 2;

my $rx = qr{
    ^
    (?|   1+       / (1)
      | (11+)  /1* / /1+
    )
    $
}x;

for my $i ( 1 .. $max ) {
    for my $j ( 1 .. $max ) {
        my $test;
        if (((1 x $i) . "/" . (1 x $j)) =~ /$rx/) {
            my $cf = length($1);
            $test = $i / $cf;
            $test .= "/" . $j/$cf unless $j/$cf == 1;
        } else {
            $test = "$i/$j";
        }
        cmp_ok($test, "eq", reduce($i, $j), "$i/$j is $test");
    }
}

sub reduce {
    my ($a, $b) = @_;
    use Math::BigRat;
    my $f = new Math::BigRat "$a/$b";
    return "$f";
}

Answer 2

No, no se puede hacer. Como un buen científico informático, ignoraré los aspectos específicos de la expresión regular de la herramienta y asumiré que está preguntando si hay una expresión regular. No tengo suficiente conocimiento sobre las características de expresiones regulares para garantizar que esté restringido a expresiones regulares. Esa advertencia aparte, con el espectáculo.

Reescribiendo esto obtenemos:

Sea L el lenguaje {" a / b " | donde a y b son números naturales codificados en una raíz r y a y b son coprime} . ¿Es L regular?

Supongamos que tal lenguaje es regular. Luego existe un DFA que puede decidir la membresía en L Sea N el número de estados de tal DFA. Hay un número infinito de números primos. Como el número de primos es infinito, arbitrariamente hay muchos primos mayores que el número más grande codificable en N dígitos en la raíz r . (Nota: el número más grande está claramente elevado a la potencia de N Estoy usando esta extraña redacción para mostrar cómo acomodar unario). Seleccione N+1 primos que sean mayores que este número. Todos estos números se codifican utilizando al menos N+1 dígitos (en la raíz r ). Enumera estos números primos p₀ a pₙ . Deje que sᵢ sea ​​el estado de pᵢ inmediatamente después de leer el / . Por el principio del agujero de la paloma, hay N estados y N+1 estados, por lo que existe al menos un par de índices (j,k) tal que sⱼ = sₖ . Así que a partir del estado inicial de la DFA, las entradas pₖ/ y pⱼ/ conducen al mismo estado sⱼ (o sₖ ) y pⱼ y pₖ son primos distintos.

L debe aceptar todos los pares de primos distintos p/q ya que son coprime y rechazar todos los primos divididos por ellos mismos p/p ya que p no es coprime a p . Ahora el lenguaje acepta pⱼ = pₖ por lo que hay una secuencia de estados desde sⱼ usando la cadena pₖ hasta un estado de aceptación, llame a esta secuencia β . Sea α la secuencia de estados que lee pₖ partir del estado inicial. La secuencia de estados para el DFA que comienza en el estado inicial para la cadena pₖ/pₖ debe ser la misma que α seguida de β . Esta secuencia comienza en un estado inicial, va a sₖ (leyendo la entrada pₖ ) y alcanza un estado de aceptación al leer pₖ . El DFA acepta pₖ/pₖ y pₖ/pₖ está en L pₖ no es coprime a pₖ , y por lo tanto pₖ/pₖ no está en L Contradicción. Por lo tanto el lenguaje L es irregular, o no existe una expresión regular.

Answer 3

Puedes saber que un número que termina en (0,5) es divisible por (5), o que termina en (2,4,6,8,0) es divisible por 2.

Para 3,4,6,7,8,9 como divisores, no esperaría una posibilidad, y tampoco para divisores arbitrarios.

Supongo que conoces el método, para decidir la divisibilidad entre 3 - para construir la suma cruzada rekursiva, que tiene que ser divisible entre 3, para hacer que el número sea divisible. Así que allí podría eliminar todos los 3, 6 y 9 del número, así como el 0. Para un número arbitrario, procedería de esta manera:

• borrar cada 0369
• cambie 47 a 1, (porque 4% 3 y 7% 3 = 1)
• Cambia 58 a 2, razón ve arriba.
• cambiar cada 2 a 11
• Cambia cada grupo de 111 a nada.

Si el resultado está vacío, el número era divisible por 3:

echo ${RANDOM}${RANDOM}${RANDOM} | sed ''s/[0369]//g;s/[47]/1/g;s/[58]/2/g;s/2/11/g;s/1/{3/}//g''

Un enfoque similar podría funcionar para 9, donde tienes una regla similar. ¿Pero un enfoque general para divisores arbitrarios?

Answer 4

Si escribe los números en unario y usa ":" como signo de división, creo que esto coincide con las fracciones reducibles:

/^1+:1$|^(11+):/1$|^(11+?)/2+:/2/2+$/

Luego puedes usar! ~ Para encontrar cadenas que no coincidan.

Basado en esto: montreal.pm.org/tech/neil_kandalgaonkar.shtml