Вызов

Учитывая левую или правую стохастическую матрицу, где предел при x приближается к бесконечности матрицы, а степень x приближается к матрице со всеми конечными значениями, возвращает матрицу, к которой сходится матрица. По сути, вы хотите продолжать умножать матрицу на себя, пока результат больше не изменится.

Тестовые случаи

[[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]]

правила

• Применяются стандартные лазейки
• Вы можете выбрать, хотите ли вы матрицу справа или слева стохастик
• Вы можете использовать любой разумный тип чисел, такой как числа с плавающей точкой, рациональные числа, десятичные числа с бесконечной точностью и т. Д.
• Это код-гольф , поэтому самая короткая подача в байтах для каждого языка объявляется победителем для его языка. Ответ не будет принят

R ,  44  43 байта

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

Попробуйте онлайн!

Просто продолжайте умножать, пока не найдете фиксированную матрицу. Видимо X!=(X=X%*%m)делает сравнение, затем переназначает X, так что это аккуратно.

Спасибо @Vlo за сбривание байта; даже если вычеркнуто 44 все еще регулярно 44.

Октава ,45 42 35 байт

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

Попробуйте онлайн!

Благодаря Giuseppe удалось сэкономить 3 байта, а еще Луиса Мендо - еще 7!

При этом используется, что собственный вектор, соответствующий собственному значению 1 (также максимальному собственному значению), является вектором столбца, который повторяется для каждого значения ограничивающей матрицы. Мы должны нормализовать вектор, чтобы иметь сумму 1, чтобы он был стохастическим, затем мы просто повторяем его, чтобы заполнить матрицу. Я не слишком хорошо разбираюсь в игре в гольф в Octave, но мне не удалось найти функциональный способ повторного умножения, и полная программа кажется, что она всегда будет длиннее этой.

Мы можем использовать, any(A)так как из ограничений мы знаем, что матрица должна описывать неприводимую цепь Маркова, и поэтому каждое состояние должно быть достижимым из других состояний. Поэтому хотя бы одно значение в каждом столбце должно быть ненулевым.

Wolfram Language (Mathematica) , 14 байтов

Выходное число плавает:

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

Попробуйте онлайн!

Wolfram Language (Mathematica) , 30 байтов

Выходные доли:

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

Попробуйте онлайн!

Желе , 6 байт

æ׳$ÐL

Это полная программа.

Попробуйте онлайн!

APL (Дьялог) , 18 6 байтов

12 байтов сохранено благодаря @ H.PWiz

+.×⍨⍣≡

Попробуйте онлайн!

к / кв, 10 байт

k / q потому что программа идентична на обоих языках. Код действительно просто идиоматический к / к.

{$[x]/[x]}

объяснение

{..}вне лямбда-синтаксиса, с xнеявным параметром

$[x] имеет $ как оператор умножения двоичной матрицы, при условии, что только один параметр создает унарный оператор, который умножается на матрицу Маркова

/[x] применяет левое умножение до сходимости, начиная с самого x.

C (gcc) , 207 192 190 181 176 байт + 2 байта флага-lm

• Сохранено пятнадцать, семнадцать, двадцать два байта, благодаря floorcat .
• Сохранено девять байтов; удаление 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]));}

Попробуйте онлайн!

Python 3 , 75 61 байт

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

Попробуйте онлайн!

В тестовых случаях есть неточности с плавающей точкой, поэтому значения могут немного отличаться от точных дробей.

PS. numpy.allclose()используется потому, что numpy.array_equal()длиннее и склонен к неточностям.

-14 байт Спасибо HyperNeutrino;) О да, я забыл оператор @; P

Java 8, 356 339 байт

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 байт благодаря @ceilingcat .

Определенно не правильный язык .. Черт с плавающей точкой точности ..

Объяснение:

Попробуйте онлайн.

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