OKlibrary  0.2.1.6
InclusionExclusion.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 3.2.2008 (Swansea) */
00002 /* Copyright 2008, 2013 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/Generators/Pigeonhole.mac")\$
00025
00026
00027 kill(f)\$
00028
00029 /* Testing whether f computes the probability of satisfying assignments for
00030    clause-sets */
00031 okltest_satprob(f) := block([F],
00032   assert(f({}) = 1),
00033   assert(f({{}}) = 0),
00034   assert(f({{1}}) = 1/2),
00035   assert(f({{1},{}}) = 0),
00036   assert(f({{1},{-1}}) = 0),
00037   assert(f({{1,2}}) = 3/4),
00038   assert(f({{1,2},{2,3}}) = 5/8),
00039   assert(f({{1,2},{-1,3}}) = 1/2),
00040   assert(f({{1,2},{3,4}}) = 9/16),
00041   assert(f({{1},{2,3},{-3,4}}) = 1/4),
00042   for n : 0 thru 10 do
00043     assert(f({setn(n)}) = 1 - 2^(-n)),
00044   if oklib_test_level = 0 then return(true),
00045   for m : 0 thru 3 do
00046    for n : 0 thru 3 do
00047     assert(f(weak_php_cs(m,n)) = satprob_weak_php(m,n)),
00048   true)\$
00049
00050 /* Testing whether f computes the list of approximations of the
00051     probability of satisfying assignments via inclusion-exclusion */
00052 okltest_satprob_approxlist(f) := block([F],
00053   assert(f({}) = [1]),
00054   assert(f({{}}) = [1,0]),
00055   assert(f({{1}}) = [1,1/2]),
00056   assert(f({{1},{-1}}) = [1,0]),
00057   assert(f({{1},{2}}) = [1,0,1/4]),
00058   assert(f({{1,2},{-2,3},{2,3}}) = [1,1/4,3/8]),
00059   assert(f({{1,2},{-2,3},{-3},{-1}}) = [1,-1/2,0]),
00060   assert(f({{1,2},{-2,3},{2,-3},{1,-3}}) = [1,0,3/8,2/8]),
00061   if oklib_test_level = 0 then return(true),
00062   block([oklib_test_level : 0],
00063     okltest_satprob(buildq([f],lambda([F],last(f(F)))))),
00064   true)\$
00065
00066 okltest_satprob_hitting(f) := (
00067   assert(f({}) = 1),
00068   assert(f({{}}) = 0),
00069   assert(f({{1}}) = 1/2),
00070   assert(f({{-1}}) = 1/2),
00071   assert(f({{1},{-1}}) = 0),
00072   assert(f({{1,2}}) = 3/4),
00073   assert(f({{1,2},{-1,2}}) = 1/2),
00074   assert(f({{1,2},{-1,2}, {1,-2}}) = 1/4),
00075   assert(f({{},{1},{1,2}}) = 1 - 7/4),
00076   true)\$
00077
00078
```