    001package org.cpsolver.studentsct;
    002
    003import java.text.DecimalFormat;
    004import java.util.Comparator;
    005import java.util.HashMap;
    006import java.util.Iterator;
    007import java.util.TreeSet;
    008
    009import org.cpsolver.ifs.util.JProf;
    010
    011
    012/**
    013 * A test class to demonstrate and compare different online sectioning
    014 * approaches. It assumes only a single course with just one instructional type
    015 * (subpart) and that we know the correct expected demand in advance. <br>
    016 * <br>
    017 * With the given configuration (e.g., two sections of size 5), it tries all
    018 * combinations of students how they can be enrolled and compute average and
    019 * worst case scenarios. <br>
    020 * <br>
    021 * Execution:<br>
    022 * &nbsp;&nbsp;&nbsp;&nbsp;java -cp cpsolver-all-1.1.jar
    023 * org.cpsolver.studentsct.OnlineSectProof n1 n2 n3 ...<br>
    024 * where n1, n2, etc. are the sizes of particular sections, e.g., 10 10 for two
    025 * sections of size 10. <br>
    026 * <br>
    027 *
    028 * @version StudentSct 1.3 (Student Sectioning)<br>
    029 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    030 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    031 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    032 * <br>
    033 *          This library is free software; you can redistribute it and/or modify
    034 *          it under the terms of the GNU Lesser General Public License as
    035 *          published by the Free Software Foundation; either version 3 of the
    036 *          License, or (at your option) any later version. <br>
    037 * <br>
    038 *          This library is distributed in the hope that it will be useful, but
    039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    041 *          Lesser General Public License for more details. <br>
    042 * <br>
    043 *          You should have received a copy of the GNU Lesser General Public
    044 *          License along with this library; if not see
    045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    046 */
    047public class OnlineSectProof {
    048    private static DecimalFormat sDF = new DecimalFormat("0.000");
    049
    050    /** A representation of a long number of given base. */
    051    public static class Sequence {
    052        private int iBase;
    053        private int[] iSequence;
    054        private int[] iCnt;
    055
    056        /**
    057         * Constructor
    058         *
    059         * @param length
    060         *            size of the vector
    061         * @param base
    062         *            base (e.g., 2 for a binary vector)
    063         */
    064        public Sequence(int length, int base) {
    065            iSequence = new int[length];
    066            for (int i = 0; i < iSequence.length; i++)
    067                iSequence[i] = 0;
    068            iCnt = new int[base];
    069            for (int i = 0; i < iCnt.length; i++)
    070                iCnt[i] = 0;
    071            iCnt[0] = length;
    072            iBase = base;
    073        }
    074
    075        /**
    076         * Increment vector by 1, returns false it flips from the highest
    077         * possible number to zero
    078         * @return false if flipped back to zero
    079         */
    080        public boolean inc() {
    081            return inc(0);
    082        }
    083
    084        /** Base of the sequence
    085         * @return sequence base
    086         **/
    087        public int base() {
    088            return iBase;
    089        }
    090
    091        private boolean inc(int pos) {
    092            if (pos >= iSequence.length)
    093                return false;
    094            iCnt[iSequence[pos]]--;
    095            iSequence[pos] = (iSequence[pos] + 1) % iBase;
    096            iCnt[iSequence[pos]]++;
    097            if (iSequence[pos] == 0)
    098                return inc(pos + 1);
    099            return true;
    100        }
    101
    102        /** Count number of occurrences of given number in the sequence
    103         * @param i given number
    104         * @return number of occurrences in the sequence
    105         **/
    106        public int count(int i) {
    107            return iCnt[i];
    108        }
    109
    110        /** Size of the sequence
    111         * @return sequence size
    112         **/
    113        public int size() {
    114            return iSequence.length;
    115        }
    116
    117        /**
    118         * Return number on the given position, zero is the number of the least
    119         * significant value, size()-1 is the highest one
    120         * @param i given position
    121         * @return number of the given position
    122         */
    123        public int seq(int i) {
    124            return iSequence[i];
    125        }
    126
    127        /**
    128         * Set the sequence from a string representation (A..0, B..1, C..2,
    129         * etc.)
    130         * @param seq a sequence
    131         */
    132        public void set(String seq) {
    133            for (int i = 0; i < iCnt.length; i++)
    134                iCnt[i] = 0;
    135            for (int i = 0; i < iSequence.length; i++) {
    136                iSequence[i] = (seq.charAt(i) - 'A');
    137                iCnt[iSequence[i]]++;
    138            }
    139        }
    140
    141        /**
    142         * String representation (A..0, B..1, C..2, etc.) going from the least
    143         * significant value to the highest
    144         */
    145        @Override
    146        public String toString() {
    147            StringBuffer s = new StringBuffer();
    148            for (int i = 0; i < iSequence.length; i++)
    149                s.append((char) ('A' + iSequence[i]));
    150            return s.toString();
    151        }
    152
    153        /**
    154         * If a sequence of all zeros is considered as 0, and the highest
    155         * possible sequence (sequence of all base-1) is 1, this returns the
    156         * position of the current sequence between these two bounds.
    157         * @return current progress
    158         */
    159        public double progress() {
    160            double ret = 0.0;
    161            double mx = 1.0;
    162            for (int i = size() - 1; i >= 0; i--) {
    163                ret += mx * (iSequence[i]) / iBase;
    164                mx *= 1.0 / iBase;
    165            }
    166            return ret;
    167        }
    168
    169        /**
    170         * Category of a sequence, i.e., a string representation of the count of
    171         * each number in the sequence. E.g., A5B3C1 means that there are 5
    172         * zeros, 3 ones, and 1 two int the sequence.
    173         * @return sequence category
    174         */
    175        public String cat() {
    176            StringBuffer s = new StringBuffer();
    177            for (int i = 0; i < iBase; i++)
    178                if (iCnt[i] > 0) {
    179                    s.append((char) ('A' + i));
    180                    s.append(iCnt[i]);
    181                }
    182            return s.toString();
    183        }
    184    }
    185
    186    /**
    187     * Extension of {@link OnlineSectProof.Sequence} that represents an ordered
    188     * set of students as they are to be enrolled into a course (given set of
    189     * sections).
    190     */
    191    public static class StudentSequence extends Sequence {
    192        private int[] iColumns;
    193        private int[] iMaxCnt;
    194
    195        /**
    196         * Constructor
    197         *
    198         * @param columns
    199         *            limits of sections of a course (e.g., new int[] {5, 10}
    200         *            for two sections, first of the size 5, second of the size
    201         *            of 10)
    202         */
    203        public StudentSequence(int[] columns) {
    204            super(length(columns), base(columns.length));
    205            iColumns = columns;
    206            iMaxCnt = new int[base()];
    207            for (int i = 0; i < iMaxCnt.length; i++)
    208                iMaxCnt[i] = maxCnt(i);
    209        }
    210
    211        /*
    212         * Number of columns, i.e., number of sections in a course.
    213         */
    214        public int nrColumns() {
    215            return iColumns.length;
    216        }
    217
    218        /**
    219         * Limit of a column (section of a course).
    220         * @param col column
    221         * @return limit
    222         */
    223        public int limit(int col) {
    224            return iColumns[col];
    225        }
    226
    227        /**
    228         * Check that the underlying sequence is a valid sequence of students.
    229         * I.e., that each student can be enrolled into a section.
    230         *
    231         * @return true, if valid
    232         */
    233        public boolean check() {
    234            for (int i = 0; i < base(); i++)
    235                if (maxCnt(i) < count(i))
    236                    return false;
    237            for (int c = 0; c < nrColumns(); c++) {
    238                int allowed = 0;
    239                for (int i = 0; i < size() && allowed < limit(c); i++)
    240                    if (allow(seq(i), c))
    241                        allowed++;
    242                if (allowed < limit(c))
    243                    return false;
    244            }
    245            return true;
    246        }
    247
    248        private static int length(int columns[]) {
    249            int len = 0;
    250            for (int i = 0; i < columns.length; i++)
    251                len += columns[i];
    252            return len;
    253        }
    254
    255        private static int base(int nrColumns) {
    256            return (1 << nrColumns) - 1;
    257        }
    258
    259        /**
    260         * Check whether it is possible to allow student of given type into the
    261         * given section. Student type can be seen as a binary string that has 1
    262         * for each section into which a student can be enrolled. I.e., student
    263         * of type 0 can be enrolled into the fist section, type 2 into the
    264         * second section, type 3 into both first and section section, type 4
    265         * into the third section, type 5 into the first and third section etc.
    266         * @param x type
    267         * @param col section
    268         * @return allowed
    269         */
    270        public boolean allow(int x, int col) {
    271            return ((x + 1) & (1 << col)) != 0;
    272        }
    273
    274        /**
    275         * Number of sections into which a student of a given type can be
    276         * enrolled (see {@link OnlineSectProof.StudentSequence#allow(int, int)}
    277         * ).
    278         * @param x type
    279         * @return number of sections
    280         */
    281        public int nrAllow(int x) {
    282            int ret = 0;
    283            for (int i = 0; i < nrColumns(); i++)
    284                if (allow(x, i))
    285                    ret++;
    286            return ret;
    287        }
    288
    289        /**
    290         * Maximum number of student of the given type that can be enrolled into
    291         * the provided sections (i.e., sum of limits of sections that are
    292         * allowed fot the student of the given type, see
    293         * {@link OnlineSectProof.StudentSequence#allow(int, int)}).
    294         * @param x type
    295         * @return maximal number of students
    296         */
    297        public int maxCnt(int x) {
    298            int ret = 0;
    299            for (int i = 0; i < nrColumns(); i++)
    300                if (allow(x, i))
    301                    ret += limit(i);
    302            return ret;
    303        }
    304    }
    305
    306    /** Implemented online algorithms (heuristics) */
    307    public static String sOnlineAlgs[] = new String[] { "Max(Available)", "Min(Used/Limit)", "Min(Expected-Available)",
    308            "Min(Expected/Available)", "Min((Expected-Available)/Limit)", "Min(Expected/(Available*Limit))" };
    309
    310    /**
    311     * Return true, if the given heuristics should be skipped (not evaluated).
    312     *
    313     * @param computeExpectations
    314     *            true, if expected demand should be computed in advance
    315     * @param alg
    316     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    317     * @param allTheSame
    318     *            true, if all the sections are of the same size
    319     * @return true if the given heuristics does not need to be computed (e.g.,
    320     *         it is the same of some other)
    321     */
    322    public static boolean skip(boolean computeExpectations, int alg, boolean allTheSame) {
    323        switch (alg) {
    324            case 0:
    325                return !computeExpectations;
    326            case 1:
    327                return !computeExpectations;
    328        }
    329        return false;
    330    }
    331
    332    /**
    333     * Implementation of the sectioning algorithms.
    334     *
    335     * @param limit
    336     *            section limit
    337     * @param used
    338     *            number of space already used
    339     * @param expected
    340     *            expected demand for the given section
    341     * @param alg
    342     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    343     * @return value that is to be minimized (i.e., a section with the lowest
    344     *         number will be picked for the student)
    345     */
    346    public static double onlineObjective(double limit, double used, double expected, int alg) {
    347        double available = limit - used;
    348        switch (alg) {
    349            case 0:
    350                return -available;
    351            case 1:
    352                return used / limit;
    353            case 2:
    354                return expected - available;
    355            case 3:
    356                return expected / available;
    357            case 4:
    358                return (expected - available) / limit;
    359            case 5:
    360                return expected / (available * limit);
    361        }
    362        return 0.0;
    363    }
    364
    365    /**
    366     * Section given sequence of students into the course and return the number
    367     * of students that cannot be sectioned.
    368     *
    369     * @param sq
    370     *            sequence of studends
    371     * @param computeExpectations
    372     *            true, if expected demand for each section should be computed
    373     *            in advance (otherwise, it is initially set to zero)
    374     * @param alg
    375     *            online algorithm (see {@link OnlineSectProof#sOnlineAlgs})
    376     * @param debug
    377     *            if true, some debug messages are printed
    378     * @return number of students that will not be sectioned in such a case
    379     */
    380    public static int checkOnline(StudentSequence sq, boolean computeExpectations, int alg, boolean debug) {
    381        int used[] = new int[sq.nrColumns()];
    382        double exp[] = new double[sq.nrColumns()];
    383        for (int i = 0; i < sq.nrColumns(); i++) {
    384            used[i] = 0;
    385            exp[i] = 0.0;
    386        }
    387        if (computeExpectations) {
    388            for (int i = 0; i < sq.size(); i++) {
    389                int x = sq.seq(i);
    390                double ex = 1.0 / sq.nrAllow(x);
    391                for (int c = 0; c < sq.nrColumns(); c++) {
    392                    if (!sq.allow(x, c))
    393                        continue;
    394                    exp[c] += ex;
    395                }
    396            }
    397        }
    398        if (debug) {
    399            StringBuffer sbExp = new StringBuffer();
    400            StringBuffer sbUse = new StringBuffer();
    401            for (int c = 0; c < sq.nrColumns(); c++) {
    402                if (c > 0) {
    403                    sbExp.append(",");
    404                    sbUse.append(",");
    405                }
    406                sbExp.append(sDF.format(exp[c]));
    407                sbUse.append(used[c]);
    408            }
    409            System.out.println("      -- initial USE:[" + sbUse + "], EXP:[" + sbExp + "], SQ:" + sq.toString()
    410                    + ", ALG:" + sOnlineAlgs[alg]);
    411        }
    412        int ret = 0;
    413        for (int i = 0; i < sq.size(); i++) {
    414            int x = sq.seq(i);
    415            int bestCol = -1;
    416            double bestObj = 0.0;
    417            for (int c = 0; c < sq.nrColumns(); c++) {
    418                if (!sq.allow(x, c))
    419                    continue;
    420                if (used[c] >= sq.limit(c))
    421                    continue;
    422                double obj = onlineObjective(sq.limit(c), used[c], exp[c], alg);
    423                if (debug)
    424                    System.out.println("      -- test " + ((char) ('A' + x)) + " --> " + (c + 1) + " (OBJ="
    425                            + sDF.format(obj) + ")");
    426                if (bestCol < 0 || bestObj > obj) {
    427                    bestCol = c;
    428                    bestObj = obj;
    429                }
    430            }
    431            if (bestCol >= 0) {
    432                used[bestCol]++;
    433                double ex = 1.0 / sq.nrAllow(x);
    434                for (int c = 0; c < sq.nrColumns(); c++) {
    435                    if (!sq.allow(x, c))
    436                        continue;
    437                    exp[c] -= ex;
    438                }
    439                if (debug) {
    440                    StringBuffer sbExp = new StringBuffer();
    441                    StringBuffer sbUse = new StringBuffer();
    442                    for (int c = 0; c < sq.nrColumns(); c++) {
    443                        if (c > 0) {
    444                            sbExp.append(",");
    445                            sbUse.append(",");
    446                        }
    447                        sbExp.append(sDF.format(exp[c]));
    448                        sbUse.append(used[c]);
    449                    }
    450                    System.out.println("    " + ((char) ('A' + x)) + " --> " + (bestCol + 1) + " (OBJ="
    451                            + sDF.format(bestObj) + ", USE:[" + sbUse + "], EXP:[" + sbExp + "])");
    452                }
    453            } else {
    454                if (debug)
    455                    System.out.println("    " + ((char) ('A' + x)) + " --> FAIL");
    456                ret++;
    457            }
    458        }
    459        return ret;
    460    }
    461
    462    /** Simple integer counter */
    463    public static class Counter {
    464        private int iCnt = 0;
    465
    466        /** A counter starting from zero */
    467        public Counter() {
    468        }
    469
    470        /** A counter starting from the given number
    471         * @param init initial value
    472         **/
    473        public Counter(int init) {
    474            iCnt = init;
    475        }
    476
    477        /** Increase counter by one */
    478        public void inc() {
    479            iCnt++;
    480        }
    481
    482        /** Increase counter by the given value
    483         * @param val increment
    484         **/
    485        public void inc(int val) {
    486            iCnt += val;
    487        }
    488
    489        /** Return counter value
    490         * @return current value
    491         **/
    492        public int intValue() {
    493            return iCnt;
    494        }
    495    }
    496
    497    /** Comparison of two categories */
    498    public static class CatCmp implements Comparator<String> {
    499        HashMap<String, Integer> iWorstCaseCat;
    500        HashMap<String, Counter> iTotalCat, iCountCat;
    501
    502        /**
    503         * Constructor
    504         *
    505         * @param countCat
    506         *            table (category, number of sequences of that category)
    507         * @param totalCat
    508         *            table (category, total number of students that were not
    509         *            sectioned of a sequence from this category)
    510         * @param worstCaseCat
    511         *            (category, worst number of students that were not
    512         *            sectioned of a sequence from this category)
    513         */
    514        public CatCmp(HashMap<String, Counter> countCat, HashMap<String, Counter> totalCat,
    515                HashMap<String, Integer> worstCaseCat) {
    516            iWorstCaseCat = worstCaseCat;
    517            iTotalCat = totalCat;
    518            iCountCat = countCat;
    519        }
    520
    521        /**
    522         * Higher number of not-sectioned students in the worst case goes first.
    523         * If the same, higher average number of not-sectioned students goes
    524         * first. If the same, compare by category.
    525         */
    526        @Override
    527        public int compare(String c1, String c2) {
    528            int wc1 = (iWorstCaseCat.get(c1)).intValue();
    529            int wc2 = (iWorstCaseCat.get(c2)).intValue();
    530            int cmp = Double.compare(wc2, wc1);
    531            if (cmp != 0)
    532                return cmp;
    533            int cc1 = (iCountCat.get(c1)).intValue();
    534            int tc1 = (iTotalCat.get(c1)).intValue();
    535            int cc2 = (iCountCat.get(c2)).intValue();
    536            int tc2 = (iTotalCat.get(c2)).intValue();
    537            cmp = Double.compare(((double) tc2) / cc2, ((double) tc1) / cc1);
    538            if (cmp != 0)
    539                return cmp;
    540            return c1.compareTo(c2);
    541        }
    542    }
    543
    544    /**
    545     * Test given course (set of sections)
    546     *
    547     * @param args
    548     *            set of integers -- limits of each sections
    549     */
    550    @SuppressWarnings("unchecked")
    551    public static void main(String[] args) {
    552        int[] x = new int[args.length];
    553        for (int i = 0; i < args.length; i++)
    554            x[i] = Integer.parseInt(args[i]);
    555        if (args.length == 0)
    556            x = new int[] { 5, 5 };
    557        boolean categories = "true".equals(System.getProperty("cat", "true"));
    558        boolean allTheSameSize = true;
    559        String filter = System.getProperty("filter");
    560
    561        StudentSequence sq = new StudentSequence(x);
    562        System.out.println("base: " + sq.base());
    563        System.out.println("columns:");
    564        int sameSize = -1;
    565        for (int col = 0; col < x.length; col++) {
    566            System.out.println("  " + (col + 1) + ". column of limit " + sq.limit(col));
    567            if (sameSize < 0)
    568                sameSize = sq.limit(col);
    569            else if (sameSize != sq.limit(col))
    570                allTheSameSize = false;
    571        }
    572        System.out.println("combinations:");
    573        for (int i = 0; i < sq.base(); i++) {
    574            System.out.println("  case " + (char) ('A' + i) + ": ");
    575            System.out.println("    max: " + sq.maxCnt(i));
    576            for (int col = 0; col < x.length; col++) {
    577                if (sq.allow(i, col))
    578                    System.out.println("      " + (col + 1) + ". column allowed");
    579            }
    580        }
    581
    582        if (System.getProperty("check") != null) {
    583            sq.set(System.getProperty("check"));
    584            if (System.getProperty("case") != null) {
    585                int i = Integer.parseInt(System.getProperty("case")) - 1;
    586                System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    587                        + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    588                checkOnline(sq, (i % 2) == 0, i / 2, true);
    589            } else {
    590                for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    591                    if (skip((i % 2) == 0, i / 2, allTheSameSize))
    592                        continue;
    593                    System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    594                            + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    595                    checkOnline(sq, (i % 2) == 0, i / 2, true);
    596                }
    597            }
    598            return;
    599        }
    600
    601        TreeSet<String>[] worstCaseSq = new TreeSet[2 * sOnlineAlgs.length];
    602        int[] worstCase = new int[2 * sOnlineAlgs.length];
    603        int[] total = new int[2 * sOnlineAlgs.length];
    604        HashMap<String, String>[] worstCaseSqCat = new HashMap[2 * sOnlineAlgs.length];
    605        HashMap<String, Integer>[] worstCaseCat = new HashMap[2 * sOnlineAlgs.length];
    606        HashMap<String, Counter>[] totalCat = new HashMap[2 * sOnlineAlgs.length];
    607        HashMap<String, Counter>[] countCat = new HashMap[2 * sOnlineAlgs.length];
    608        for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    609            total[i] = 0;
    610            worstCase[i] = -1;
    611            worstCaseSq[i] = null;
    612            worstCaseSqCat[i] = new HashMap<String, String>();
    613            worstCaseCat[i] = new HashMap<String, Integer>();
    614            totalCat[i] = new HashMap<String, Counter>();
    615            countCat[i] = new HashMap<String, Counter>();
    616        }
    617        long nrCases = 0;
    618        System.out.println("N=" + sDF.format(Math.pow(sq.base(), sq.size())));
    619        long t0 = JProf.currentTimeMillis();
    620        long mark = t0;
    621        long nc = 0, hc = 0;
    622        do {
    623            // System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
    624            if ((filter == null || filter.equals(sq.cat())) && sq.check()) {
    625                for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    626                    if (skip((i % 2) == 0, i / 2, allTheSameSize))
    627                        continue;
    628                    int onl = checkOnline(sq, (i % 2) == 0, i / 2, false);
    629                    total[i] += onl;
    630                    if (worstCaseSq[i] == null || worstCase[i] < onl) {
    631                        if (worstCaseSq[i] == null)
    632                            worstCaseSq[i] = new TreeSet<String>();
    633                        else
    634                            worstCaseSq[i].clear();
    635                        worstCaseSq[i].add(sq.toString());
    636                        worstCase[i] = onl;
    637                    } else if (worstCase[i] == onl && onl > 0 && worstCaseSq[i].size() < 100) {
    638                        worstCaseSq[i].add(sq.toString());
    639                    }
    640                    if (categories) {
    641                        String cat = sq.cat();
    642                        Counter cc = countCat[i].get(cat);
    643                        if (cc == null) {
    644                            countCat[i].put(cat, new Counter(1));
    645                        } else {
    646                            cc.inc();
    647                        }
    648                        if (onl > 0) {
    649                            Counter tc = totalCat[i].get(cat);
    650                            if (tc == null) {
    651                                totalCat[i].put(cat, new Counter(onl));
    652                            } else {
    653                                tc.inc(onl);
    654                            }
    655                            Integer wc = worstCaseCat[i].get(cat);
    656                            if (wc == null || wc.intValue() < onl) {
    657                                worstCaseCat[i].put(cat, new Integer(onl));
    658                                worstCaseSqCat[i].put(cat, sq.toString());
    659                            }
    660                        }
    661                    }
    662                }
    663                nrCases++;
    664                hc++;
    665            }
    666            nc++;
    667            if ((nc % 1000000) == 0) {
    668                mark = JProf.currentTimeMillis();
    669                double progress = sq.progress();
    670                double exp = ((1.0 - progress) / progress) * (mark - t0);
    671                System.out.println("  " + sDF.format(100.0 * progress) + "% done in "
    672                        + sDF.format((mark - t0) / 60000.0) + " min (" + sDF.format(exp / 60000.0) + " min to go, hit "
    673                        + sDF.format(100.0 * hc / nc) + "%)");
    674            }
    675        } while (sq.inc());
    676        System.out.println("Number of combinations:" + nrCases + " (hit " + sDF.format(100.0 * hc / nc) + "%)");
    677        for (int i = 0; i < 2 * sOnlineAlgs.length; i++) {
    678            if (skip((i % 2) == 0, i / 2, allTheSameSize))
    679                continue;
    680            System.out.println("Online sectioning #" + (i + 1) + " " + sOnlineAlgs[i / 2]
    681                    + ((i % 2) == 0 ? "" : " w/o precomputed expectations"));
    682            System.out.println("  worst case: " + sDF.format((100.0 * worstCase[i]) / sq.size()) + "% (" + worstCase[i]
    683                    + " of " + sq.size() + ", sequence " + worstCaseSq[i] + ")");
    684            System.out.println("  average case: " + sDF.format((100.0 * total[i]) / (sq.size() * nrCases)) + "%");
    685            sq.set(worstCaseSq[i].first());
    686            checkOnline(sq, (i % 2) == 0, i / 2, true);
    687            TreeSet<String> cats = new TreeSet<String>(new CatCmp(countCat[i], totalCat[i], worstCaseCat[i]));
    688            cats.addAll(totalCat[i].keySet());
    689            for (Iterator<String> j = cats.iterator(); j.hasNext();) {
    690                String cat = j.next();
    691                int cc = (countCat[i].get(cat)).intValue();
    692                int tc = (totalCat[i].get(cat)).intValue();
    693                int wc = (worstCaseCat[i].get(cat)).intValue();
    694                String wcsq = worstCaseSqCat[i].get(cat);
    695                System.out.println("  Category " + cat + " (size=" + cc + ")");
    696                System.out.println("    worst case: " + sDF.format((100.0 * wc) / sq.size()) + "% (" + wc + " of "
    697                        + sq.size() + ", sequence " + wcsq + ")");
    698                System.out.println("    average case: " + sDF.format((100.0 * tc) / (sq.size() * cc)) + "%");
    699            }
    700        }
    701        /*
    702         * sq.set("EEEBBBAAA");
    703         * System.out.println(sq+" (cat="+sq.cat()+", check="+sq.check()+")");
    704         * sq.set("CACACAAABB"); checkOnline(sq, true, 2, true);
    705         */
    706    }
    707
    708}