OKlibrary  0.2.1.6
RandomBooleanFunctions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 29.1.2011 (Swansea) */
00002 /* Copyright 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/Hypergraphs/Lisp/SetSystems.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Generators/Generators.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Generators/RandomClauseSets.mac")$
00025 
00026 
00027 /* For a set S returns a random subset where each subset has the same
00028    probability of being chosen (namely 1/2^length(S)).
00029    Prerequisite:: S does not contain 0. */
00030 /* TODO: Move somewhere more appropriate. */
00031 random_subset(S) := 
00032   disjoin(0, setify(listify(S) * create_list(random(2),i,1,length(S))))$
00033 
00034 /* In the following, "random" means that each function chosen
00035    has equal probability of being chosen (uniform distribution). */
00036 
00037 /* Computes a random boolean function in n variables as a full CNF: */
00038 random_bf_fcs(n) := [setn(n),random_subset(full_cs(n))]$
00039 output_random_bf_fcs(n,filename_) :=
00040   output_fcs(
00041     sconcat("Random boolean function in ", n, " variables."),
00042     random_bf_fcs(n),
00043     sconcat(filename_))$
00044 output_random_bf_fcs_stdname(n) :=
00045   output_random_bf_fcs(n,sconcat("Random_bf_",n,".cnf"))$
00046 
00047 /* Computes a random balanced boolean function in n variables as a full CNF: */
00048 random_bal_bf_fcs(n) :=
00049   [setn(n),setify(random_k_sublist_l(listify(full_cs(n)),2^(n-1)))]$
00050 /* A boolean function is balanced if it has the same number
00051    of true points as false points. */
00052