OKlibrary  0.2.1.6
Enumeration.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 14.1.2009 (Swansea) */
00002 /* Copyright 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/BasicNotions.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Homomorphisms.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")$
00030 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00031 
00032 
00033 /* *********************
00034    * Basic enumeration *
00035    *********************
00036 */
00037 
00038 /* All groupoids of order n, as Maxima matrices: */
00039 all_grd2m(n) := all_m(n,n,create_list(i,i,1,n))$
00040 all_grd(n) := map(m2grd,all_grd2m(n))$
00041 
00042 
00043 /* ************
00044    * Counting *
00045    ************
00046 */
00047 
00048 number_grd(n) := pow(n, n^2)$
00049 number_iso_grd(n) := if n<=1 then 1 elseif n=2 then 10 elseif n=3 then 3330
00050   else unknown$
00051 number_isot_grd(n) := if n<=1 then 1 elseif n=2 then 5 elseif n=3 then 139
00052   else unknown$
00053 
00054 /* Commutativity: */
00055 number_cgrd(n) := pow(n, n*(n+1)/2)$
00056 number_iso_cgrd(n) := if n<=1 then 1 elseif n=2 then 4 elseif n=3 then 129
00057   else unknown$
00058 
00059 /* Unit element: */
00060 number_ugrd(n) := n * n^((n-1)^2)$
00061 number_iso_ugrd(n) := if n<=1 then n elseif n=2 then 2 elseif n=3 then 45
00062   else unknown$
00063 
00064 number_cugrd(n) := n * pow(n, n*(n-1)/2)$
00065 number_iso_cugrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 15
00066   else unknown$
00067 
00068 /* Idempotent: */
00069 number_igrd(n) := pow(n, n^2-n)$
00070 number_iso_igrd(n) := if n<=1 then 1 elseif n=2 then 3 elseif n=3 then 138
00071   else unknown$
00072 
00073 number_iugrd(n) := n * n^((n-1)^2 - (n-1))$
00074 number_iso_iugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 6
00075   else unknown$
00076 
00077 number_cigrd(n) := pow(n, n*(n-1)/2)$
00078 number_iso_cigrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 7
00079   else unknown$
00080 
00081 number_ciugrd(n) := pow(n, n*(n+1)/2-2*n+2)$
00082 number_iso_ciugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 2
00083   else unknown$
00084 
00085 /* Null element: */
00086 number_ngrd(n) := n * n^((n-1)^2)$
00087 number_iso_ngrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 45
00088   else unknown$
00089 
00090 number_cngrd(n) := n * pow(n,n*(n-1)/2)$
00091 number_iso_cngrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 15
00092   else unknown$
00093 
00094 number_ingrd(n) := n * n^((n-1)*(n-2))$
00095 number_iso_ingrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 6
00096   else unknown$
00097 
00098 number_nugrd(n) := if n <= 1 then n else n*(n-1)*n^((n-2)^2)$
00099 number_iso_nugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 3
00100   else unknown$
00101 
00102 number_cingrd(n) := n^(n*(n+1)/2-2*n+2)$
00103 number_iso_cingrd(n) := if n<=1 then 1 elseif n=2 then 2 elseif n=3 then 2
00104   else unknown$
00105 
00106 number_cnugrd(n) := if n<=1 then n else n*(n-1)*n^((n-1)*(n-2)/2)$
00107 number_iso_cnugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 3
00108   else unknown$
00109 
00110 number_inugrd(n) := if n <= 1 then n else n*(n-1)*n^((n-2)*(n-3))$
00111 number_iso_inugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 1
00112   else unknown$
00113 
00114 number_cinugrd(n) := if n<=1 then n else n*(n-1)*n^((n-2)*(n-3)/2)$
00115 number_iso_cinugrd(n) := if n<=1 then 1 elseif n=2 then 1 elseif n=3 then 1
00116   else unknown$
00117 
00118 
00119 /* ***********************************
00120    * Enumerating isomorphism classes *
00121    ***********************************
00122 */
00123 
00124 /* The isomorphism classes of the set of all standardised groupoids of order n
00125    (with base set {1,...,n}); the results are directly represented as
00126    Maxima matrices. (Given such a matrix M, the corresponding groupoid
00127    is obtained by scom2grd(m2scom(M)).)
00128 */
00129 /* First the direct computation: */
00130 all_isomorphism_classes_bydef_grd(n) := 
00131  map(lambda([C], map(lambda([G], lmscom2m(grd2scom(G))), C)),
00132   equiv_classes(
00133     setify(all_grd(n)),
00134     is_isomorphic_bydef_grd))$
00135 /* Now the more efficient computation by actively computing the
00136    equivalence classes.
00137 */
00138 /* First an auxiliary function, which for a given set S of groupoids
00139    represented as Maxima matrices computes the complete isomorphism
00140    classes of these matrices (w.r.t. all groupoids of order n).
00141    Inherits: the set all_perm of permutations of N
00142    (as functions).
00143 */
00144 all_isomorphism_classes_actively_sm_grd(S) := block(
00145  [result : []],
00146   while not emptyp(S) do block(
00147    [M : m2grd(choose_element(S)), C],
00148     /* C is the isomorphism class of M */
00149     C : setify(map(lambda([f], grd2m(transport_grd(M,f))), all_perm)),
00150     S : setdifference(S, C),
00151     result : cons(C,result)
00152   ),
00153   setify(result))$
00154 /* Now the full function (running through all groupoids of order n):
00155 */
00156 all_isomorphism_classes_actively_grd(n) := block(
00157  [N : create_list(i,i,1,n), all_perm],
00158   all_perm : map(lambda([p], lambda_array(l2ary(p))),
00159            listify(permutations(N))), /* all permutations */
00160   all_isomorphism_classes_actively_sm_grd(setify(all_m(n,n,N))))$
00161 
00162 
00163 /* *********************************
00164    * Enumerating isotopism classes *
00165    *********************************
00166 */
00167 
00168 /* Now all isotopy classes (a rougher equivalence relation than isomorphism):
00169 */
00170 /* Perhaps should be better also organised as above. XXX */
00171 all_isotopism_classes_actively_grd(n) := block(
00172  [N : create_list(i,i,1,n), G, LP, LP3, result : []],
00173   G : setify(all_m(n,n,N)), /* all groupoids */
00174   LP : map(lambda([p], lambda_array(l2ary(p))),
00175            listify(permutations(N))), /* all permutations */
00176   LP3 : cartesian_product_l([LP,LP,LP]),
00177   while not emptyp(G) do block(
00178    [M : m2grd(choose_element(G)), C],
00179     /* C is the isomorphism class of M */
00180     C : setify(map(lambda([F], 
00181                  grd2m(transport3_grd(M,F[1],F[2],F[3]))), LP3)),
00182     G : setdifference(G, C),
00183     result : cons(C,result)
00184   ),
00185   setify(result))$
00186 
00187 /* Creating all isotopy classes, which are further subdivided into
00188    isomorphism classes:
00189 */
00190 all_isotopismisomorphism_classes_actively_grd(n) := block(
00191  [all_perm : map(lambda([p], lambda_array(l2ary(p))),
00192            listify(permutations(create_list(i,i,1,n))))],
00193   map(all_isomorphism_classes_actively_sm_grd,
00194       all_isotopism_classes_actively_grd(n)))$
00195 
00196 
00197 /* ********************
00198    * Evaluation tools *
00199    ********************
00200 */
00201 
00202 /* Given a set S of isomorphism classes of Maxima-matrices representing
00203    groupoids, select those classes fulfilling all the properties of the
00204    list P:
00205 */
00206 selectclasses_m2grd(S,P) := subset(S, lambda([C], 
00207   block([M : m2grd(first_element(C))],
00208     every_s(lambda([p], p(M)), P))))$
00209