Desafío

Dada una matriz estocástica izquierda o derecha donde el límite a medida que x se aproxima al infinito de la matriz a la potencia de x se aproxima a una matriz con todos los valores finitos, devuelve la matriz a la que converge la matriz. Básicamente, desea seguir multiplicando la matriz por sí misma hasta que el resultado ya no cambie.

Casos de prueba

[[7/10, 4/10], [3/10, 6/10]] -> [[4/7, 4/7], [3/7, 3/7]]
[[2/5, 4/5], [3/5, 1/5]] -> [[4/7, 4/7], [3/7, 3/7]]
[[1/2, 1/2], [1/2, 1/2]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/3, 2/3], [2/3, 1/3]] -> [[1/2, 1/2], [1/2, 1/2]]
[[1/10, 2/10, 3/10], [4/10, 5/10, 6/10], [5/10, 3/10, 1/10]] -> [[27/130, 27/130, 27/130], [66/130, 66/130, 66/130], [37/130, 37/130, 37/130]]
[[1/7, 2/7, 4/7], [2/7, 4/7, 1/7], [4/7, 1/7, 2/7]] -> [[1/3, 1/3, 1/3], [1/3, 1/3, 1/3], [1/3, 1/3, 1/3]]

Reglas

• Se aplican lagunas estándar
• Puede elegir si desea una matriz estocástica derecha o izquierda
• Puede usar cualquier tipo de número razonable, como flotantes, racionales, decimales de precisión infinita, etc.
• Este es el código de golf , por lo que el envío más corto en bytes para cada idioma se declara ganador de su idioma. No se aceptarán respuestas.

R ,  44  43 bytes

function(m){X=m
while(any(X-(X=X%*%m)))0
X}

Pruébalo en línea!

Simplemente sigue multiplicándose hasta que encuentra una matriz fija. Aparentemente X!=(X=X%*%m)hace la comparación, luego reasigna X, así que eso está bien.

Gracias a @Vlo por eliminar un byte; a pesar de que tachado 44 sigue siendo regular 44.

Octava ,45 42 35 bytes

@(A)([v,~]=eigs(A,1))/sum(v)*any(A)

Pruébalo en línea!

¡Ahorré 3 bytes gracias a Giuseppe y 7 más gracias a Luis Mendo!

Esto utiliza que el vector propio correspondiente al valor propio 1 (también el valor propio máximo) es el vector de columna que se repite para cada valor de la matriz limitante. Tenemos que normalizar el vector para que tenga la suma 1 para que sea estocástico, luego simplemente lo repetimos para completar la matriz. No estoy muy versado en el golf Octave, pero no he podido encontrar una manera funcional de hacer multiplicaciones repetidas, y un programa completo parece que siempre será más largo que esto.

Podemos usarlo any(A)ya que, a partir de las restricciones, sabemos que la matriz debe describir una cadena de Markov irreducible, por lo que cada estado debe ser accesible desde los otros estados. Por lo tanto, al menos un valor en cada columna debe ser distinto de cero.

Wolfram Language (Mathematica) , 14 bytes

Flotadores de salida:

N@#//.x_:>x.#&

Pruébalo en línea!

Wolfram Language (Mathematica) , 30 bytes

Fracciones de salida:

Limit[#~MatrixPower~n,n->∞]&

Pruébalo en línea!

Jalea , 6 bytes

æ׳$ÐL

Este es un programa completo.

Pruébalo en línea!

APL (Dyalog) , 18 6 bytes

12 bytes guardados gracias a @ H.PWiz

+.×⍨⍣≡

Pruébalo en línea!

k / q, 10 bytes

k / q porque el programa es idéntico en ambos idiomas. El código es realmente idiomático k / q.

{$[x]/[x]}

Explicación

{..}está fuera de la sintaxis lambda, con xcomo parámetro implícito

$[x] tiene $ como operador de multiplicación de matriz binaria, proporcionar solo un parámetro crea un operador unario que deja multiplicados por la matriz de Markov

/[x] aplica la multiplicación izquierda hasta la convergencia, comenzando con la propia x.

C (gcc) , 207 192 190 181 176 bytes + 2 bytes de bandera-lm

• Salvó quince diecisiete veintidós bytes gracias a ceilingcat .
• Guardado nueve bytes; la eliminación return A;.

float*f(A,l,k,j)float*A;{for(float B[l*l],S,M=0,m=1;fabs(m-M)>1e-7;wmemcpy(A,B,l*l))for(M=m,m=0,k=l*l;k--;)for(S=j=0;j<l;)m=fmax(m,fdim(A[k],B[k]=S+=A[k/l*l+j]*A[k%l+j++*l]));}

Pruébalo en línea!

Python 3 , 75 61 bytes

f=lambda n:n if allclose(n@n,n)else f(n@n)
from numpy import*

Pruébalo en línea!

En los casos de prueba hay imprecisiones de flotación, por lo que los valores pueden diferir un poco de las fracciones exactas.

PD. numpy.allclose()se usa porque numpy.array_equal()es más largo y propenso a imprecisiones de flotación.

-14 bytes Gracias HyperNeutrino;) Oh sí, olvidé el operador @; P

Java 8, 356339 bytes

import java.math.*;m->{BigDecimal t[][],q;RoundingMode x=null;for(int l=m.length,f=1,i,k;f>0;m=t.clone()){for(t=new BigDecimal[l][l],i=l*l;i-->0;)for(f=k=0;k<l;t[i/l][i%l]=(q!=null?q:q.ZERO).add(m[i/l][k].multiply(m[k++][i%l])))q=t[i/l][i%l];for(;++i<l*l;)f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?f:1;}return m;}

-17 bytes gracias a @ceilingcat .

Definitivamente no es el lenguaje correcto ... Maldita precisión de coma flotante ...

Explicación:

Pruébalo en línea.

import java.math.*;     // Required import for BigDecimal and RoundingMode
m->{                    // Method with BigDecimal-matrix as both parameter and return-type
  BigDecimal t[][],q;   //  Temp BigDecimal-matrix
  RoundingMode x=null;  //  Static RoundingMode value to reduce bytes
  for(int l=m.length,   //  The size of the input-matrix
          f=1,          //  Flag-integer, starting at 1
          i,k;          //  Index-integers
      f>0;              //  Loop as long as the flag-integer is still 1
      m=t.clone()){     //    After every iteration: replace matrix `m` with `t`
    for(t=new BigDecimal[l][l],
                        //   Reset matrix `t`
        i=l*l;i-->0;)   //   Inner loop over the rows and columns
      for(f=k=0;        //    Set the flag-integer to 0
          k<l           //    Inner loop to multiply
          ;             //      After every iteration:
           t[i/l][i%l]=(q!=null?q:q.ZERO).add(
                        //       Sum the value at the current cell in matrix `t` with:
             m[i/l][k]  //        the same row, but column `k` of matrix `m`,
             .multiply(m[k++][i%l])))
                        //        multiplied with the same column, but row `k` of matrix `m`
        q=t[i/l][i%l];  //     Set temp `q` to the value of the current cell of `t`
    for(;++i<l*l;)      //   Loop over the rows and columns again
      f=t[i/l][i%l].setScale(9,x.UP).equals(m[i/l][i%l].setScale(9,x.UP))?
                        //    If any value in matrices `t` and `m` are the same:
         f              //     Leave the flag-integer unchanged
        :               //    Else (they aren't the same):
         1;}            //     Set the flag-integer to 1 again
  return m;}            //  Return the modified input-matrix `m` as our result