Apakah ini matriks stokastik?

24

Sebuah matriks stokastik adalah matriks probabilitas digunakan dalam konteks rantai Markov.

Sebuah kanan matriks stokastik adalah matriks di mana setiap baris jumlah untuk 1.

Sebuah meninggalkan matriks stokastik adalah matriks di mana setiap kolom jumlah untuk 1.

Sebuah ganda matriks stokastik adalah matriks di mana setiap baris dan setiap kolom jumlah untuk 1.

Dalam tantangan ini, kami akan mewakili probabilitas dalam persen menggunakan bilangan bulat . Baris atau kolom harus dalam hal ini jumlah 100dan bukan 1.

Tujuan Anda adalah untuk menulis sebuah program atau fungsi yang, diberi matriks persegi bilangan bulat sebagai input, menampilkan salah satu dari empat nilai yang menunjukkan bahwa matriks tersebut adalah stokastik kanan, stokastik kiri, stokastik berlipat ganda atau tidak ada satupun.

Memasukkan

Anda dapat menggunakan representasi matriks yang wajar untuk bahasa Anda sebagai input. Misalnya, daftar daftar, serangkaian nilai yang dipisahkan koma dengan baris yang dipisahkan oleh linebreak, dll.

Matriks input akan selalu berbentuk bujur sangkar dan hanya akan berisi bilangan bulat non-negatif. Matriks input akan selalu setidaknya 1×1.

Anda dapat meneruskan input menggunakan STDIN, sebagai argumen fungsi, atau yang serupa.

Keluaran

Anda harus memilih empat output berbeda yang sesuai dengan stokastik kanan , stokastik kiri , stokastik ganda atau tidak sama sekali . Keluaran tersebut harus konstan terlepas dari input apa yang dilewatkan. Program Anda mungkin tidak mengembalikan output yang berbeda untuk kasus yang sama, misalnya mengatakan bahwa angka negatif yang sesuai dengan tidak ada yang tidak valid.

Singkatnya, harus ada korespondensi 1-ke-1 antara output Anda dan empat kasus yang mungkin. Beberapa contoh dari keempat keluaran itu adalah {1, 2, 3, 4}atau {[1,0], [0,1], [1,1], [0,0]}atau bahkan {right, left, doubly, none}.

Harap tunjukkan dalam jawaban Anda empat keluaran yang digunakan program Anda.

Jika matriks stochastic ganda, maka Anda harus mengembalikan output yang sesuai dengan stochastic ganda, dan bukan stochastic kanan atau kiri.

Anda dapat mencetak hasilnya STDOUT, mengembalikannya dari fungsi, atau yang serupa.

Uji kasus

[100]               => Doubly stochastic

[42]                => None of those

[100  0  ]          => Doubly stochastic
[0    100]

[4   8   15]
[16  23  42]        => Left stochastic
[80  69  43]

[99  1 ]            => Right stochastic
[2   98]

[1   2   3   4 ]
[5   6   7   8 ]    => None of those
[9   10  11  12]
[13  14  15  16]

Mencetak gol

Ini adalah , jadi jawaban tersingkat dalam byte menang.

Fatalisasi
sumber
Bisakah saya mengambil input menentukan ukuran matriks terlebih dahulu?
HyperNeutrino
@AlexL. Tidak, ini tidak adil untuk mengubah spesifikasi pada saat ini.
Fatalkan

Jawaban:

9

05AB1E , 13 11 10 byte

Stochastic kanan: Stochastic [0,1]
kiri : Stochastic [1,0]
ganda: [1,1]
Tidak satu pun dari mereka: [0,0]

Dø2FOTnQPˆ

Cobalah online!

Penjelasan

D            # duplicate input
 ø           # transpose the copy
  2F         # 2 times do (once for each matrix)
    O        # sum of the rows
     TnQ     # is equal to 100
        P    # product
         ˆ   # add to global list
             # implicitly print global list at the end of the program
Emigna
sumber
14

Haskell, 57 55 byte

import Data.List
s a=all((==100).sum)<$>[transpose a,a]

Input tipe (Eq a, Num a) => [[a]]. Output daftar boolean[left-stochastic, right-stochastic]

Terima kasih kepada @proudhaskeller karena telah menghemat 2 byte

Angs
sumber
Tidak bisakah Anda menyimpan beberapa byte dengan membuat fungsi pointfree? misalnya dengan [transpose,id]<*>(maka Anda bisa menghilangkan s a=fungsi anynomous diizinkan)
flawr
@ flawr mungkin, tetapi [transpose,id]<*>memiliki tipe [[[a]]]->[[[a]]], yang membutuhkan lapisan lain dari mapdan pure/ return/ (:[])atau input tipe [[[Int]]], yang tidak alami. Yang terbaik yang saya dapatkan adalahmap(all(==100).map sum).(<$>[transpose,id]).flip id
Angs
Ah benar, terima kasih atas penjelasannya!
flawr
Bagaimana kalau all((==100).sum)bukan all(==100).map sum?
haskeller bangga
@proudhaskeller tentu saja! allmelakukan pemetaan itu sendiri.
Angs
11

R, 55 byte

function(m)c(all(colSums(m)==100),all(rowSums(m)==100))

Fungsi tanpa nama di mana mdiasumsikan sebagai R-matrix.

Keluaran:

  • [1] TRUE FALSE: Stochastic kiri
  • [1] FALSE TRUE: Stochastic benar
  • [1] TRUE TRUE: Diragukan
  • [1] FALSE FALSE: Tidak ada
Billywob
sumber
any(colSums(m)-100)dan juga untuk itu rowSumsakan menjatuhkan Anda dua byte saat membalikkan semua output, jadi jika Anda ingin menyimpannya, Anda selalu dapat meletakkan !di depan untuk -1byte net .
Giuseppe
7

Oktaf, 35 34 32 31 byte

@(n)any([sum(n);sum(n')]-100,2)

Sebut saja seperti ini:

f(100)
f(42)
f([4,8,15; 16,23,42; 80,69,43])
f([99,1;2,98])
f([1,2,3,4;5,6,7,8;9,10,11,12;13,14,15,16])

Uji di sini.

Disimpan 2 byte berkat flawr pada awalnya, tetapi pergi untuk pendekatan lain yang 1 byte lebih pendek.

Ini menghasilkan berikut untuk kasus yang berbeda:

0    Doubly
0    

1    None
1

0    Left
1

1    Right
0

Yang terakhir ,2tidak perlu jika satu digit tidak dimasukkan. Juga, jika ini dijumlahkan 1alih-alih 100(seperti yang bisa terjadi), itu akan menghemat 4byte lain .

Stewie Griffin
sumber
6

Mathematica 29 Bytes

{}⋃Tr/@#=={100}&/@{#,#}&

mengganti karakter  = U + F3C7 = [\ Transpose]. Cuplikan kode ini akan menempel dengan benar ke Mathematica.

Konvensi kebenaran yang sama dengan {lefttruth, righttruth} sebagai output

Kelly Lowder
sumber
{}⋃menghemat satu byte lebihUnion@
A Simmons
@ASimmons, terima kasih atas tipnya! Masukkan dan koreksi kesalahan dalam total byte saya.
Kelly Lowder
Saya juga berpikir jika Anda membuat output Anda {righttruth, lefttruth}, kemudian mengganti Total@dengan Tr/@akan menghemat 2 byte lebih lanjut.
A Simmons
Atau sebaliknya membalikkan dua matriks sehingga solusinya menjadi{}⋃Tr/@#=={100}&/@{#,#}&
A Simmons
@ ASimmons, Ya, itu menyelamatkan yang lain 2. Terima kasih!
Kelly Lowder
6

k, 21 19 byte

{min'100=+/'(x;+x)}

Keluaran

  • 00b tidak ada
  • 10b kiri
  • 01b kanan
  • 11b kedua

Contoh:

k)f:{min'100=+/'(x;+x)} //store function as f
k)f(100 0;98 2)
01b

sunting: kurangi jumlah byte oleh 3 - fungsi tidak perlu dimasukkan dalam lambda

sunting: kurangi bytecount sebesar 2 - H / T @Simon Major

skeevey
sumber
1
Anda benar-benar dapat menyimpan byte dengan melampirkan di lambda: {min'100 = + / '(x; +: x)}
Simon Major
5

MATL , 12 byte

sG!sv!100=XA

Output adalah dua nilai nol / satu. Pertama menunjukkan apakah matriksnya stochastic kiri, kedua jika itu adalah stochastic kanan.

Cobalah online! Atau verifikasi semua kasus uji

s      % Implicitly input N×N matrix. Sum of each column. Gives a 1×N vector
G!     % Push input transposed
s      % Sum of each column. Gives a 1×N vector
v      % Concatenate vertically. Gives a 2×N matrix
!      % Transpose. N×2
100=   % Does each entry equal 100?
XA     % True for columns that contain only "true". Gives 1×2 vector. Implicitly display
Luis Mendo
sumber
Pria yang 100 itu mahal, jawaban yang bagus.
Magic Gurita Guci
5

Mathematica, 46 43 byte

AllTrue[#==100&]/@Apply[Plus,{#,#},{1}]&

Seperti jawaban lain, hasilnya adalah

{False, False} untuk non-stokastik

{True, False} untuk stochastic kiri

{False, True} untuk stochastic kanan

{True, True} untuk stokastik ganda

Disimpan 3 byte dengan beralih ke bentuk operator dari AllTrue

A Simmons
sumber
Gunakan U + F3C7 (penggunaan pribadi) untuk\[Transpose]
u54112
Saya mempertimbangkannya tetapi berpikir itu kurang mencerahkan
A Simmons
Juga ada tambahan @di akhir
u54112
4

PHP, 104 byte

function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;}

Fungsi anonim yang menggema 0 => keduanya, 1 => kiri, 2 => kanan, 3 => keduanya.
Gunakan seperti:

php -r "$c=function($a){for($s=array_sum;$a[+$i];)$o|=$s($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;};$c(json_decode($argv[1]));" "[[4,8,15],[16,23,42],[80,69,43]]"

Versi program baris perintah dengan 114 byte:

for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;

Digunakan seperti:

 php -r "for($a=json_decode($argv[1]);$a[+$i];)$o|=($s=array_sum)($a[+$i])!=100|($s(array_column($a,+$i++))!=100)*2;echo$o;" "[[4,8,15],[16,23,42],[80,69,43]]"
pengguna59178
sumber
4

Python 2, 70 64 Bytes

Tidak ada yang gila di sini, hanya menggunakan splatting in zipuntuk memindahkan matriks :) Outputnya adalah sebagai berikut:

0 - not stochastic
1 - right stochastic
2 - left stochastic
3 - doubly stochastic

Dan inilah kodenya :)

k=lambda m:all(sum(x)==100for x in m)
lambda n:k(n)+2*k(zip(*n))
Kade
sumber
Apakah bintang dalam (* na kesalahan?
hhh
1
@hhh Tidak, itu splatoperatornya :) Intinya itulah yang membiarkan saya mengubah urutan matriks :)
Kade
4

C #, 205 203 183 byte

Golf:

int F(int[,]m){int x,i,j,r,c,e,w;x=m.GetLength(0);e=w=1;for(i=0;i<x;i++){r=c=0;for(j=0;j<x;j++){r+=m[i,j];c+=m[j,i];}if(r!=100)e=0;if(c!=100)w=0;}return e==1&&w==1?3:e==1?1:w==1?2:4;}

Tidak dikoleksi dengan komentar:

    int F(int[,] m)
    {
        //x - matrix size
        //i, j - loop control variables
        //r, c - row/column sum
        //e, w - east/west, pseudo-bool values indicate right/left stochastic
        int x, i, j, r, c, e, w;
        x = m.GetLength(0);
        e = w = 1;

        for (i = 0; i < x; i++)
        {
            r = c = 0;

            for (j = 0; j < x; j++)
            {
                r += m[i, j];
                c += m[j, i];
            }

            if (r != 100)
                e = 0;

            if (c != 100)
                w = 0;
        }

        return e == 1 && w == 1 ? 3 : e == 1 ? 1 : w == 1 ? 2 : 4;
    }

Kunci output: 1 - stokastik kanan 2 - stokastik kiri 3 - stokastik ganda 4 - tidak ada

Cobalah: http://rextester.com/PKYS11433

EDIT1: r=0;c=0;=>r=c=0;

EDIT2: Operator ternary bersarang. Kredit diberikan ke @Yodle.

paldir
sumber
2
if(e==1&&w==1)return 3;if(e==1)return 1;return w==1?2:4;Karena edan whanya bisa 1 atau 0, itu dapat diubah menjadi return w<<1|e;dan mendefinisikan kembali tidak ada == 0.
Tautan Ng
1
Anda dapat mempersingkat 30 Anda jika Anda mengubah beberapa ifpernyataan tersebut menjadi operasi ternary dan mengembalikan integer pada akhirnya. Idunno jika saya harus memposting solusi saya karena sangat mirip.
Yodle
@ LinkNg Sangat bagus. Saya tidak ingin menulis kode tanpa pemahaman. Saya tidak terbiasa dengan operator biner.
paldir
@Yodle Terima kasih, saya mengubah solusi saya. Jangan ragu untuk memposting bahkan jika itu sangat mirip.
paldir
3

JavaScript (ES6), 83 byte

a=>[a.some(a=>a.reduce((l,r)=>l-r,100)),a.some((_,i)=>a.reduce((l,a)=>l-a[i],100))]

Justru sebaliknya, ini tidak hanya menghasilkan hasil stoachistic kanan di sebelah kiri, tetapi boolean juga terbalik, sehingga output [false, true]masih berarti stoachistic kanan.

Neil
sumber
3

C # 6, 130 byte

using System.Linq;bool[]F(int[][]a)=>new[]{a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()==a.Length,a.All(x=>x.Sum()==100)};

{False, False}untuk non-stochastic
{True, False}untuk stochastic kiri
{False, True}untuk stochastic kanan
{True, True} untuk stochastic ganda

demo repl.it

Tidak disatukan

bool[]F(int[][]a)=>
    // Return new array of two bools. Array type is inferred from arguments
    new[]
    {
        // Left:
        // Count the no. of columns which sums up to 100
        a.Where((_,i)=>a.Select(x=>x[i]).Sum()==100).Count()
            // Then check if no. of such columns equal to total column count
            ==a.Length,
        // Right: Do all rows sum up to 100?
        // Can't use this trick for left because no overload of All() accept Func<TSource,int,bool> like Where() does
        a.All(x=>x.Sum()==100)
    };
Tautan Ng
sumber
3

Groovy, 57

{a={it.every{it.sum()==100}};[a(it),a(it.transpose())]}​

Keluaran

[0,0] jika tidak ada.

[1,0] jika benar

[0,1] jika dibiarkan.

[1,1] jika keduanya.

Guci Gurita Ajaib
sumber
2

Pip , 17 byte

Dalam putaran yang tidak terduga, pengajuan ini adalah fungsi.

{[h]=UQ$+_M[Zaa]}

Mengembalikan daftar dua 0/ 1nilai: [0 0]= tidak stokastik, [0 1]= stokastik kiri, [1 0]= stokastik kanan, [1 1]= stokastik dua kali lipat. Cobalah online!

Penjelasan

{               }  A function:
              a    Function argument (nested list)
           [Za ]   Create a list containing a's transpose and a
          M        Map this function to each of the above:
       $+_           Sum down the columns
     UQ              Get unique elements
 [h]=                If stochastic, the result should be [100]
DLosc
sumber
2

Dyalog APL , 16 byte

{∧/100=+/↑⍵(⍉⍵)}

{ } definisi fungsi langsung (alias "dfn"), adalah argumennya

⍵(⍉⍵) matriks di samping transposisinya

mencampurnya menjadi sebuah array 2 × n × n tunggal

+/ jumlah sepanjang sumbu terakhir, dapatkan matriks 2 × n

100= elemen mana yang 100 (booleans adalah 0 1)

∧/ "dan" -pangkas sepanjang sumbu terakhir, dapatkan 2 boolean untuk stokastik kiri, kanan

ngn
sumber
2

C ++ 14, 139 136 133 130 byte

-3 byte untuk s=M.size(), -3 byte untuk kembali dengan parameter referensi, -3 byte sebagai lambda yang tidak disebutkan namanya

[](auto M,int&r){int a,b,i,j,s=M.size();r=3;for(i=-1;++i<s;){for(j=-1,a=b=0;++j<s;a+=M[i][j],b+=M[j][i]);r&=(a==100)+2*(b==100);}}

Mengasumsikan input menjadi seperti vector<vector<int>>. Mengembalikan 3,2,1,0 untuk dua kali lipat, kiri, kanan, tidak ada stokastik.

Tidak Disatukan:

auto f=
[](auto M, int& r){
  int a,b,i,j,s=M.size();
  r=3;
  for(i=-1;++i<s;){
    for(j=-1,a=b=0;++j<s;
      a+=M[i][j],
      b+=M[j][i]);
    r&=(a==100)+2*(b==100);
  }
}
;
Karl Napf
sumber