OKlibrary  0.2.1.6
SignVectors.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 13.7.2008 (Swansea) */
00002 /* Copyright 2008, 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/DataStructures/Lisp/Lists.mac")$
00024 
00025 
00026 /* A "sign vector" is a list with entries in {-1,0,+1}.
00027 */
00028 
00029 /* Translating a sign vector to a clause. */
00030 sgnv2c(S) := disjoin(0,setify(map("*", S, create_list(i,i,1,length(S)))))$
00031 /* Given a set of sign vectors of the same length, compute the corresponding
00032    formal clause-set: */
00033 sgnvs2cs(S) := [
00034  if emptyp(S) then {} else setn(length(choose_element(S))),
00035  map(sgnv2c,S)]$
00036 
00037 /* The sign vector of a vector: */
00038 lsignum(L) := map(signum,L)$
00039 
00040 /* Given a list V of vectors (same length), determine the sign vectors
00041    occurring for linear combinations with coefficients from -N to N: */
00042 span_sgnvs(V,N) := block([coef : setmn(-N,N), n : length(V)],
00043  map(lambda([c],lsignum(apply("+", c * V))), 
00044        uaapply(cartesian_product,create_list(coef,i,1,n))))$
00045 /* Of course, the question is, how large needs N to be, and can we do
00046    it more efficiently?
00047    If N is large enough, and we obtain all sign vectors, then we have an
00048    example for an oriented matroid.
00049 */
00050 /* The corresponding (standardised) formal clause-set: */
00051 span_fcs_sgnvs(V,N) := sgnvs2cs(span_sgnvs(V,N))$
00052 
00053 /* Example 5.2 (corrected) from [Bachem, Kern; Linear Programming Duality]:
00054 a : [1,0,1,1];
00055 b : [0,1,-1,-2];
00056 FF : span_fcs_sgnvs([a,b],3);
00057 assert(length(FF[2]) = 17);
00058 
00059 The orthogonal complement is given by:
00060 c : [-1,1,1,0];
00061 d : [0,1,-1,1];
00062 CFF : span_fcs_sgnvs([c,d],3);
00063 assert(length(CFF[2]) = 17);
00064 
00065 assert(all_aut_cs(FF[2]) = CFF[2]);
00066 assert(all_aut_cs(CFF[2]) = FF[2]);
00067 
00068 */
00069