OKlibrary  0.2.1.6
Subsets.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 21.1.2009 (Swansea) */
00002 /* Copyright 2009, 2010 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/DataStructures/Lisp/Lists.mac")$
00025 
00026 
00027 kill(f)$
00028 
00029 /* ************
00030    * Counting *
00031    ************
00032 */
00033 
00034 okltest_count_ksubsets_s(f) := block([a,b,c],
00035   for n : -2 thru 2 do
00036     assert(f({},n) = if n=0 then 1 else 0),
00037   assert(f({a,b,c},2) = 3),
00038   assert(okltest_count_ksubsets(buildq([f], lambda([n,k], f(setn(n),k)))) = true),
00039   true)$
00040 
00041 okltest_count_ksubsets(f) := (
00042   for n : -2 thru 2 do
00043     assert(f(0,n) = if n=0 then 1 else 0),
00044   assert(f(1,-1) = 0),
00045   assert(f(1,0) = 1),
00046   assert(f(1,1) = 1),
00047   assert(f(1,2) = 0),
00048   assert(f(4,2) = 6),
00049   true)$
00050 
00051 /* ****************************
00052    * Lexicographical ordering *
00053    ****************************
00054 */
00055 
00056 okltest_lex_ksubsets_l(f) := block(
00057   for i : 0 thru 5 do
00058     assert(f(setn(i),0) = [{}]),
00059   for i : 1 thru 5 do
00060     assert(f({},i) = []),
00061   for i : 2 thru 5 do
00062     for j : 0 thru 5 do
00063       assert(f(setn(i),j) = listify(powerset(setn(i),j))),
00064   true)$ 
00065 
00066 okltest_lex_ksubsets_ll(f) := block(
00067   assert(f([],0) = [{}]),
00068   assert(f([],1) = []),
00069   assert(f([3,2,1],1) = [{3},{2},{1}]),
00070   assert(f([4],2) = []),
00071   assert(f([4,1],2) = [{4,1}]),
00072   assert(f([3,1,2],2) = [{1,3},{2,3},{1,2}]),
00073   assert(f([1,4,3,2],2) = [{1,4},{1,3},{1,2},{3,4},{2,4},{2,3}]),
00074   assert(f([1,4,3,2],3) = [{1,4,3},{1,4,2},{1,3,2},{4,3,2}]),
00075   assert(f([1,4,3,2,5],3) = [{1,4,3},{1,4,2},{1,4,5},{1,3,2},{1,3,5},{1,2,5},{4,3,2},{4,3,5},{4,2,5},{3,2,5}]),
00076   assert(okltest_lex_ksubsets_l(buildq([f],lambda([M,k],f(listify(M),k)))) = true),
00077   if oklib_test_level=0 then return(true),
00078   assert(f(create_list(i,i,1,200000),1) = create_list({i},i,1,200000)),
00079   assert(length(f(create_list(i,i,1,200),2)) = binomial(200,2)),
00080   true)$
00081 
00082 okltest_rank_lex_ksubsets(f) := block(
00083   for i : 0 thru 5 do  
00084     assert(f({},i) = 1),
00085   for i : 1 thru 5 do
00086     assert(f({i},5) = i),
00087   assert(f({5,6}, 10) = 31),
00088   assert(f({1,3,4,7}, 15) = 81), 
00089   true)$
00090 
00091 okltest_unrank_lex_ksubsets(f) := block(
00092   for i : 0 thru 5 do
00093     assert(f(1, i, 0) = {}),
00094   for i : 1 thru 5 do
00095     assert(f(i,5,1) = {i}),
00096   assert(f(31,10,2) = {5,6}),
00097   assert(f(81,15,4) = {1,3,4,7}), 
00098   true)$
00099 
00100 
00101 /* ******************************
00102    * Colexicographical ordering *
00103    ******************************
00104 */
00105 
00106 okltest_colex_ksubsets_l(f) := block([cl],
00107   for i : 0 thru 5 do
00108     assert(f(setn(i),0) = [{}]),
00109   for i : 1 thru 5 do
00110     assert(f({},i) = []),
00111   assert(f(setn(4),3) = [{1,2,3},{1,2,4},{1,3,4},{2,3,4}]),
00112   cl : f(setn(7),3),
00113   for i : 3 thru 6 do block([rl],
00114     rl : f(setn(i),3),
00115     assert(take_elements(length(rl),cl) = rl)),
00116   true)$ 
00117 
00118 okltest_colex_ksubsets_ll(f) := block(
00119   assert(f([],0) = [{}]),
00120   assert(f([],1) = []),
00121   assert(f([3,2,1],1) = [{3},{2},{1}]),
00122   assert(f([4],2) = []),
00123   assert(f([4,1],2) = [{4,1}]),
00124   assert(f([3,1,2],2) = [{1,3},{2,3},{1,2}]),
00125   assert(f([1,4,3,2],2) = [{1,4},{1,3},{3,4},{1,2},{2,4},{2,3}]),
00126   assert(f([1,4,3,2],3) = [{1,4,3},{1,4,2},{1,3,2},{4,3,2}]),
00127   assert(f([1,4,3,2,5],3) = [{1,4,3},{1,4,2},{1,3,2},{4,3,2},{1,4,5},{1,3,5},{4,3,5},{1,2,5},{4,2,5},{3,2,5}]),
00128   assert(okltest_colex_ksubsets_l(buildq([f],lambda([M,k],f(listify(M),k)))) = true),
00129   if oklib_test_level=0 then return(true),
00130   assert(f(create_list(i,i,1,200000),1) = create_list({i},i,1,200000)),
00131   assert(length(f(create_list(i,i,1,200),2)) = binomial(200,2)),
00132   true)$
00133 
00134 okltest_rank_colex_ksubsets(f) := block(
00135   assert(f({}) = 1),
00136   for i : 1 thru 5 do
00137     assert(f({i}) = i),
00138   assert(f({5,6}) = 15),
00139   assert(f({1,3,4,7}) = 18), 
00140   true)$
00141 
00142 okltest_unrank_colex_ksubsets(f) := block(
00143   for i : 0 thru 5 do
00144     assert(f(1, i, 0) = {}),
00145   for i : 1 thru 5 do
00146     assert(f(i,5,1) = {i}),
00147   assert(f(15,10,2) = {5,6}),
00148   assert(f(18,15,4) = {1,3,4,7}), 
00149   true)$
00150 
00151