OKlibrary  0.2.1.6
Sequences.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 22.4.2010 (Swansea) */
00002 /* Copyright 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/DataStructures/Lisp/Lists.mac")$
00023 
00024 /* ****************
00025    * Transformers *
00026    ****************
00027 */
00028 
00029 /* 
00030   Transforming an initial list T of transversal vdW-numbers to transversal
00031   vdw-numbers, or transforming a "steplist" of independence numbers into a
00032   list of independence numbers.
00033   If T contains non-integer values, then the list is cut off at
00034   the first such occurrence.
00035   The list of transversal vdw-numbers starts with n=0.
00036 
00037   Given a sequence T for fixed k, containing vanderwaerden_{m+1}([2]_m, k) for
00038   m = 0, ..., (or the steplist as explained below), one obtains
00039   tau_arithprog(k,n) for n=0, ... by running through m=0,1,..., and observing
00040   when first the value x=T[m+1] is strictly greater than n --- for this m we
00041   have tau_arithprog(k,n) = m.
00042 
00043   So transform_threshold_l(T) is the list [t_0,t_1, ..., t_p]
00044   of non-decreasing natural numbers t_i >= 0, where t_i is the smallest
00045   0 <= m <= length(T) such that T'[m+1] > i, and where T' is obtained from
00046   T by adding an element to the end which is bigger by one than the last
00047   element of T (this yields one more correct value in the result list, since
00048   the numbers of T are strictly increasing).
00049   In other words, transform_threshold_l(T) contains T[1] 0's, T[2]-T[1] 1's,
00050   T[3]-T[2] 2's, and so on, and concluded by length(T) if T is not empty.
00051   So p = -1 if T is empty, while otherwise p = last(T).
00052   And we have t_i <= t_{i+1} <= t_i + 1.
00053   Prerequisite: T is a sequence of strictly increasing natural numbers >= 0,
00054   with a possible suffix of non-integers.
00055 */
00056 transform_threshold_l(T) :=  block(
00057  block([noti : find_first_l(lambda([x], not integerp(x)), T)],
00058   if noti#inf then T : take_l(noti-1,T)),
00059  if emptyp(T) then return([]),
00060  block([n : 0, m : 0, R : []],
00061   for x in endcons(last(T)+1,T) do (
00062     if x > n then (
00063       R : append(R,create_list(m,i,1,x-n)), 
00064       n : x
00065     ),
00066     m : m+1
00067   ),
00068   return(R)))$
00069 
00070 /* The inverse, which in general, where L is a non-decreasing list of natural
00071    numbers >= 0, computes the indices i in L (i >= 1) where L[i+1] > L[i],
00072    and appends them to the result: */
00073 transform_steps_l(L) := if length(L) <= 1 then [] else
00074  block([a : first(L), i : 1, R : []],
00075   for b in rest(L) do (
00076     if b > a then (R : endcons(i,R), a : b),
00077     i : i + 1
00078   ),
00079   return(R))$
00080 
00081 /* The inversion-relation more precisely:
00082    Consider the following two sets of finite sequences of natural numbers:
00083    - the set M of finite, strictly increasing sequences
00084      (possibly empty) of natural numbers >= 1,
00085    - and the set N of finite,
00086      non-decreasing sequences (possibly empty) of natural numbers >= 0, which
00087      for a non-empty list after removal of repeated elements are the sequences
00088      0,1,2,...,m for m >= 1, and where the last element is strictly greater
00089      than the penultimate element.
00090    Now transform_threshold_l is a bijection from M to N with inverse
00091    transform_steps_l.
00092    To understand the definitions of M and N, the sequences in M are 1-based,
00093    while the sequences in N are 0-based.
00094    transform_threshold_l([k]) thus is k 0's, followed by 1, while
00095    transform_steps_l([0,0,1]) is [2].
00096 
00097    The sequences in N are given by vanderwaerden_{m+1}([2]_m, k), for
00098    m = 0, 1, ... (though the index is 1-based, thus considering in a sense
00099    the length of the whole list), where k >= 1, while the sequences in M are
00100    given by tau_arithprog(k,n), for n = 0, 1, ... .
00101    Alternatively, the sequences in N are given by alpha_arithprog(k,n),
00102    for n = 0, 1, ..., while the sequences in M yield a "compressed"
00103    presentation (called "steplists" below) of these lists.
00104 */
00105 
00106 /* Treating L as a list of transversal- or independence-numbers, and computing
00107    the complementary numbers, using the index (n=1, ...) as the number of
00108    elements:
00109 */
00110 alphatau_l(L) := create_list(i,i,1,length(L)) - L$
00111 
00112 /* Given an "alpha-steplist", compute the associated list of
00113    transversal-numbers (of the hypergraphs; starting with n=1).
00114    S is a non-empty list of strictly increasing natural numbers >= 1.
00115 */
00116 alphastep2tau(S) := alphatau_l(rest(transform_threshold_l(S)))$
00117 /* The inverse, i.e., given a list of transversal-numbers (starting with n=1),
00118    compute the associated "alpha-steplist".
00119    T is a non-empty list of non-decreasing natural numbers >= 0, where every
00120    step is +1.
00121 */
00122 tau2alphastep(T) := transform_steps_l(cons(0,alphatau_l(T)))$
00123 /* Note that we always have
00124      tau2alphastep(alphastep2tau(S)) = S,
00125    however alphastep2tau(tau2alphastep(T)) will a tail of T leading to a
00126    constant tail of alpha-values will be reduced to length 1.
00127 */
00128 
00129 
00130 /* ************
00131    * Analysis *
00132    ************
00133 */
00134 
00135 /* For a given Ramsey-number-function N, compute the list
00136    N([k,k], N([k-1,k+1]), ..., N([2,2k+2]):
00137 */
00138 deharmonise_eval_2(k,N_) := map(N_, create_list([k-i,k+i],i,0,k-2))$
00139 
00140