Quandle Quandary Episode I: Identifikasi Finite Quandles

20

Tulis program yang akan menentukan apakah matriks yang diberikan merepresentasikan quandle. Sebuah quandle adalah satu set dilengkapi dengan single (non-komutatif, non-asosiatif) operasi ◃ yang mematuhi aksioma-aksioma berikut:

  • Operasi ditutup, artinya a◃b = celemen selalu dari himpunan jika adan bmerupakan elemen himpunan.
  • Operasi ini kanan-diri distributif: (a◃b)◃c = (a◃c)◃(b◃c).
  • Operasi ini dapat dibagi kanan: Untuk setiap pasangan yang dipilih adan b, ada satu yang unik csehinggac◃a = b
  • Operasi idempoten: a◃a = a

Quandle terbatas dapat direpresentasikan sebagai matriks persegi. Di bawah ini adalah contoh dari quandle order-5 ( sumber ).

0 0 1 1 1
1 1 0 0 0
3 4 2 4 3
4 2 4 3 2
2 3 3 2 4

Nilai yang terletak di baris ke-n dan kolom ke-m (diindeks 0) adalah nilai dari n◃m. Misalnya, dalam quandle ini, 4◃1 = 3. Beberapa properti quandle mudah dilihat dari matriks ini:

  • Ditutup karena hanya nilai 0-4 yang muncul dalam matriks 5x5 ini.
  • Ini idempoten karena matriks diagonal adalah 0 1 2 3 4
  • Ini dapat dibagi kanan karena tidak ada kolom yang berisi nilai duplikat. (Baris bisa, dan biasanya akan.)

Properti dari distribusi-diri-kanan lebih sulit untuk diuji. Mungkin ada jalan pintas, tetapi metode paling sederhana adalah untuk beralih pada setiap kombinasi yang mungkin dari tiga indeks untuk memverifikasi itu m[m[a][b]][c] = m[m[a][c]][m[b][c]].

Memasukkan

Input akan menjadi daftar baris matriks persegi, menggunakan indeks-0 atau indeks-1 (pilihan Anda). Setiap entri akan menjadi satu digit angka dari 0ke 8(atau 1sampai 9). Saya akan fleksibel pada format input. Beberapa format yang dapat diterima meliputi:

  • Format bahasa Anda yang paling alami untuk matriks atau daftar, seperti [[0 0 0][2 1 1][1 2 2]]atau (0,0,0,2,1,1,1,2,2).
  • Daftar nilai yang dibatasi oleh spasi, baris baru, koma, dll.
  • String tunggal yang terdiri dari semua nilai yang disatukan, seperti 000211122.

Anda juga diperbolehkan mengambil transpos matriks sebagai input (menukar baris dengan kolom). Pastikan untuk menyatakan ini dalam jawaban Anda.

Keluaran

Nilai kebenaran / falsey tunggal yang menunjukkan status matriks sebagai quandle.

Contoh pertengkaran

0

0 0
1 1

0 0 0
2 1 1
1 2 2

0 0 1 1
1 1 0 0
3 3 2 2
2 2 3 3

0 3 4 1 2
2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4

Contoh non-pertengkaran

tidak tertutup

1

0 0 0
2 1 1
1 9 2

tidak self-distributive

0 0 1 0
1 1 0 1
2 3 2 2
3 2 3 3

(3◃1)◃2 = 2◃2 = 2
(3◃2)◃(1◃2) = 3◃0 = 3

tidak bisa dibagi kanan

0 2 3 4 1
0 1 2 3 4
3 4 2 2 2
3 3 3 3 3
4 1 1 1 4

0 1 2 3
3 1 2 0
3 1 2 3
0 1 2 3

tidak idempoten

1 1 1 1
3 3 3 3
2 2 2 2
0 0 0 0

2 1 0 4 3
3 4 2 0 1
4 2 1 3 0
1 0 3 2 4
0 3 4 1 2
PhiNotPi
sumber
1
Kata "matrix" menyesatkan, karena ini tidak ada hubungannya dengan aljabar linier. "Table" akan lebih baik (atau mungkin "Cayley table", tapi saya pikir itu hanya cocok untuk grup).
Peter Taylor

Jawaban:

7

Python 2 , 104 103 102 byte

t=input();e=enumerate
[0%(a==A[a]in B>C[B[a]]==t[C[b]][C[a]])for(a,A)in e(t)for(b,B)in e(t)for C in t]

Input dialihkan. Output melalui kode keluar, jadi 0 (sukses) benar dan 1 (gagal) salah.

Cobalah online!

Bagaimana itu bekerja

e(t)mengembalikan baris disebutkan input matriks t - yang mewakili operator - sebagai (indeks, baris) pasang. for(a,A)in e(t), misalnya, mengulangi ini, menyimpan indeks dalam a dan baris itu sendiri dalam A , jadi Amenjadi jalan pintas untuk t[a].

Antara yang pertama,, for(b,B)in e(t)dan for C in t, kita mengulangi semua kemungkinan tupel yang dipesan (a, b, c) dalam kekuatan Cartesian t 3 .

Untuk masing-masing tupel ini, kami mengevaluasi ekspresi

0%(a==A[a]in B>C[B[a]]==t[C[b]][C[a]])

Nilai Boolean yang dikurung adalah False jika dan hanya jika satu atau lebih dari perbandingan individu berikut melakukan hal yang sama.

  • a==A[a]akan gagal (untuk beberapa nilai a ) iff tidak idempoten.

  • A[a]in Bakan gagal jika B tidak mengandung semua indeks A .

    Karena A memiliki n indeks dan B memiliki n elemen, non-kegagalan berarti bahwa elemen B cocok dengan indeks A , jadi tertutup dan dapat dibagi kanan.

  • B>C[B[a]] adalah tautologi, karena Python 2 dianggap angka "lebih kecil" daripada iterables.

  • C[B[a]]==t[C[b]][C[a]]akan gagal untuk beberapa nilai jika tidak self-distributive.

Jika salah satu dari perbandingan mengembalikan False , ekspresi (0%...)akan melempar ZeroDivisionError . Juga, jika tidak ditutup A[a]atau C[b]mungkin juga melempar IndexError . Dalam kedua kasus, program keluar dengan kode status 1 (gagal).

Jika semua tes lulus, program akan keluar secara normal dengan kode status 0 (berhasil).

Dennis
sumber
6

Haskell, 100 byte

Jawaban ini menggunakan input yang dialihkan .

q m=and$(elem<$>v<*>m)++[a#a==a&&a#b#c==a#c#(b#c)|a<-v,b<-v,c<-v]where v=[0..length m-1];i#j=m!!j!!i

Sepertinya saya tidak bisa menggunakan penjaga pola untuk mengikat operator infiks, jadi saya gunakan wheredalam kasus ini.

(Versi pertama adalah 108 byte tetapi gagal tes idempotensi, versi tetap adalah 120 byte, versi kemudian memiliki 108, 103 dan 98 byte tetapi saya harus menyadari berkat @nimi bahwa mereka semua salah: tentu saja saya perlu melakukan yang benar- uji pembagian (yang menyiratkan penutupan) sebelum melakukan !!operasi berbahaya , tapi saya masih bisa menggunakan sebagian besar ide golf saya nanti dan dengan satu lagi, itu 102 byte, sekarang ditingkatkan dengan mengubah urutan operan #(yang lebih baik pula untuk mengkompensasi transposisi) untuk memanfaatkan asosiasi yang lebih baik ke kiri)

Gunakan seperti ini:

*Main> q [[0,1,2,3],[0,1,3,2],[1,0,2,3],[0,1,2,3]]
False
Sievers Kristen
sumber
4

Python 2 , 138 byte

def f(m):R=range(len(m));return all(m[i][i]==i<set(zip(*m)[i])==set(R)>m[m[j][k]][i]==m[m[j][i]][m[k][i]]for i in R for j in R for k in R)

m adalah daftar daftar bilangan bulat.

Cobalah online!

Lynn
sumber
4

JavaScript (ES6), 150 byte

a=>!(a.some((b,i)=>b[i]-i)|a.some(b=>[...new Set(b)].sort()+''!=[...b.keys()])||a.some((_,i)=>a.some((_,j)=>a.some((b,k)=>b[a[j][i]]-a[b[j]][b[i]]))))

Mengambil input sebagai array array kolom bilangan bulat.

Neil
sumber
3

Mathematica, 122 byte

(n_±m_:=#[[m,n]];#&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]&&And@@Flatten@Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}])&

Fungsi murni mengambil array 2D bilangan bulat (1-diindeks) sebagai input, dengan baris dan kolom dibalik dari konvensi dalam pertanyaan, dan mengembalikan Trueatau False. Baris pertama mendefinisikan operasi infiks biner n_±m_sebagai operasi quandle.

Untuk lx larray, tertutup dan dapat dibagi kanan setara dengan setiap baris (dalam kasus saya) menjadi beberapa permutasi {1, ..., l}, dan idempoten setara dengan diagonal utama yang tepat {1, ..., l}. Jadi #&@@Union[Sort/@#]==Range@l==Array[#±#&,l=Length@#]mendeteksi untuk tiga kondisi ini. (Penggunaan di Sort/@#sini adalah mengapa saya memilih untuk menukar baris dan kolom.)

Untuk distribusi-benar, kami benar-benar memeriksa semua kemungkinan menggunakan Array[±##2±#==(#2±#)±(#3±#)&,{l,l,l}]). (Catatan yang ±##2±#secara otomatis diperluas ke (#2±#3)±#, karena ##2mewakili urutan argumen kedua dan ketiga untuk fungsi murni tiga variabel yang sedang diatur.) Kemudian &&And@@Flatten@periksa apakah setiap tes tunggal dilewati. Untuk beberapa pertengkaran yang tidak tertutup, kesalahan mungkin terjadi ketika mencoba mengakses bagian dari matriks yang tidak ada, tetapi jawaban yang benar masih dikembalikan.

Greg Martin
sumber
±m__:=#[[m]];Kupikir. Dan ada Diagonalbuilt-in. Dan ±yang tersisa-asosiatif sehingga Anda dapat menggunakan #2±#±(#3±#), tetapi jika aku tidak melakukan kesalahan maka itu lebih pendek untuk menetapkan kembali #ke #3dan melakukan #±#2±#3==#±#3±±##2&. Dan itu juga harus mungkin menggantikan seluruh Flatten@bagian dengan(...&~Array~{l,l,l}<>"")
Martin Ender
Saya ingin tahu apakah Anda harus pindah l=Lengthke Range@lkarena itu yang harus dievaluasi dulu, jadi jika Anda menggunakan fungsi berulang kali, saya pikir Rangemasih mendapatkan yang sebelumnya l, bukan?
Martin Ender
0

C ++ 14, 175 byte

Sebagai lambda tanpa nama, dengan asumsi nseperti std::vector<std::vector<int>>dan kembali melalui parameter referensi. 0 salah, semuanya benar.

#define F(x);for(x=-1;++x<s;){
[](auto m,int&r){int s=r=m.size(),a,b,c F(a)auto A=m[a];r*=s==A.size()&&A[a]==a;int u=0 F(b)u|=1<<m[b][a];r*=A[b]<s F(c)r*=m[A[b]][c]==m[A[c]][m[b][c]];}}r*=!(u-(1<<s)+1);}}

Tidak digabungkan dan digunakan:

#include<vector>
#include<iostream>

auto f=
#define F(x);for(x=-1;++x<s;){
[](auto m,int&r){
 int s=r=m.size(),a,b,c
 F(a)
  auto A=m[a];               //shortcut for this row
  r*=s==A.size()&&A[a]==a;   //square and idempotet
  int u=0                    //bitset for uniqueness in col
  F(b)
   u|=1<<m[b][a];            //count this item
   r*=A[b]<s                 //closed
   F(c)
    r*=m[A[b]][c]==m[A[c]][m[b][c]];
   }
  }
  r*=!(u-(1<<s)+1);          //check right-divisibility
 }
}
;

int main(){
 int r;
 std::vector<std::vector<int>>
  A = {
   {0, 0, 1, 1},
   {1, 1, 0, 0},
   {3, 3, 2, 2},
   {2, 2, 3, 3},
  },
  B = {
   {0, 2, 3, 4, 1},
   {0, 1, 2, 3, 4},
   {3, 4, 2, 2, 2},
   {3, 3, 3, 3, 3},
   {4, 1, 1, 1, 4},
  };
 f(A,r);
 std::cout << r << "\n";
 f(B,r);
 std::cout << r << "\n";
}
Karl Napf
sumber
Sarankan int a,b,c,u,s=r=m.size()Falih-alih int s=r=m.size(),a,b,c F, u=0;r*=s==A.size()&&a==A[a]Falih-alih r*=s==A.size()&&A[a]==a;int u=0 F, r*=s>A[b]Falih- alih r*=A[b]<s Fdan ~u+(1<<s)bukannyau-(1<<s)+1
ceilingcat