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, 2012 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 /* ************
00027    * Counting *
00028    ************
00029 */
00030 
00031 /* The number of subsets of size k of set M: */
00032 count_ksubsets_s(M,k) := binomial(length(M),k)$
00033 /* The number of k-subsets of {1,...,n} (n >= 0): */
00034 count_ksubsets(n,k) := binomial(n,k)$
00035 /* Prerequisites in both cases: k is an integer. */
00036 
00037 /* ****************************
00038    * Lexicographical ordering *
00039    ****************************
00040 */
00041 
00042 /* "Lexicographical order" treats a subset as a list, sorted in ascending
00043     order, and the next subset is obtained by increasing the right-most
00044     element which can be increased (while maintaing the subset- and the
00045     sortedness-condition), where upon increment at some position the elements
00046     to the right are reset to their smallest possible values.
00047 
00048     This corresponds to considering the list as a base-n representation
00049     of a number, where n is the size of the base-set, and to each digit
00050     1 is added, and then going to the next element means to add 1 to the
00051     number.
00052 */
00053 
00054 /* Produces a list of all k-subsets of M in lexicographical order: */
00055 lex_ksubsets_l(M,k) := listify(powerset(M,k))$
00056 /* This implementation assumes that the internal order of sets is given by
00057    lexicographical order.
00058    Alternatively we have
00059      lex_ksubsets_l(M,k) = lex_ksubsets_ll(listify(M),k)
00060                         = map(setify,
00061                               sort(map(listify,
00062                                        listify(powerset(M,k))), lex_lessp_l)).
00063 */
00064 /* More generally, now M is a repetition-free list, and the order is as
00065    specified by the order of M:
00066 */
00067 lex_ksubsets_ll(M,k) := reverse(colex_ksubsets_ll(reverse(M),k))$
00068 
00069 /* Returns the rank (position) of the subset S of {1,...,n} in the
00070    lexicographical enumeration of all |S|-subsets: */
00071 rank_lex_ksubsets(S,n) := block([L : listify(S), k : length(S)],
00072   binomial(n,k) - sum_l(map(binomial,n-L,create_list(k-i+1, i,1,k))))$
00073 /*  Note, for lex ordering, this does depend on n (as for instance {2,3,4}
00074     comes after {1,2,6}).
00075 */
00076 /* Explanation:
00077    This formula comes from considering how many subsets are *after*
00078    S in the order: Let S = {v_1, ..., v_k} (as above). The elements after S
00079    have either every element larger than v_1, these are binomial(n-v_1,k),
00080    plus the k-subsets containing v_1 as first element, which without
00081    this element are after {v_2, ..., v_k}. Via recursion then the
00082    formula is obtained.
00083 */
00084 
00085 /* Returns the 'x'th subset in the lexicographical enumeration of all
00086    k-subsets of {1,...,n}: */
00087 unrank_lex_ksubsets(x,n,k) := block([S : [], L : 1],
00088   x : binomial(n,k) - x,
00089   for i : 1 thru k do block([j : k-i+1],
00090     while binomial(n-L, j) > x do L : L + 1,
00091     S : endcons(L,S), x : x - binomial(n-L, j)
00092   ),
00093   return(setify(S)))$
00094 
00095 
00096 /* ******************************
00097    * Colexicographical ordering *
00098    ******************************
00099 */
00100 
00101 /* "Coexicographical order" treats a subset as a list, sorted in ascending
00102     order, and the next subset is obtained by increasing the left-most
00103     element which can be increased (while maintaing the subset- and the
00104     sortedness-condition), where upon increment at some position the elements
00105     to the left are reset to their smallest possible values.
00106 */
00107 
00108 /* Produces a list of all k-subsets of M in colexicographical order: */
00109 colex_ksubsets_l(M,k) := colex_ksubsets_ll(listify(M),k)$
00110 /* We have colex_ksubsets_l(M,k) =
00111    map(setify,sort(map(listify,listify(powerset(M,k))), colex_lessp_l)).
00112 */
00113 /* More generally, now M is a repetition-free list, and the order is as
00114    specified by the order of M:
00115 */
00116 colex_ksubsets_ll(M,k) := if k=0 then [{}]
00117  elseif k=1 then map(set,M)
00118  elseif k=2 then block([res : [], j : 1],
00119    for y in M do block([i : 1],
00120      for x in M unless i = j do (
00121        res : cons({x,y},res), i : i+1
00122      ),
00123      j : j+1
00124    ),
00125    return(reverse(res))
00126  )
00127  elseif emptyp(M) then [] else
00128   block([x : last(M), R : rest(M,-1)],
00129     append(colex_ksubsets_ll(R,k), add_element_l(x,colex_ksubsets_ll(R,k-1))))$
00130 
00131 /* Returns the rank (position) of the subset S of {1,...,n} in the
00132    colexicographical enumeration of all |S|-subsets: */
00133 rank_colex_ksubsets(S) := block([L : listify(S)],
00134   sum_l(map(binomial,L-1,create_list(i,i,1,length(L)))) + 1)$
00135 /*  Note, for colex ordering, this does not depend on n. */
00136 
00137 /* Explanation:
00138    This formula comes from considering how many subsets are before
00139    S in the order: Let S = {v_1, ..., v_k} (k = length(S)) be sorted
00140    in ascending order. Now the elements before S are those k-subsets with
00141    elements all smaller than v_k, these are binomial(v_k-1,k), plus the
00142    k-subsets containing v_k as last element, and without this last element
00143    being before {v_1, ..., v_{k-1}}. The formula is obtained then by
00144    recursion.
00145 */
00146 
00147 /* Returns the 'x'th subset in the colexicographical enumeration of all
00148    k-subsets of {1,...,n}. */
00149 unrank_colex_ksubsets(x,n,k) := block([S : [], L : n],
00150   x : x - 1,
00151   for i : k thru 1 step -1 do (
00152     while binomial(L-1,i) > x do L : L - 1,
00153     S : cons(L,S), x : x - binomial(L-1, i)
00154   ),
00155   return(setify(S)))$
00156