OKlibrary  0.2.1.6
Permutations.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 15.12.2009 (Swansea) */
00002 /* Copyright 2009, 2010, 2011 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 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ClauseSets/PartialAssignments.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ClauseSets/BasicOperations.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/FiniteFunctions/Permutations.mac")$
00027 
00028 
00029 kill(f)$
00030 
00031 /* *************************************
00032    * Permutations as boolean functions *
00033    *************************************
00034 */
00035 
00036 okltest_trans2dnffcl(f) := (
00037   assert(okltest_perm2dnffcl(f) = true),
00038   assert(f([1,1]) = [[1,2],[{-1,-2},{1,-2}]]),
00039   assert(f([2,1,2,3]) = [[1,2,3,4],[{-1,-2,-3,4},{-1,2,-3,-4},{1,-2,-3,4},{1,2,3,-4}]]),
00040   true)$
00041 
00042 okltest_trans2dnffcs(f) := (
00043   assert(okltest_perm2dnffcs(f) = true),
00044   true)$
00045 
00046 okltest_perm2dnffcl(f) := (
00047   assert(f([1]) = [[],[{}]]),
00048   assert(f([1,2]) = [[1,2],[{-2,-1},{1,2}]]),
00049   assert(f([2,1]) = [[1,2],[{-1,2},{1,-2}]]),
00050   assert(f([1,2,3,4]) = [[1,2,3,4],[{-4,-3,-2,-1},{-3,-1,2,4},{-4,-2,1,3},
00051     {1,2,3,4}]]),
00052   assert(f([2,1,4,3]) = [[1,2,3,4],[{-3,-2,-1,4},{-4,-3,-1,2},{-2,1,3,4},
00053     {-4,1,2,3}]]),
00054   assert(f([2,4,1,3]) = [[1,2,3,4],[{-1,-2,-3,4},{-1,2,3,4},{1,-2,-3,-4},{1,2,3,-4}]]),
00055   for k : 0 thru 5 do block([m : 2^k, P, FF],
00056     P : create_list(i,i,1,m),
00057     FF : f(P),
00058     assert(FF[1] = create_list(i,i,1,2*k)),
00059     assert(length(FF[2]) = m),
00060     assert(setify(FF[2]) = setify(map(union, all_tass_l(setn(k)), all_tass_l(setmn(k+1,2*k)))))
00061   ),
00062   assert(okltest_perm2dnffcs(buildq([f], lambda([P], fcl2fcs(f(P))))) = true),
00063   true)$
00064 
00065 okltest_perm2dnffcs(f) := (
00066   assert(f([1]) = [{},{{}}]),
00067   assert(f([1,2]) = [{1,2},{{-2,-1},{1,2}}]),
00068   assert(f([2,1]) = [{1,2},{{-1,2},{-2,1}}]),
00069   assert(f([1,2,3,4]) = [{1,2,3,4},{{-4,-3,-2,-1},{-3,-1,2,4},{-4,-2,1,3},
00070     {1,2,3,4}}]),
00071   assert(f([2,1,4,3]) = [{1,2,3,4},{{-3,-2,-1,4},{-4,-3,-1,2},{-2,1,3,4},
00072     {-4,1,2,3}}]),
00073   /* XXX */
00074   true)$
00075 
00076 
00077 okltest_trans2cnffcs(f) := (
00078   assert(okltest_perm2cnffcs(f) = true),
00079   true)$
00080 
00081 okltest_perm2cnffcs(f) := (
00082   assert(f([1]) = [{},{}]),
00083   assert(f([1,2]) = [{1,2},{{-2,1},{-1,2}}]),
00084   assert(f([2,1]) = [{1,2},{{-2,-1},{1,2}}]),
00085   assert(f([1,2,3,4]) = [{1,2,3,4},{{-4,-3,-2,1},{-4,-3,-1,2},{-4,-3,1,2},
00086     {-4,-2,-1,3},{-4,-1,2,3},{-4,1,2,3},{-3,-2,-1,4},{-3,-2,1,4},{-3,1,2,4},
00087     {-2,-1,3,4},{-2,1,3,4},{-1,2,3,4}}]),
00088   /* XXX */
00089   true)$
00090 
00091 okltest_m2dnffcl(f) := (
00092   assert(f(matrix()) = [[],[{}]]),
00093   assert(f(matrix([0])) = [[1,2],[{-1,-2},{1,-2}]]),
00094   assert(f(matrix([1])) = [[1,2],[{-1,-2},{1,2}]]),
00095   assert(f(matrix([0,0],[0,0])) = [[1,2,3,4],[{-1,-2,-3,-4},{-1,2,-3,-4},{1,-2,-3,-4},{1,2,-3,-4}]]),
00096 assert(f(matrix([1,0],[0,1])) = [[1,2,3,4],[{-1,-2,-3,-4},{-1,2,-3,4},{1,-2,3,-4},{1,2,3,4}]]),
00097   assert(okltest_m2dnffcs(buildq([f], lambda([M], fcl2fcs(f(M))))) = true),
00098   true)$
00099 
00100 okltest_m2dnffcs(f) := (
00101   assert(f(matrix()) = [{},{{}}]),
00102 assert(f(matrix([1,1],[1,1])) = [{1,2,3,4},{{-1,-2,-3,-4},{-1,2,3,4},{1,-2,3,4},{1,2,-3,-4}}]),
00103   true)$
00104 
00105 okltest_m2cnffcs(f) := (
00106   assert(f(matrix()) = [{},{}]),
00107   /* XXX */
00108   true)$
00109