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