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}