    001package org.cpsolver.ifs.util;
    002
    003import java.io.ByteArrayOutputStream;
    004import java.io.File;
    005import java.io.FileInputStream;
    006import java.io.IOException;
    007import java.io.OutputStream;
    008import java.io.PrintStream;
    009import java.util.ArrayList;
    010import java.util.Collection;
    011import java.util.Date;
    012import java.util.Enumeration;
    013import java.util.HashSet;
    014import java.util.Iterator;
    015import java.util.List;
    016import java.util.Map;
    017import java.util.Properties;
    018import java.util.Random;
    019import java.util.Set;
    020import java.util.StringTokenizer;
    021import java.util.TreeSet;
    022
    023import org.apache.logging.log4j.Level;
    024import org.apache.logging.log4j.LogManager;
    025import org.apache.logging.log4j.Logger;
    026import org.apache.logging.log4j.core.config.Configurator;
    027import org.apache.logging.log4j.core.config.builder.api.AppenderComponentBuilder;
    028import org.apache.logging.log4j.core.config.builder.api.ComponentBuilder;
    029import org.apache.logging.log4j.core.config.builder.api.ConfigurationBuilder;
    030import org.apache.logging.log4j.core.config.builder.api.ConfigurationBuilderFactory;
    031import org.apache.logging.log4j.core.config.builder.api.LayoutComponentBuilder;
    032import org.apache.logging.log4j.core.config.builder.api.LoggerComponentBuilder;
    033import org.apache.logging.log4j.core.config.builder.api.RootLoggerComponentBuilder;
    034import org.apache.logging.log4j.core.config.builder.impl.BuiltConfiguration;
    035
    036/**
    037 * Several auxiliary static methods.
    038 *
    039 * @version IFS 1.3 (Iterative Forward Search)<br>
    040 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    041 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    042 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    043 * <br>
    044 *          This library is free software; you can redistribute it and/or modify
    045 *          it under the terms of the GNU Lesser General Public License as
    046 *          published by the Free Software Foundation; either version 3 of the
    047 *          License, or (at your option) any later version. <br>
    048 * <br>
    049 *          This library is distributed in the hope that it will be useful, but
    050 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    051 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    052 *          Lesser General Public License for more details. <br>
    053 * <br>
    054 *          You should have received a copy of the GNU Lesser General Public
    055 *          License along with this library; if not see
    056 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    057 */
    058public class ToolBox {
    059    private static long sSeed = System.currentTimeMillis();
    060    private static Random sRandom = new Random(sSeed);
    061
    062    /** Returns random number (int) from the set 0 .. limit - 1
    063     * @param limit a limit
    064     * @return a random number between 0 and limit - 1
    065     **/
    066    public static int random(int limit) {
    067        return (int) (random() * limit);
    068    }
    069
    070    /** Returns random element from the given set of elements
    071     * @param set collection of objects
    072     * @param <E> some type
    073     * @return randomly selected object
    074     **/
    075    public static <E> E random(Collection<E> set) {
    076        switch (set == null ? 0 : set.size()) {
    077            case 0:
    078                return null;
    079            case 1:
    080                return set.iterator().next();
    081            case 2:
    082                Iterator<E> i = set.iterator();
    083                if (sRandom.nextBoolean()) i.next();
    084                return i.next();
    085            default:
    086                int index = random(set.size());
    087                if (set instanceof List<?>) return ((List<E>)set).get(index);
    088                Iterator<E> it = set.iterator();
    089                for (int j = 0; j < index; j++) it.next();
    090                return it.next();
    091        }
    092    }
    093
    094    /**
    095     * Returns a randomly generated subset of the given set
    096     *
    097     * @param set
    098     *            set
    099     * @param part
    100     *            probability of selection of an element into the resultant
    101     *            subset
    102     * @param <E> some type
    103     * @return randomly selected subset
    104     */
    105    public static <E> Collection<E> subSet(Collection<E> set, double part) {
    106        return subSet(set, part, 1);
    107    }
    108
    109    /** Swaps two elements in the list*/
    110    private static <E> void swap(List<E> list, int first, int second) {
    111        E o = list.get(first);
    112        list.set(first, list.get(second));
    113        list.set(second, o);
    114    }
    115
    116    /**
    117     * Returns a randomly generated subset of the given set
    118     *
    119     * @param set
    120     *            set
    121     * @param part
    122     *            probability of selection of an element into the resultant
    123     *            subset
    124     * @param minSize
    125     *            minimal size of the returned subset
    126     * @param <E> some type
    127     * @return randomly selected subset
    128     */
    129    public static <E> Collection<E> subSet(Collection<E> set, double part, int minSize) {
    130        if (set.size() <= minSize || part >= 1.0)
    131            return set;
    132        ArrayList<E> subSet = new ArrayList<E>(set);
    133        int size = set.size();
    134        int numberToSelect = Math.max(minSize, (int) (part * set.size()));
    135        for (int idx = 0; idx < numberToSelect; idx++) {
    136            swap(subSet, idx, idx + (int) (random() * (size - idx)));
    137        }
    138        return subSet.subList(0, numberToSelect);
    139    }
    140
    141    /** Trim a string to have given length
    142     * @param s a string to trim
    143     * @param length a length to trim to
    144     * @return trimmed and padded string of the given length
    145     **/
    146    public static String trim(String s, int length) {
    147        if (s.length() > length)
    148            return s.substring(0, length);
    149        StringBuffer sb = new StringBuffer(s);
    150        while (sb.length() < length)
    151            sb.append(" ");
    152        return sb.toString();
    153    }
    154
    155    /** Multiline representation of a collection
    156     * @param col a collection
    157     * @param tab tab size
    158     * @return string representation
    159     **/
    160    public static String col2string(Collection<?> col, int tab) {
    161        StringBuffer tabsb = new StringBuffer();
    162        while (tabsb.length() < 2 * tab)
    163            tabsb.append("  ");
    164        StringBuffer sb = new StringBuffer("[\n");
    165        for (Iterator<?> i = col.iterator(); i.hasNext();) {
    166            sb.append(tabsb + "  " + i.next() + (i.hasNext() ? "," : "") + "\n");
    167        }
    168        sb.append(tabsb + "]");
    169        return sb.toString();
    170    }
    171
    172    /** Multiline representation of a dictionary
    173     * @param dict a map
    174     * @param tab tab size
    175     * @param <K> a key class
    176     * @param <V> a value class
    177     * @return string representation
    178     */
    179    public static <K, V> String dict2string(Map<K, V> dict, int tab) {
    180        StringBuffer tabsb = new StringBuffer();
    181        while (tabsb.length() < 2 * tab)
    182            tabsb.append("  ");
    183        StringBuffer sb = new StringBuffer("[\n");
    184        TreeSet<K> keys = new TreeSet<K>(dict.keySet());
    185        for (K key : keys) {
    186            V value = dict.get(key);
    187            sb.append(tabsb + "  " + key + ": " + value + "\n");
    188        }
    189        sb.append(tabsb + "]");
    190        return sb.toString();
    191    }
    192
    193    /**
    194     * Root mean square
    195     *
    196     * @param n
    197     *            number of tests
    198     * @param x
    199     *            total value of all tests
    200     * @param x2
    201     *            total value^2 of all tests
    202     * @return root mean square
    203     */
    204    public static double rms(int n, double x, double x2) {
    205        double var = x2 / n;
    206        double mean = x / n;
    207        return Math.sqrt(Math.abs(var - mean * mean));
    208    }
    209
    210    /** Merge source with target
    211     * @param target target list
    212     * @param source source list
    213     * @param <E> some object
    214     **/
    215    public static <E> void merge(List<E> target, Collection<E> source) {
    216        for (E o : source) {
    217            if (!target.contains(o))
    218                target.add(o);
    219        }
    220    }
    221
    222    /** Returns intersection of two collections
    223     * @param source1 first collection
    224     * @param source2 second collection
    225     * @param <E> some object
    226     * @return intersection
    227     */
    228    public static <E> List<E> intersect(Collection<E> source1, Collection<E> source2) {
    229        List<E> target = new ArrayList<E>();
    230        for (E o : source1) {
    231            if (!source2.contains(o))
    232                target.add(o);
    233        }
    234        return target;
    235    }
    236
    237    /**
    238     * Sets seeds for {@link ToolBox#getRandom()} and {@link ToolBox#random()}
    239     * methods.
    240     * @param seed random seed
    241     */
    242    public static void setSeed(long seed) {
    243        sSeed = seed;
    244        sRandom = new Random(sSeed);
    245    }
    246
    247    /** Gets current seed
    248     * @return random seed
    249     **/
    250    public static long getSeed() {
    251        return sSeed;
    252    }
    253
    254    /** Gets random number generator
    255     * @return random number generator
    256     **/
    257    public static Random getRandom() {
    258        return sRandom;
    259    }
    260
    261    /** Generates random double number
    262     * @return random number
    263     **/
    264    public static double random() {
    265        return sRandom.nextDouble();
    266    }
    267
    268    /** Configurates log4j loging */
    269    public static void configureLogging() {
    270        if ("true".equalsIgnoreCase(System.getProperty("org.cpsolver.debug", "false"))) {
    271            Configurator.setLevel("org.cpsolver", Level.DEBUG);
    272        }
    273    }
    274
    275    /**
    276     * Setup log4j logging
    277     *
    278     * @param logFile  log file
    279     * @param debug true if debug messages should be logged (use -Ddebug=true to enable debug message)
    280     */
    281    public static void setupLogging(File logFile, boolean debug) {
    282        ConfigurationBuilder<BuiltConfiguration> builder = ConfigurationBuilderFactory.newConfigurationBuilder();
    283
    284        AppenderComponentBuilder console = builder.newAppender("stdout", "Console");
    285        console.addAttribute("target", "SYSTEM_OUT");
    286        LayoutComponentBuilder consoleLayout = builder.newLayout("PatternLayout");
    287        consoleLayout.addAttribute("pattern", "%-5p %c{2}: %m%n");
    288        console.add(consoleLayout);
    289        builder.add(console);
    290
    291        RootLoggerComponentBuilder root = builder.newRootLogger(Level.INFO);
    292        root.add(builder.newAppenderRef("stdout"));
    293        builder.add(root);
    294
    295        if (logFile != null) {
    296            AppenderComponentBuilder file = builder.newAppender("log", "File");
    297            file.addAttribute("fileName", logFile.getPath());
    298
    299            LayoutComponentBuilder filePattern = builder.newLayout("PatternLayout");
    300            filePattern.addAttribute("pattern", "%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n");
    301            file.add(filePattern);
    302            builder.add(file);
    303
    304            LoggerComponentBuilder logger = builder.newLogger("org.cpsolver", debug ? Level.DEBUG : Level.INFO);
    305            logger.add(builder.newAppenderRef("log"));
    306            logger.addAttribute("additivity", true);
    307            builder.add(logger);
    308        }
    309        Configurator.reconfigure(builder.build());
    310    }
    311
    312    /**
    313     * Configure log4j logging
    314     *
    315     * @param logDir
    316     *            output folder
    317     * @param properties
    318     *            some other log4j properties
    319     * @return name of the log file
    320     */
    321    public static String configureLogging(String logDir, Properties properties) {
    322        return configureLogging(logDir, properties, false);
    323    }
    324
    325    /**
    326     * Configure log4j logging
    327     *
    328     * @param logDir
    329     *            output folder
    330     * @param properties
    331     *            some other log4j properties
    332     * @param timeInFileName
    333     *            if true log file is named debug_yyyy-MM-dd_(HH.mm.ss).log, it
    334     *            is named debug.log otherwise
    335     * @return name of the log file
    336     */
    337    public static String configureLogging(String logDir, Properties properties, boolean timeInFileName) {
    338        return configureLogging(logDir, properties, timeInFileName, true);
    339    }
    340
    341    /**
    342     * Configure log4j logging
    343     *
    344     * @param logDir
    345     *            output folder
    346     * @param properties
    347     *            some other log4j properties
    348     * @param timeInFileName
    349     *            if true log file is named debug_yyyy-MM-dd_(HH.mm.ss).log, it
    350     *            is named debug.log otherwise
    351     * @param includeSystemOuts include system out and error in the log
    352     * @return name of the log file
    353     */
    354    public static String configureLogging(String logDir, Properties properties, boolean timeInFileName, boolean includeSystemOuts) {
    355        (new File(logDir)).mkdirs();
    356
    357        ConfigurationBuilder<BuiltConfiguration> builder = ConfigurationBuilderFactory.newConfigurationBuilder();
    358
    359        AppenderComponentBuilder console = builder.newAppender("stdout", "Console");
    360        LayoutComponentBuilder consoleLayout = builder.newLayout("PatternLayout");
    361        consoleLayout.addAttribute("pattern", "[%t] %m%n");
    362        console.add(consoleLayout);
    363        builder.add(console);
    364
    365        AppenderComponentBuilder file = null;
    366        String fileName = null;
    367        if (timeInFileName) {
    368            file = builder.newAppender("log", "File");
    369            String time = new java.text.SimpleDateFormat("yyyy-MM-dd_(HH.mm.ss)", java.util.Locale.US).format(new Date());
    370            fileName = logDir + File.separator + "debug_" + time + ".log";
    371            file.addAttribute("fileName", fileName);
    372        } else {
    373            file = builder.newAppender("log", "RollingFile");
    374            fileName = logDir + File.separator + "debug.log";
    375            file.addAttribute("fileName", fileName);
    376            file.addAttribute("filePattern", logDir + File.separator + "debug-%d{MM-dd-yy}-%i.log.gz");
    377            ComponentBuilder<?> triggeringPolicies = builder.newComponent("Policies")
    378                    .addComponent(builder.newComponent("CronTriggeringPolicy").addAttribute("schedule", "0 0 0 * * ?"))
    379                    .addComponent(builder.newComponent("SizeBasedTriggeringPolicy").addAttribute("size", "100M"));
    380            file.addComponent(triggeringPolicies);
    381        }
    382        LayoutComponentBuilder filePattern = builder.newLayout("PatternLayout");
    383        filePattern.addAttribute("pattern", "%d{dd-MMM-yy HH:mm:ss.SSS} [%t] %-5p %c{2}> %m%n");
    384        file.add(filePattern);
    385        builder.add(file);
    386
    387        RootLoggerComponentBuilder root = builder.newRootLogger("true".equals(System.getProperty("org.cpsolver.debug", "false")) ? Level.DEBUG : Level.INFO);
    388        root.add(builder.newAppenderRef("log"));
    389        builder.add(root);
    390
    391        LoggerComponentBuilder info = builder.newLogger("org.cpsolver", Level.INFO);
    392        info.add(builder.newAppenderRef("stdout"));
    393        info.addAttribute("additivity", true);
    394        builder.add(info);
    395
    396        if (properties != null) {
    397            for (Map.Entry<Object, Object> e: properties.entrySet()) {
    398                String property = (String)e.getKey();
    399                String value = (String)e.getValue();
    400                if (property.startsWith("log4j.logger.")) {
    401                    if (value.indexOf(',') < 0) {
    402                        LoggerComponentBuilder logger = builder.newLogger(property.substring("log4j.logger.".length()), Level.getLevel(value));
    403                        builder.add(logger);
    404                    } else {
    405                        String level = value.substring(0, value.indexOf(','));
    406                        String appender = value.substring(value.indexOf(',') + 1);
    407                        LoggerComponentBuilder logger = builder.newLogger(property.substring("log4j.logger.".length()), Level.getLevel(level));
    408                        for (String a: appender.split(","))
    409                            logger.add(builder.newAppenderRef(a));
    410                        builder.add(logger);
    411                    }
    412                }
    413            }
    414        }
    415        Configurator.reconfigure(builder.build());
    416
    417        Logger log = LogManager.getRootLogger();
    418        log.info("-----------------------------------------------------------------------");
    419        log.info("IFS debug file");
    420        log.info("");
    421        log.info("Created: " + new Date());
    422        log.info("");
    423        log.info("System info:");
    424        log.info("System:      " + System.getProperty("os.name") + " " + System.getProperty("os.version") + " "
    425                + System.getProperty("os.arch"));
    426        log.info("CPU:         " + System.getProperty("sun.cpu.isalist") + " endian:"
    427                + System.getProperty("sun.cpu.endian") + " encoding:" + System.getProperty("sun.io.unicode.encoding"));
    428        log.info("Java:        " + System.getProperty("java.vendor") + ", " + System.getProperty("java.runtime.name")
    429                + " " + System.getProperty("java.runtime.version", System.getProperty("java.version")));
    430        log.info("User:        " + System.getProperty("user.name"));
    431        log.info("Timezone:    " + System.getProperty("user.timezone"));
    432        log.info("Working dir: " + System.getProperty("user.dir"));
    433        log.info("Classpath:   " + System.getProperty("java.class.path"));
    434        log.info("");
    435        if (includeSystemOuts) {
    436            System.setErr(new PrintStream(new LogOutputStream(System.err, org.apache.logging.log4j.LogManager.getLogger("STDERR"), Level.ERROR)));
    437            System.setOut(new PrintStream(new LogOutputStream(System.out, org.apache.logging.log4j.LogManager.getLogger("STDOUT"), Level.DEBUG)));
    438        }
    439        return fileName;
    440    }
    441
    442    /**
    443     * Loads data properties. If there is INCLUDE property available, it is
    444     * interpreted as semi-colon separated list of porperty files which should
    445     * be also loaded (works recursively).
    446     * @param propertyFile a file to read
    447     * @return solver configuration
    448     *
    449     */
    450    public static DataProperties loadProperties(File propertyFile) {
    451        FileInputStream is = null;
    452        try {
    453            DataProperties ret = new DataProperties();
    454            is = new FileInputStream(propertyFile);
    455            ret.load(is);
    456            is.close();
    457            is = null;
    458            if (ret.getProperty("INCLUDE") != null) {
    459
    460                StringTokenizer stk = new StringTokenizer(ret.getProperty("INCLUDE"), ";");
    461                while (stk.hasMoreTokens()) {
    462                    String aFile = stk.nextToken();
    463                    System.out.println("  Loading included file '" + aFile + "' ... ");
    464                    if ((new File(aFile)).exists())
    465                        is = new FileInputStream(aFile);
    466                    if ((new File(propertyFile.getParent() + File.separator + aFile)).exists())
    467                        is = new FileInputStream(propertyFile.getParent() + File.separator + aFile);
    468                    if (is == null)
    469                        System.err.println("Unable to find include file '" + aFile + "'.");
    470                    ret.load(is);
    471                    is.close();
    472                    is = null;
    473                }
    474                ret.remove("INCLUDE");
    475            }
    476            return ret;
    477        } catch (Exception e) {
    478            System.err.println("Unable to load property file " + propertyFile);
    479            e.printStackTrace();
    480            return new DataProperties();
    481        } finally {
    482            try {
    483                if (is != null)
    484                    is.close();
    485            } catch (IOException e) {
    486            }
    487        }
    488    }
    489
    490    public static boolean equals(Object o1, Object o2) {
    491        return (o1 == null ? o2 == null : o1.equals(o2));
    492    }
    493
    494    private static class LogOutputStream extends OutputStream {
    495        private Logger iLogger = null;
    496        private Level iLevel = null;
    497        private OutputStream iOldOutputStream;
    498        private ByteArrayOutputStream iOut = new ByteArrayOutputStream();
    499
    500        public LogOutputStream(OutputStream oldOutputStream, Logger logger, Level level) {
    501            iLogger = logger;
    502            iLevel = level;
    503            iOldOutputStream = oldOutputStream;
    504        }
    505
    506        @Override
    507        public void write(int b) throws IOException {
    508            iOldOutputStream.write(b);
    509            if (b == '\r')
    510                return;
    511            if (b == '\n') {
    512                iOut.flush();
    513                iLogger.log(iLevel, new String(iOut.toByteArray()));
    514                iOut.reset();
    515            } else
    516                iOut.write(b);
    517        }
    518    }
    519
    520    /**
    521     * Convert array of elements into a list
    522     * @param obj array of elements
    523     * @return list of elements
    524     */
    525    public static <E> List<E> toList(E... obj) {
    526        List<E> ret = new ArrayList<E>(obj == null ? 0 : obj.length);
    527        if (obj != null)
    528            for (E e: obj)
    529                ret.add(e);
    530        return ret;
    531    }
    532
    533    /**
    534     * Compute number of K-tuples of N elements
    535     * @param N number of elements (e.g., number of room locations in a domain)
    536     * @param K size of a tuple (e.g., number of rooms a class needs)
    537     * @return number of different K-tupples of N elements
    538     */
    539    public static long binomial(int N, int K) {
    540        long ret = 1;
    541        for (int k = 0; k < K; k++)
    542            ret = ret * (N-k) / (k+1);
    543        return ret;
    544    }
    545
    546    /**
    547     * Create random sample (m-tuple) of given list of elements
    548     * @param items list of elements
    549     * @param m size of a tuple
    550     * @return random subset of the list of size m
    551     */
    552    public static <E> Set<E> sample(List<E> items, int m) {
    553        HashSet<E> res = new HashSet<E>(m);
    554        int n = items.size();
    555        for(int i = n - m; i < n; i++){
    556            int pos = getRandom().nextInt(i+1);
    557            E item = items.get(pos);
    558            if (res.contains(item))
    559                res.add(items.get(i));
    560            else
    561                res.add(item);
    562        }
    563        return res;
    564    }
    565
    566    /**
    567     * Generate given permutation
    568     * @param items list of elements
    569     * @param m size of a tuple (permutation)
    570     * @param id position of the permutation in the list of all permutations of m-tuples of the given list of elements
    571     * @return given subset of the list of size m
    572     */
    573    public static <E> List<E> permutation(final List<E> items, int m, long id) {
    574        List<E> ret = new ArrayList<E>();
    575        int n = items.size();
    576        int p = -1;
    577        for (int i = 0; i < m - 1; i++) {
    578            p ++;
    579            for (long r = binomial(n - p - 1, m - i - 1); r <= id; r = binomial(n - p - 1, m - i - 1))  {
    580                id -= r; p ++;
    581            }
    582            ret.add(items.get(p));
    583        }
    584        ret.add(items.get(p + 1 + (int)id));
    585        return ret;
    586    }
    587
    588    /**
    589     * Generate a list of samples of the given list
    590     * @param items list of elements
    591     * @param m size of a sample
    592     * @param count number of samples
    593     * @return list of samples (m-tuples) of the given items
    594     */
    595    public static <E> Enumeration<Collection<E>> sample(final List<E> items, final int m, final int count) {
    596        final long limit = binomial(items.size(), m);
    597        if (count >= limit) return permutations(items, m);
    598        return new Enumeration<Collection<E>>() {
    599            int el = 0;
    600            Set<Long> used = new HashSet<Long>();
    601
    602            @Override
    603            public boolean hasMoreElements() {
    604                return el < count && el < limit;
    605            }
    606
    607            @Override
    608            public Set<E> nextElement() {
    609                int n = items.size();
    610                for (;;) {
    611                    HashSet<E> res = new HashSet<E>(m);
    612                    TreeSet<Integer> ids = new TreeSet<Integer>();
    613                    for(int i = n - m; i < n; i++){
    614                        int pos = getRandom().nextInt(i+1);
    615                        E item = items.get(pos);
    616                        if (res.contains(item)) {
    617                            res.add(items.get(i));
    618                            ids.add(i);
    619                        } else {
    620                            res.add(item);
    621                            ids.add(pos);
    622                        }
    623                    }
    624                    long fp = 0;
    625                    for (Integer id: ids) {
    626                        fp = (n * fp) + id;
    627                    }
    628                    if (used.add(fp)) {
    629                        el ++;
    630                        return res;
    631                    }
    632                }
    633            }
    634        };
    635    }
    636
    637    /**
    638     * Generate a list of all permutations of size m of the given list
    639     * @param items list of elements
    640     * @param m size of a permutation
    641     * @return list of all permutations (m-tuples) of the given items
    642     */
    643    public static <E> Enumeration<Collection<E>> permutations(final List<E> items, final int m) {
    644        return new Enumeration<Collection<E>>() {
    645            int n = items.size();
    646            int[] p = null;
    647
    648            @Override
    649            public boolean hasMoreElements() {
    650                return p == null || p[0] < n - m;
    651            }
    652
    653            @Override
    654            public Collection<E> nextElement() {
    655                if (p == null) {
    656                    p = new int[m];
    657                    for (int i = 0; i < m; i++)
    658                        p[i] = i;
    659                } else {
    660                    for (int i = m - 1; i >= 0; i--) {
    661                        p[i] = p[i] + 1;
    662                        for (int j = i + 1; j < m; j++)
    663                            p[j] = p[j - 1] + 1;
    664                        if (i == 0 || p[i] <= n - (m - i)) break;
    665                    }
    666                }
    667                List<E> ret = new ArrayList<E>();
    668                for (int i = 0; i < m; i++)
    669                    ret.add(items.get(p[i]));
    670                return ret;
    671            }
    672        };
    673    }
    674
    675    /**
    676     * Generate a list of random samples combined of the given two lists
    677     * @param items1 list of first elements
    678     * @param m1 size of a first sample
    679     * @param items2 list of second elements
    680     * @param m2 size of a second sample
    681     * @param count number of samples
    682     * @return list of samples where each sample contains m1 elements of the first list and m2 elements of the second list
    683     */
    684    private static <E> Enumeration<Collection<E>> sample(final List<E> items1, final int m1, final List<E> items2, final int m2, final int count) {
    685        final long c1 = binomial(items1.size(), m1);
    686        final long c2 = binomial(items2.size(), m2);
    687        final long limit = c1 * c2;
    688        if (limit <= 10l * count && 10l * count < Integer.MAX_VALUE) {
    689            return new Enumeration<Collection<E>>() {
    690                Set<Integer> used = new HashSet<Integer>();
    691
    692                @Override
    693                public boolean hasMoreElements() {
    694                    return used.size() < count && used.size() < limit;
    695                }
    696
    697                @Override
    698                public Collection<E> nextElement() {
    699                    int id;
    700                    do {
    701                        id = getRandom().nextInt((int)limit);
    702                    } while (!used.add(id));
    703                    List<E> res = new ArrayList<E>(m1 + m2);
    704                    if (m1 > 0)
    705                        res.addAll(permutation(items1, m1, id / c2));
    706                    if (m2 > 0)
    707                        res.addAll(permutation(items2, m2, id % c2));
    708                    return res;
    709                }
    710            };
    711        } else {
    712            return new Enumeration<Collection<E>>() {
    713                int n1 = items1.size(), n2 = items2.size();
    714                int el = 0;
    715                Set<Long> used = new HashSet<Long>();
    716
    717                @Override
    718                public boolean hasMoreElements() {
    719                    return el < count && el < limit;
    720                }
    721
    722                @Override
    723                public Collection<E> nextElement() {
    724                    for (;;) {
    725                        HashSet<E> res = new HashSet<E>(m1 + m2);
    726                        TreeSet<Integer> ids1 = new TreeSet<Integer>();
    727                        if (m1 == n1) {
    728                            // Special case 1: first permutation contains all elements
    729                            res.addAll(items1);
    730                        } else if (m1 + 1 == n1) {
    731                            // Special case 2: first permutation contains all elements but one
    732                            int pos = getRandom().nextInt(n1);
    733                            for (int i = 0; i < n1; i++)
    734                                if (i != pos) res.add(items1.get(i));
    735                            ids1.add(pos);
    736                        } else {
    737                            for(int i = n1 - m1; i < n1; i++){
    738                                int pos = getRandom().nextInt(i+1);
    739                                E item = items1.get(pos);
    740                                if (res.contains(item)) {
    741                                    res.add(items1.get(i));
    742                                    ids1.add(i);
    743                                } else {
    744                                    res.add(item);
    745                                    ids1.add(pos);
    746                                }
    747                            }
    748                        }
    749                        TreeSet<Integer> ids2 = new TreeSet<Integer>();
    750                        if (m2 == n2) {
    751                            // Special case 1: second permutation contains all elements
    752                            res.addAll(items2);
    753                        } else if (m2 + 1 == n2) {
    754                            // Special case 2: second permutation contains all elements but one
    755                            int pos = getRandom().nextInt(n2);
    756                            for (int i = 0; i < n2; i++)
    757                                if (i != pos) res.add(items2.get(i));
    758                            ids2.add(pos);
    759                        } else {
    760                            for(int i = n2 - m2; i < n2; i++){
    761                                int pos = getRandom().nextInt(i+1);
    762                                E item = items2.get(pos);
    763                                if (res.contains(item)) {
    764                                    res.add(items2.get(i));
    765                                    ids2.add(n1 + i);
    766                                } else {
    767                                    res.add(item);
    768                                    ids2.add(n1 + pos);
    769                                }
    770                            }
    771                        }
    772                        long fp = 0;
    773                        for (Integer id: ids1) fp = (n1 * fp) + id;
    774                        for (Integer id: ids2) fp = (n2 * fp) + id;
    775                        if (used.add(fp)) {
    776                            el ++;
    777                            return res;
    778                        }
    779                    }
    780                }
    781            };
    782        }
    783    }
    784
    785    /**
    786     * Generate a list of random samples combined of the given two lists
    787     * @param preferred list of preferred elements
    788     * @param additional list of additional elements
    789     * @param m size of a sample
    790     * @param count number of samples
    791     * @return list of samples of size m, preferring as many elements of the preferred list as possible
    792     */
    793    public static <E> Enumeration<Collection<E>> sample(final List<E> preferred, final List<E> additional, final int m, final int count) {
    794        return new Enumeration<Collection<E>>() {
    795            long limit = Math.min(count, binomial(preferred.size() + additional.size(), m));
    796            int k = Math.min(m, preferred.size());
    797            int el = 0;
    798            Enumeration<Collection<E>> e = sample(preferred, k, additional, m - k, count);
    799
    800            @Override
    801            public boolean hasMoreElements() {
    802                return el < limit;
    803            }
    804
    805            @Override
    806            public Collection<E> nextElement() {
    807                if (e.hasMoreElements()) {
    808                    el ++;
    809                    return e.nextElement();
    810                }
    811                k = Math.max(Math.min(k - 1, preferred.size() - 1), 0);
    812                e = sample(preferred, k, additional, m - k, count);
    813                el ++;
    814                return e.nextElement();
    815            }
    816        };
    817    }
    818}