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